LeetCode 233：数字 1 的个数

LeetCode 233：数字 1 的个数

问题本质：统计数字规律

给定整数 n，计算 [0, n] 中所有整数里数字 1 出现的总次数。直接暴力遍历每个数统计会超时（n 可达 10^9），需通过数学规律逐位分析。

核心思路：逐位贡献计算

对于数字 n 的每一位，分析该位上 1 出现的次数，最终累加所有位的结果。

关键观察：

将数字拆分为 高位（high）、当前位（cur）、低位（low），根据 cur 的值分三种情况计算该位的贡献：

• 情况 1：cur < 1：该位的 1 由高位决定，贡献为 high × 10^pos（pos 是当前位的权值，如个位 pos=1，十位 pos=10）。
• 情况 2：cur == 1：贡献为 high × 10^pos + low + 1（高位决定基础部分，低位补充剩余情况）。
• 情况 3：cur > 1：贡献为 (high + 1) × 10^pos（高位加1，覆盖当前位为 1 的所有可能）。

算法步骤详解

步骤 1：初始化变量

• ans：记录最终结果，初始为 0。
• mod：当前位的权值（如个位 mod=1，十位 mod=10，依次递增），初始为 1。

步骤 2：逐位处理

循环处理每一位，直到 mod > n（覆盖所有位）：

1. 计算高位、当前位、低位：

   • div = mod × 10（用于提取高位）。
   • high = n / div（当前位左侧的数字）。
   • cur = (n / mod) % 10（当前位的数字）。
   • low = n % mod（当前位右侧的数字）。

2. 根据 cur 计算贡献：

   • 若 cur < 1：贡献为 high × mod。
   • 若 cur == 1：贡献为 high × mod + low + 1。
   • 若 cur > 1：贡献为 (high + 1) × mod。

3. 累加贡献并更新权值：

   • ans += 贡献。
   • mod *= 10（处理下一位，如从个位→十位→百位）。

完整代码（Java）

class Solution {
    public int countDigitOne(int n) {
        int ans = 0;
        long mod = 1; // 用long防止溢出（n≤1e9，mod最大为1e10，int会溢出）
        while (mod <= n) {
            long div = mod * 10;
            long high = n / div;
            long cur = (n / mod) % 10;
            long low = n % mod;
            
            if (cur < 1) {
                ans += high * mod;
            } else if (cur == 1) {
                ans += high * mod + low + 1;
            } else {
                ans += (high + 1) * mod;
            }
            
            mod *= 10;
        }
        return ans;
    }
}

关键细节解析

1. 溢出处理：
   mod 可能达到 10^10（当 n=1e9 时，mod 最终为 1e10），用 long 存储避免整数溢出。

2. 位分解逻辑：

   • div 是 mod 的 10 倍，用于隔离高位（如 n=1234，mod=10 时，div=100，high=12）。
   • cur 通过 (n / mod) % 10 提取（如 mod=10 时，1234 / 10 = 123，123 % 10 = 3，即十位的 3）。
   • low 通过 n % mod 提取（如 mod=10 时，1234 % 10 = 4，即个位的 4）。

3. 示例验证：

   • 示例 1（n=13）：
     • 个位（mod=1）：cur=3>1，贡献 (1+1)×1=2（数字 1、11 的个位 1）。
     • 十位（mod=10）：cur=1，贡献 0×10 + 3 + 1=4（数字 10、11、12、13 的十位 1）。
     • 总和 2+4=6，符合预期。

复杂度分析

• 时间复杂度：O(log n)，仅需遍历 n 的位数（最多 10 位，10^9 是 10 位数）。
• 空间复杂度：O(1)，仅用常数变量存储中间结果。

该方法通过数学规律逐位拆解，避免了暴力遍历的高复杂度，高效解决了大范围数字的统计问题，是处理“数字规律”类题目的经典思路。