LeetCode-剑指43-1-n整数中出现1的次数

1、逐位统计

我们统计每一位k上面可能出现1的次数：1、对于每一位k上面的出现的1，我们首先统计其出现$(n/10^k)\times 10^{k-1}$次的1；2、考虑到存在余数的情况，我们还需要比较剩余余数中出现1的次数，为$(n\%10^k)-10^{k-1}+1$，当其小于0时我们将其置为0，当其大于$10^{k-1}$时将其置为$10^{k-1}$。最终我们逐位统计即可获得每一位上出现1的次数。

class Solution {
public:
    int countDigitOne(int n) {
        long long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; ++k) {
            ans += (n / (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0LL), mulk);
            mulk *= 10;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12