LeetCode 面试题 17.06. 2出现的次数
目录
题目描述
题意分析
统计闭区间
[0,n]内所有十进制表示中数字 2 出现的总次数。逐个枚举整数再拆位需要O(n log n)，n 大时不可接受。十进制每一位的贡献可以独立计算。对当前位权 factor（1、10、100……），把 n 分成：
high = n / (factor * 10)：当前位左侧；cur = (n / factor) % 10：当前位数字；low = n % factor：当前位右侧。完整的 0 到 9 循环中，当前位为 2 的数字恰好占 factor 个。high 表示已经走过多少个完整循环；cur 决定当前未完整循环还要不要补这一段。
解法：逐位统计十进制贡献
核心思路
对任意 factor，基础贡献都是
high * factor。
cur < 2：当前轮还没走到 2，贡献不增加；cur == 2：当前轮从该位为 2 且低位全 0，走到 n 的低位 low，共low+1个；cur > 2：当前轮已经完整经过当前位为 2 的整段，再加 factor。因而三种公式分别为
high*factor、high*factor+low+1、(high+1)*factor。逐位相加就是答案。例：n=25。个位 factor=1：high=2、cur=5，贡献 3（2、12、22）；十位 factor=10：high=0、cur=2、low=5，贡献 6（20 到 25）。总数为 9，注意 22 贡献了两个 2。
不变量是：处理完 factor 后，answer 已精确包含所有不高于该位的“2”贡献，不会重复，因为每个数字中的每个 2 只属于一个十进制位置。
解题步骤
- 用宽整数保存 n、factor 与 answer。
- factor 从 1 开始，每轮乘 10，直到超过 n。
- 计算 high、cur、low。
- 按 cur 与 2 的关系累加当前位贡献。
- 返回累加结果；n=0 时循环不进入，答案为 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)，每个十进制位只处理一次。- 空间复杂度：
O(1)，只使用若干宽整数变量。
关键点总结
- 把“枚举所有数字”换成“按十进制位置统计”，复杂度从与 n 相关降到与位数相关。
low+1中的加一代表低位从全 0 到 low 的闭区间，最容易漏。- 22 含两个 2，会在个位和十位各统计一次，这正是逐位独立求和的含义。
- 面试追问通常会把目标数字从 2 改成任意
d∈[1,9]，只需把三分支阈值 2 替换成 d；统计 0 时要额外排除前导零，不能直接照搬。
易错点总结
cur==2分支漏掉+1：n=25 时十位只算 5 个，漏掉 20，返回 8 而正确答案是 9。cur>2仍用high*factor：n=25 的个位会漏掉 22，个位贡献错算成 2。- low 写成
n%(factor*10)：把当前位也混进低位。n=25、十位会得到 low=25，贡献严重偏大。- 范围误写成
[0,n)：n=2 会返回 0，题目闭区间的正确答案是 1。- 用 int 计算
factor*10：接近整型上界时可能溢出，high 随之错误；中间量应使用 long/int64。- 直接枚举 0 到 n：n 达到十亿时需要十亿轮，面试中即使逻辑正确也无法接受。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 233. 数字 1 的个数 | 困难 | 同一套逐位贡献公式，目标数字为 1 |
| 剑指 Offer 43. 1～n 整数中 1 出现的次数 | 困难 | 数位统计同题 |
| 788. 旋转数字 | 中等 | 数位 DP 的另一类计数条件 |