力扣233题解：数学推导与位运算优化——高效统计数字中1的个数

一、题目解读

力扣233题要求计算给定整数n中数字“1”出现的总次数。例如，n=13时，1~13中包含“1”的数字有1、10、11、12、13，共5个。题目需高效求解，避免暴力遍历所有数字，需寻找数学规律或算法优化。

二、解题思路

采用数学推导结合位运算的优化策略。核心思想是将数字n拆分为不同位（个位、十位、百位等），通过公式计算每一位的“1”的个数，最后累加。关键在于：

1. 循环从最低位（个位）开始，每次乘以10递增位阶；

2. 利用除法与取余操作，将n拆分为高位、当前位和低位；

3. 推导当前位对“1”的贡献公式：考虑高位是否为0、当前位是否为1，以及低位的影响；

4. 通过min和max函数处理边界情况，避免溢出或重复计算。

三、解题步骤

1. 初始化计数器count为0，循环变量i从1开始逐位递增（i *= 10）。

2. 计算当前位的分隔值divider = i * 10（如个位时divider=10，十位时divider=100）。

3. 拆分n：

○ 高位部分：n / divider（如n=12345，十位时高位为12）；

○ 当前位值：i（当前位阶，如10）；

○ 低位部分：n % divider（如n=12345，十位时低位为345）。

4. 计算当前位“1”的个数：

○ 若高位为0，当前位从1到i的贡献为i；

○ 若高位不为0，需结合低位计算：如n=12345（当前位为十位），若当前位为1，则贡献为高位12 * 10 + 低位345中1的个数；若当前位为2，则贡献为高位12 * 10 + 10（即11~19）。

○ 使用公式：(n / divider) * i + min(max(n % divider - i + 1, 0LL), i) 综合以上情况。

5. 累加各位置计算结果，最终返回count。

四、代码与注释

class Solution {
public:
    int countDigitOne(int n) {
        int count = 0;
        // 从个位开始逐位计算1出现的次数
        for (long long i = 1; i <= n; i *= 10) {
            // 当前位、高位和低位
            long long divider = i * 10;
            count += (n / divider) * i + min(max(n % divider - i + 1, 0LL), i);
        }
        return count;
    }
};

注释说明：

● i *= 10：循环变量按位阶递增，遍历个位、十位、百位等；

● divider = i * 10：计算当前位的分隔值，用于拆分n；

● 公式 (n / divider) * i：计算高位对当前位“1”的贡献（如高位为x，则x个完整当前位段）；

● min(max(n % divider - i + 1, 0LL), i)：处理当前位及低位的贡献，避免溢出或重复计算（如当前位为1时，低位需从0开始；当前位>1时，贡献固定为i）。

五、总结

本文通过数学推导与位运算，将数字拆分为多段计算“1”的个数，避免了暴力遍历。核心在于利用除法与取余操作定位位阶，结合公式精准计算每一位的贡献。算法时间复杂度O(log n)，空间复杂度O(1)，为高效统计问题的典型解法，适用于大范围整数场景。