剑指 Offer 43. 1～n 整数中 1 出现的次数

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

输入：n = 12
输出：5

输入：n = 13
输出：6

解题思路：

设数字n是一个x位数，可以表示为
$$
n{x}n{x-1}…n{2}n{1}
$$
将ni设置为当前位，ni-1 ni-2 … n2 n1设置为低位low

nx nx-1 … ni+2 ni+1称为高位high

10i为位因子

• cur == 0时：1的出现次数为high * digit
• cur == 1时：1的出现次数为high * digit + low + 1
• else：(high + 1) * digit

那么各个位初始化为：

high = n // 10
cur = n % 10
low = 0
digit = 1 # 个位

AC代码

class Solution {
public:
    int countDigitOne(int n) {
        long digit = 1,res = 0;
        int high = n / 10;
        int low = 0;
        int cur = n % 10;
        while (high != 0 || cur != 0){
            if(cur == 0)    res += digit * high;
            else if(cur == 1)   res += digit * high + low + 1;
            else res += (high + 1) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
};