Leetcode 233. Number of Digit One

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存储中间变量。

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;
    }
};