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.

例子

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