LeetCode 233. 数字 1 的个数

约 4 分钟
文章信息 11 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 10-20 字节跳动 微软 阿里巴巴 快手 腾讯 旷视
标签
动态规划 数学 递归
目录

题目描述

✅ 233. 数字 1 的个数

题意分析

要数的是 0 到 n 这些整数写成十进制之后，字符 1 一共出现了多少次。注意统计的是出现次数而不是含 1 的数的个数：11 里有两个 1，要算两次；范围是闭区间，n 自己也要算进去。

约束信号：$0 \le n \le 10^9$。这个上界几乎是明示——逐个数字拆位要跑 $10^9$ 次循环、约 $10^{10}$ 次取模，肯定超时，所以必须找到一种只跟 n 的位数有关的算法，也就是 $O(\log n)$ 级别。

边界有三处：n = 0 时答案是 0；n = 1 时答案是 1；n 恰好是 $10^9$ 这种最高位为 1 的数时，最高位的贡献要单独算清楚，不能想当然。

解法：按十进制位贡献统计

核心思路

暴力逐个拆数需要 $O(n \log n)$，而十进制位数只有 $O(\log n)$。因此改为逐位统计：分别计算个位、十位、百位等位置出现 1 的次数，再把各位贡献相加。

对位权 factor，把 n 分成 high、cur、low 三部分：

  • high = n / (factor * 10)：当前位左侧；
  • cur = (n / factor) % 10：当前位；
  • low = n % factor：当前位右侧。

完整的高位周期贡献 high * factor 次。若 cur == 0，没有额外贡献；若 cur == 1，低位可以从 0 取到 low，额外贡献 low + 1；若 cur > 1，低位的 factor 种取值全部有效，额外贡献 factor。

每个数字中的每个 1 只属于一个十进制位置，因此逐位累加既不重不漏。

解题步骤

  1. 使用 64 位整数保存 factor 和答案，避免 factor * 10 溢出。
  2. 从 factor = 1 开始，每轮拆出 high、cur、low。
  3. 按 cur 为 0、1、大于 1 三种情况累加当前位贡献。
  4. factor *= 10 进入更高位，直到 factor > n。

例如 n = 13：个位 cur = 3，贡献 2（1、11）；十位 cur = 1，贡献 4（10、11、12、13），总计 6。

代码实现

class Solution {
    public int countDigitOne(int n) {
        long factor = 1;
        long ans = 0;
        while (factor <= n) {
            long high = n / (factor * 10);
            long cur = (n / factor) % 10;
            long low = n % factor;

            if (cur == 0) {
                ans += high * factor;
            } else if (cur == 1) {
                ans += high * factor + low + 1;
            } else {
                ans += (high + 1) * factor;
            }
            factor *= 10;
        }
        return (int) ans;
    }
}

func countDigitOne(n int) int {
    factor := int64(1)
    limit := int64(n)
    ans := int64(0)
    for factor <= limit {
        high := limit / (factor * 10)
        cur := (limit / factor) % 10
        low := limit % factor

        if cur == 0 {
            ans += high * factor
        } else if cur == 1 {
            ans += high*factor + low + 1
        } else {
            ans += (high + 1) * factor
        }
        factor *= 10
    }
    return int(ans)
}

复杂度分析

  • 时间复杂度：$O(\log n)$，每个十进制位只处理一次。
  • 空间复杂度：$O(1)$，只使用固定数量的整数变量。

关键点总结

  • 从“枚举数字”转成“统计每一位的贡献”，是把复杂度降到对数级的关键。
  • 三个分支的区别只在高位取到 high 时，当前位 1 是否超过上界。
  • cur == 1 时的 low + 1 包含低位全为 0 的情况。
  • 中间计算使用 64 位整数；区间查询可进一步用前缀差 f(right) - f(left - 1)。

易错点总结

  • 循环条件应为 factor <= n；否则 n = 100 时会漏掉百位。
  • cur == 1 时不要漏掉 +1，它表示低位取 0 也合法。
  • cur 必须对 10 取模，low 必须对 factor 取模，三段边界不能混淆。
  • 用 32 位整数计算 factor * 10 可能溢出，应先提升为 64 位。

相似题目

题目 难度 考察点
剑指 Offer 43. 1～n 整数中 1 出现的次数 困难 同款按位公式的剑指版
面试题 17.06. 2出现的次数 困难 换成统计数字 2
357. 统计各位数字都不同的数字个数 中等 数位上的排列组合计数
201. 数字范围按位与 中等 区间上的逐位分析
172. 阶乘后的零 中等 按因子幂次逐层累加