当前位置：首页 > news >正文

LeetCode 233：数字 1 的个数

news 2025/7/26 15:32:55

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（覆盖所有位）：

计算高位、当前位、低位：
- div = mod × 10（用于提取高位）。
- high = n / div（当前位左侧的数字）。
- cur = (n / mod) % 10（当前位的数字）。
- low = n % mod（当前位右侧的数字）。
根据 cur 计算贡献：
- 若 cur < 1：贡献为 high × mod。
- 若 cur == 1：贡献为 high × mod + low + 1。
- 若 cur > 1：贡献为 (high + 1) × mod。
累加贡献并更新权值：
- 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;}
}

关键细节解析

溢出处理：
mod 可能达到 10^10（当 n=1e9 时，mod 最终为 1e10），用 long 存储避免整数溢出。
位分解逻辑：
- 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）。
示例验证：
- 示例 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，符合预期。