给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

**输入：**n = 13
**输出：**6

示例 2：

**输入：**n = 0
**输出：**0

提示：

0 <= n <= 10(9)

对每个数字依次统计不现实，只能对每位进行枚举，即个位十位百位。。。

对于n，每位出现的数字分为0，1，大于1三种情况

cur表示当前位，high表示高位，low表示低位，digit表示cur的10^k

当cur==0时，我们要假设此位为1，此时需要借位，low的每一位都可以为0-9即每一个高位都有digit中情况，高位直接枚举即可，此时res要加high*digit（例如高位是20，可以枚举0-20共21种情况，但是因为借位了所以还是只有20种情况）

当cur==1时，此位为1，我们假设还借位（即高位先减一），此时加上high*digit，假设不借位，此时低位枚举从0到low共low+1种，两部分共high*digit+low+1

当cur>1时，高位直接枚举（high+1）种，低位因为可以向cur借位所以直接枚举0-9共（high+1）*digit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public : int countDigitOne(int n) {
        long digit = 1;
        long high = n / 10, cur = n % 10, low = 0, res = 0;
        while (n / digit != 0) {
            if (cur == 0) {
                res += high * digit;
            } else if (cur == 1) {
                res += high * digit + low + 1;
            } else {
                res += (high + 1) * digit;
            }
            low += cur * digit;
            digit *= 10;
            cur = high % 10;
            high /= 10;
        }
        return res;
    }
};