LeetCode 233. 数字 1 的个数
题目描述
题意分析
统计从
0到n的所有非负整数中，十进制数字1一共出现多少次。统计对象是每一次数位出现，同一个数里不同位置出现的1都要分别计入，不能只统计有多少个数包含1。上界
n本身也在统计范围内。n = 0时没有任何1，结果为零。逐个展开所有整数会遍历很大的范围，可以改为分别计算个位、十位等每个位置的贡献，再相加。
解法：按十进制位贡献统计
核心思路
[!blue]
固定当前数位的位权
factor，它依次取1、10、100…。把上界拆成三段：high = n / (factor * 10)是当前位左侧的高位，cur = n / factor % 10是当前位，low = n % factor是右侧低位。它们满足n = high * (factor * 10) + cur * factor + low。现在只统计当前位等于
1的数。当高位小于high时，无论低位怎样取值，整个数都小于上界。高位有high种选择，每种选择下，低位可以从0取到factor - 1，一共factor种，因此先得到固定贡献high * factor。剩下只需看高位恰好等于
high的最后一段。如果cur == 0，把当前位置成1就已经超过上界，没有额外贡献；如果cur == 1，低位只能从0到low，贡献low + 1；如果cur > 1，当前位置成1后已经小于上界，低位可以任意取值，再贡献完整的factor种。对每个位置独立执行上述统计并累加。一个整数中的每次
1都有唯一的位置，所以不会重复计数，也不会漏掉同一个整数在多个位置上的贡献。最高位之前补出的零不会产生新的1，因此高位从零开始枚举不影响统计。位权每轮乘十，直到超过
n，说明更高位置已经不可能出现1。factor * 10等中间计算使用 64 位整数，避免最高位计算时先发生溢出；在题目给定的n <= 10^9范围内，最终结果可以按接口返回整数。
解题步骤
- 使用 64 位整数初始化
factor = 1、ans = 0。- 只要
factor <= n，就计算当前位对应的high、cur、low。cur == 0时加入high * factor；cur == 1时加入high * factor + low + 1；cur > 1时加入(high + 1) * factor。- 将位权乘十，继续处理更高一位。
- 所有数位统计完后返回答案；
n = 0时循环不执行，直接得到零。
代码实现
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) {
// 当前位恰为一，末轮低位从零到 low，共有 low 加一种。
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 {
// 当前位恰为一，末轮低位从零到 low，共有 low 加一种。
ans += high*factor + low + 1
} else {
ans += (high + 1) * factor
}
factor *= 10
}
return int(ans)
}
复杂度分析
- 时间复杂度：$O(\log(n + 1))$，每个十进制数位只做常数次拆分和计数；
n = 0时为常数操作。- 空间复杂度：$O(1)$，只保存位权、三段数值和累计答案。
关键点总结
[!green]
- 从枚举整数改为枚举数位，逐位累加出现次数。
- 高位小于上界对应的部分已经完整出现，贡献统一为
high * factor。- 高位相同时，当前位决定低位取值是不可选、部分可选还是全部可选。
low + 1中的一对应低位取零，不能因为从零计数而漏掉它。
易错点总结
[!yellow]
- 把每个含
1的整数只计一次，会漏掉同一整数的其他数位贡献。- 位权循环使用
factor < n，会在上界恰好等于某个位权时漏掉最高位。- 当前位为
1时只加low，会遗漏低位全部取零的合法数字。- 混淆取模边界：当前位对
10取模，低位对factor取模，高位则需要除以factor * 10。- 用窄整数先计算位权乘十，再赋给宽整数，不能避免乘法已经发生的溢出；位权本身应使用 64 位类型。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 17.06. 2出现的次数 | 困难 | 同样按high/current/low计算每个十进制位置贡献，目标数码从1换成2。 |
| 902. 最大为 N 的数字组合 | 困难 | 同样按数位分块计数以避免逐个枚举，本题累计某个数码的出现次数，原题统计合法整数个数。 |