问题
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
例子
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
分析
详见页码统计。
举一个简单的例子，求0-5137这5138个数字中出现1的个数，就等价于求1在个位、十位、百位、千位出现的个数的总和。现考虑1在百位出现的个数。简单地枚举一下，有100-199,1100-1199,2100-2199,...,5100-5137总共500+37=537个；如果求0-5037出现1的个数，有100-199,1100-1199,2100-2199,...,4100-4199总共500个；如果求0-5237出现1的个数，有100-199,1100-1199,2100-2199,...,5100-5199总共600个。
可以得出结论，对应一个数AbC，b是一个0-9的数字，0-AdC中出现在b位置上的1的个数和b的大小有关：
- b=0，个数为A*10^C的位数；
- b=1，个数为A*10^C的位数 + C；
- b>1，个数为(A+1)*10^C的位数。
知道了这个规律，依次求出每位上1的个数加起来就是总结果了。
要点
多写写画画找找规律。
时间复杂度
O(n)，n是数字的位数
空间复杂度
O(1)
代码
class Solution {
public:
int countDigitOne(int n) {
if (n <= 0) return 0;
long long cnt = 0;
for (long long i = 1, j; j = n / i; i *= 10) {
long long high = j / 10;
long long low = n - j * i;
long long digit = j % 10;
cnt += high * i;
if (digit > 1)
cnt += i;
else if (digit == 1)
cnt += low + 1;
}
return cnt;
}
};
