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

难度: 🌕🌕🌗

问题描述

---

解法

class Solution {
    public int countDigitOne(int n) {
        // 思路：
        // 找规律
        // 从个位开始依次计算 给定数 在该位出现 1 的个数，累加
        // 当前位 1 的出现次数，取决于 当前位的值 & 当前位是多少位 & 低位的值
        // 例：6017，依次计算 个位 --> 十位 --> 百位 --> 千位
        // 个位：cur = 7 --> 602
        // 十位：cur = 1 --> 600 + 8
        // 百位：cur = 0 --> 600
        // 千位：cur = 6 --> 1000

        int cur = n % 10; // 当前位的值，初始为 个位
        int high = n / 10; // 高位的情况数，初始为 有多少个 10 
        int low = 0; // 低位的值，初始为 0
        int digit = 1; // 当前位为 10 的多少次方
        int res = 0;

        while(high != 0 || cur != 0) {
            if(cur > 1) {
                // 高位变化范围为 [0, high]
                // 低位变化范围为 [0, digit - 1] 即全部变化范围
                res += (high + 1) * digit;
            } else if(cur == 1) {
                // 高位变化范围为 [0, high - 1] + 低位无限制
                // 再加上
                // 高位固定为 high + 低位变化范围为 [0, low]
                res += high * digit;
                res += low + 1;
            } else {
                // 高位变化范围为 [0, high - 1] + 低位无限制
                res += high * digit;
            }
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
}

---

输出