面试题43. 1～n整数中1出现的次数

题目：

面试题43. 1～n整数中1出现的次数
233. 数字 1 的个数

题解：

代码：

public class 面试题43 {

    public static int countDigitOne(int n) {
        int digit = 1; // 位因子(初始化为：个位)
        int high = n / 10; // 高位
        int cur = n % 10; // 当前位
        int low = 0; // 低位

        int res = 0; // 统计最终的结果

        while(high !=0 || cur != 0) // 当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出
        {
            // 当 cur = 0 时： 此位 1 的出现次数只由高位 high 决定，
            // 计算公式为：high * digit
            if(cur == 0)
            {
                res += high * digit;
            }
            // 当 cur = 1 时： 此位 1 的出现次数由高位 high 和低位 low 决定，
            // 计算公式为：high * digit + low + 1
            else if(cur == 1)
            {
                res += high * digit + low + 1;
            }
            // 当 cur = 2, 3, ⋯, 9 时： 此位 1 的出现次数只由高位 high 决定，
            // 计算公式为：(high + 1) * digit
            else if(cur >= 2 && cur <= 9)
            {
                res += (high + 1) * digit;
            }

            low += cur * digit; // 将 cur 加入 low ，组成下轮 low
            cur = high % 10; // 下轮 cur 是本轮 high 的最低位
            high /= 10; // 将本轮 high 最低位删除，得到下轮 high
            digit *= 10; // 位因子每轮 × 10
        }
        return res;
    }

    public static void main(String[] args) {
        int res = countDigitOne(32104);
        System.out.println(res); // res == 23626
    }
}

参考：

1. 面试题43. 1～n 整数中 1 出现的次数（清晰图解）
2. java递归
3. C++ 从个位遍历到最高位依次求解
4. java 递归求解
5. 数字 1 的个数
6. 详细通俗的思路分析，多解法