LeetCode 面试题 17.06. 2出现的次数

约 4 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 困难 程序员面试金典（第 6 版）
标签
动态规划 数学 递归

题目描述

✅ 面试题 17.06. 2出现的次数

image-20260929010445216

题意分析

统计闭区间 [0, n] 中，所有整数的十进制表示一共出现多少个数字 2。一个整数若有多个位置是 2，需要分别计数。可以把总次数拆成各个十进制位置的贡献，避免逐个枚举整数。

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

核心思路

[!blue]

固定当前位权 factor，它依次为 1、10、100 等。将 n 拆成三部分：high = n / (factor * 10) 是当前位左侧的高位，current = (n / factor) % 10 是当前数字，low = n % factor 是右侧低位。

随着整数从 0 增加，当前位每经过 10 * factor 个数就完成一个周期。在每个完整周期中，当前位等于 2 时，低位可以从全零取到 factor - 1，恰好贡献 factor 次。n 所在周期之前有 high 个完整周期，先贡献 high * factor。

再看 n 所在的最后一个周期，是否已经经过当前位为 2 的那一段：

  • current < 2：还没走到这一段，没有额外贡献。
  • current == 2：已经走到这一段的低位 low，从 0 到 low 一共有 low + 1 个数。
  • current > 2：这一整段都已经过，再贡献 factor 次。

逐位累加这三种情况下的贡献即可。每一个出现的 2 都有唯一的十进制位置，因此不同位置的统计互不重复，合起来也不会遗漏。为了统一按周期计算，可以把较短整数看作前面补零；补出的只是零，不会产生额外的 2。

解题步骤

  • 用 long / int64 保存 limit、位权和累计答案。
  • 从 factor = 1 开始，每轮计算 high、current、low。
  • 按当前位小于、等于或大于 2，分别累加 high * factor、high * factor + low + 1、(high + 1) * factor。
  • 位权每轮乘 10，超过 n 后已处理所有可能出现 2 的位置，返回答案。
  • n = 0 时循环不执行，数字零本身不含 2，结果为 0。

代码实现

class Solution {
    public int numberOf2sInRange(int n) {
        long limit = n;
        long answer = 0;

        for (long factor = 1; factor <= limit; factor *= 10) {
            long high = limit / (factor * 10);
            long current = (limit / factor) % 10;
            long low = limit % factor;

            if (current < 2) {
                answer += high * factor;
            } else if (current == 2) {
                answer += high * factor + low + 1;
            } else {
                answer += (high + 1) * factor;
            }
        }

        return (int) answer;
    }
}

func numberOf2sInRange(n int) int {
    limit := int64(n)
    answer := int64(0)

    for factor := int64(1); factor <= limit; factor *= 10 {
        high := limit / (factor * 10)
        current := (limit / factor) % 10
        low := limit % factor

        if current < 2 {
            answer += high * factor
        } else if current == 2 {
            answer += high*factor + low + 1
        } else {
            answer += (high + 1) * factor
        }
    }

    return int(answer)
}

复杂度分析

  • 时间复杂度：$O(\log_{10}(n+1))$。每个十进制位只做常数次运算，n = 0 时直接结束。
  • 空间复杂度：$O(1)$。只保存当前位的几个宽整数状态。

关键点总结

[!green]

  • 高位决定已经经过的完整周期数，当前位和低位决定最后一个周期的贡献。
  • low + 1 来自包含两个端点的低位范围，不能漏掉低位全零的数。
  • 统计的是每个位置上的 2，不是“包含 2 的整数”数量。

易错点总结

[!yellow]

  • current == 2 时只加 low，会漏掉本段低位为零的第一个数。
  • current > 2 时必须多算完整的 factor 次，不能只保留基础贡献。
  • low 是 n % factor，用 n % (factor * 10) 会把当前位也混进去。
  • 题目范围包含 n，当前位恰好为 2 时必须把 n 自己计入。
  • factor * 10 也要在宽整数中计算，不能等乘法溢出后才转换类型。

相似题目

题目 难度 关联与区别
233. 数字 1 的个数 困难 同样按high/current/low分三种情况统计，只把目标数字1换成2。
400. 第 N 位数字 中等 同样利用十进制分块避免逐个枚举，原题按位数区间定位某一位数字。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/55745374
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！