当前位置 博文首页 > 庆述倾述：1～n 整数中 1 出现的次数
刷题记录第23题，上一题：字符串的排列，本题地址：1～n 整数中 1 出现的次数。
题目描述：
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12
输出：5
示例 2：
输入：n = 13
输出：6
限制：
1 <= n < 2^31
发现了一个大佬，大佬讲的太清晰了，地址：LeetCode刷题力扣题解 | 剑指Offer 43. 1～n 整数中 1 出现的次数 。
具体思路为，求该数字的每个位置，假定该位置为1，可以产生多少个数字。以图中3101595为例。分为三种情况：
1，那么左边部分a的可取值为0000~3101，也就是a+1个数字，而对于右半部分，因为cur大于1，当固定为1的时候，可取值为00~99，即base；1，那么左边部分a的取值可分为两种情况，当可取值范围为000~309，即a，右边部分可取值为base，当a取值为310时候，右边部分可取值为b+1；0，那么当我们假定当前位置取1，那么左边部分可取值为a，右半部分可取值为base；class Solution {
public int countDigitOne(int n) {
int low = 0, cur = n % 10, high = n / 10;
int count = 0, digit = 1;
while(digit <= n){
if(cur > 1) count += (high + 1) * digit;
else if(cur == 1) count += high * digit + low + 1;
else count += high * digit;
low += cur * digit;
cur = high % 10;
high = high / 10;
digit *= 10;
}
return count;
}
}
