LeetCode 剑指 Offer 43. 1～n 整数中 1 出现的次数
题目描述
题意分析
统计从
1到n的所有整数中，十进制数码1总共出现多少次。同一个整数若在多个位置含有一，每个位置都分别计数；不是只统计有多少个整数包含一。题目范围为
0 <= n < 10^9，n = 0时答案为零。逐个整数转换并统计需要处理接近n个数，需要改为直接计算每个十进制位置对答案的贡献。
解法：按十进制位统计贡献
核心思路
[!blue]
固定一个位权
digit，依次取一、十、一百等。将上界拆为high、cur、low三部分：high = n / (digit * 10)是当前位左侧数字，cur = n / digit % 10是当前位，low = n % digit是右侧数字。先统计高位部分小于
high的情况。高位可以取零到high-1，每一种都可以让当前位固定为一，而低位从零到digit-1自由变化，共有digit种。因此这部分贡献统一为high * digit。再考虑高位恰好等于
high的最后一段：若cur == 0，把当前位换成一已经超过n，没有新增；若cur == 1，低位只能取零到low，新增low + 1；若cur > 1，当前位取一后整体已经小于上界，低位可取满全部digit种。这三种情况与代码分支一一对应。前面的高位允许用零补齐，仅用于统一计数；统计的是数码一，补出的前导零不会贡献答案。每个实际出现的一只属于某个具体数位，将所有位的贡献相加即可。
位权、乘法及累计过程使用 64 位整数，避免
digit * 10的中间计算溢出；最终在本题范围内返回整数结果。
解题步骤
- 将答案初始化为零，从
digit = 1开始。- 用除法和取余拆出当前位的
high、cur、low。cur == 0时累加high * digit；等于一时再加low + 1；大于一时再加digit。- 将位权乘十，直到位权超过
n，返回总计数。
代码实现
class Solution {
public int countDigitOne(int n) {
long number = n;
long answer = 0;
for (long digit = 1; digit <= number; digit *= 10) {
long high = number / (digit * 10);
long cur = number / digit % 10;
long low = number % digit;
if (cur == 0) {
answer += high * digit;
} else if (cur == 1) {
// 当前位等于一时，最后周期的低位从零到 low 都可选。
answer += high * digit + low + 1;
} else {
answer += (high + 1) * digit;
}
}
return (int) answer;
}
}
func countDigitOne(n int) int {
number := int64(n)
var answer int64
for digit := int64(1); digit <= number; digit *= 10 {
high := number / (digit * 10)
cur := number / digit % 10
low := number % digit
if cur == 0 {
answer += high * digit
} else if cur == 1 {
// 当前位等于一时，最后周期的低位从零到 low 都可选。
answer += high*digit + low + 1
} else {
answer += (high + 1) * digit
}
}
return int(answer)
}
复杂度分析
- 时间复杂度：$O(\log(n+1))$，只遍历十进制数位，每一位做常数次算术运算。
- 空间复杂度：$O(1)$，保存固定数量的整数变量。
关键点总结
[!green]
- 改为按数位统计，就不再需要枚举每个整数。
- 小于上界高位的部分可完整计数，只有高位相同时才受当前位、低位限制。
- 当前位等于一时，低位从零开始，因此合法取值数是
low + 1。- 多个位置的一分别贡献，将各位求和正好得到总出现次数。
易错点总结
[!yellow]
- 低位应为
n % digit，取模digit * 10会把当前位也包含进去。cur == 1时只加low会漏掉低位全零的情况。- 不能以
high != 0决定是否继续，最高位左侧虽为空，最高位本身仍可能贡献。- 不应给不足当前位长度的数补入一；补零仅用于表示，实际贡献已由三分支正确限制。
- 只把答案声明为宽整数还不够，位权及乘法也需要在宽整数类型中执行。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 17.06. 2出现的次数 | 困难 | 同样按high/current/low计算每个十进制位置贡献，目标数码从1换成2。 |
| 902. 最大为 N 的数字组合 | 困难 | 同样按数位分块计数以避免逐个枚举，本题累计某个数码的出现次数，原题统计合法整数个数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！