Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example: Given n = 13, Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
给一个数，计算不超过这个数的所有正数中，1出现的次数。
一开始的想法，分段计算 0-9，10-99，100-999......除了个位，每一段1出现的次数 = 数字总数 * k - k * 8*9^(k - 1)，k为位数，即用这一段所有数字的总和减去不使用1构成的数字的个数乘上位数，这种想法太不简洁。
优美解法：枚举不超过n的每一位，对每一位1出现的次数进行统计。
参考这里：https://discuss.leetcode.com/topic/18054/4-lines-o-log-n-c-java-python
以算百位上1为例子:
假设百位上是0, 1, 和 >=2 三种情况:
case 1: n=3141092, a= 31410, b=92. 计算百位上1的个数应该为 3141 *100 次.
case 2: n=3141192, a= 31411, b=92. 计算百位上1的个数应该为 3141 *100 (92 1) 次.
case 3: n=3141592, a= 31415, b=92. 计算百位上1的个数应该为 (3141 1) *100 次.
所以可以将每一位归纳成这样一个公式：
(a 8) / 10 * m (a % 10 == 1) * (b 1)
需要注意的坑，虽然最终结果不会超过int范围，但是因为中间计算涉及乘法，所以会出现溢出，需要用long long存储中间变量。
代码语言：javascript复制class Solution {
public:
int countDigitOne(int n) {
int res = 0;
for(long long i = 1; i <= n ; i *= 10)
{
int pre = n / i;
int suf = n % i;
long long temp = (pre 8) / 10 * i;
if(pre % 10 == 1) temp = suf 1;
res = temp;
}
return res;
}
};
