LeetCode 剑指 Offer 43. 1～n 整数中 1 出现的次数
目录
题目描述
题意分析
给定一个整数
n，把 1、2 一直数到n，统计这些数写成十进制后一共出现了多少个字符 1。注意数的是字符出现次数而不是含 1 的数的个数：11 里有两个 1，要计 2 次，不是 1 次。这一句读错，整道题的口径就全偏了。当前力扣页面已迁移为 LCR 162，约束是
0 <= n < 10^9；旧版 Offer 43 的常见题面则写作n < 2^31。无论采用哪个版本，逐个数再逐位统计的 $O(n \log n)$ 做法都会超时，必须把统计维度从「第几个数」换成「第几位」，循环次数才能降到十进制位数。换维度之所以合法，是因为「1 的总个数」天然可以拆开算：每个 1 都恰好属于某个数的某一位，把每一位上出现 1 的次数分别数清楚再相加，既不重也不漏。于是问题变成十个彼此独立的子问题——个位上一共有多少个 1、十位上一共有多少个 1、依此类推。
为兼容旧题面的上限，位权和累加器都应使用 64 位：位权从 $10^9$ 再乘 10 会得到 $10^{10}$。还要区分结果范围：当前约束下最大结果为 900000000，平台的
int返回值足够；若按旧上限取n = 2147483647，精确结果是 2971027783，已经超过Integer.MAX_VALUE，通用接口应改用long。边界情形：
n = 0时区间为空，答案是 0；n = 1时答案是 1；只含一位的n也必须被统计到，不能因为高位是 0 就提前退出循环。
解法：按十进制位统计贡献
核心思路
逐个枚举 1 到
n的复杂度过高。固定某个十进制位，直接统计这一位在所有数中出现 1 的次数，再把各位贡献相加。设当前位权为
digit，把n拆成：
high = n / (digit * 10)：当前位左侧的高位部分；cur = n / digit % 10：当前位数字；low = n % digit：当前位右侧的低位部分。每个完整的
0～9周期中，当前位为 1 的区间长度都是digit，完整周期贡献high * digit。最后一个不完整周期由cur决定：
cur == 0：没有额外贡献；cur == 1：低位可取0～low，额外贡献low + 1；cur > 1：当前位为 1 的整段都已出现，额外贡献digit。循环不变量是：处理完某个位权后，
answer等于已经处理的所有数位上字符 1 的总贡献。每个 1 只属于一个数位，因此求和不重不漏。
解题步骤
- 从个位开始，令
digit = 1。- 每轮根据
digit拆出high、cur、low。- 按
cur为 0、1、大于 1 三种情况累加当前位贡献。- 令
digit *= 10，继续处理更高一位，直到位权超过n。以
n = 13为例：个位cur = 3，贡献 2（1、11）；十位cur = 1，贡献low + 1 = 4（10～13），总计 6。
代码实现
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) {
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 {
answer += high*digit + low + 1
} else {
answer += (high + 1) * digit
}
}
return int(answer)
}
复杂度分析
- 时间复杂度：$O(\log n)$。循环次数等于
n的十进制位数。- 空间复杂度：$O(1)$。只使用固定数量的整数变量。
关键点总结
- 从“逐个数统计”切换到“固定数位统计”，把规模从
n降到十进制位数。high * digit是完整周期贡献，三种分支只处理最后一个不完整周期。cur == 1时必须加low + 1，因为低位从 0 开始也对应一个合法数字。digit、乘法中间量和累加器都应使用 64 位整数，避免位权乘 10 时溢出。
易错点总结
- 把
low写成n % (digit * 10)，会把当前位也错误地包含进去。cur == 1时漏掉+1，会少统计低位全为 0 的那个数。- 以
high != 0作为循环条件会漏掉最高位，n = 1时甚至一轮都不执行。- 使用 32 位
digit，处理到十亿位后再乘 10 会溢出并破坏循环。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 233. 数字 1 的个数 | 困难 | 与本题完全同构的英文版，可直接套用同一份三分类公式，适合用来验证记忆 |
| 面试题 17.06. 2出现的次数 | 困难 | 目标数字换成 2，cur == 2 的分支不再有 low + 1，分类边界随之左移 |
| 902. 最大为 N 的数字组合 | 困难 | 可用数字受给定集合限制，靠公式凑不出来，必须上「是否贴合上界」的数位递推 |