题目
给定
n，统计
1 ~ n 所有整数中数字
1 出现的次数。
要求找规律，不要暴力。
输入: n = 13
输出: 6
解释: 1, 10, 11, 12, 13 里共有 6 个 1 ——
11 贡献两个，其余各一个。
这就是
LeetCode 233. Number of Digit One。看着像一道模拟题，
n 大起来之后暴力的代价是灾难级的：
n = 2147483647 时要逐个数检查约 21.5 亿个数、每个最多 10 个数位，合计约
2.15 × 10^10 次数位操作；而找对规律之后，不管
n 是 13 还是 21 亿，都只要
10 轮循环。
一、核心洞察：把「数 1」拆成「逐位统计」
暴力的做法是「对每个数，把它的每个数位都看一遍」。要找规律，先换个问法：
不要问「哪些数含有 1」，要问「每个数位上分别出现了多少个 1」。
这两件事的总和是一样的，但后者可以一个数位一个数位地算，而且
每个数位只由三个值决定：
以个位为例。
1 ~ n 里个位是 1 的数，是
1, 11, 21, 31, ... —— 每隔 10 个出现一个。所以：
- 完整的「十连」有
higher 个，每个十连贡献 1 个个位 1；
- 不满的末尾那一段，要看当前数位
cur 是不是已经走过了 1。
十位、百位、千位完全同理，只是把「每 10 个出现 1 个」换成「每 100 个连续出现 10 个」「每 1000 个连续出现 100 个」。
这个「连续几个」，就是该数位的权值 weight。 于是每个数位的账本都是同一句话：
把这句话翻译成代码，就是三件套：
higher（当前位之上）、
cur（当前位）、
lower（当前位之下）。
一句话总结：O(n) 的暴力是按「数」扫，O(log n) 的规律是按「数位」扫。 数位只有 10 个左右，这就是全部的提速来源。
二、找规律：从数轴上的 1 到三件套
先不碰公式。把
0 ~ 47 摆成网格（每行 10 个），一个一个数位看过去：
- 个位：每 10 个数循环一次，一个循环里个位为 1 的恰好 1 个 ——
1, 11, 21, 31, 41，是散点。0 ~ 47 里有 4 个完整十连（0-39）贡献 4 个，零头 40-47 里 41 踩线，再数出 1 个。个位合计 5。
- 十位：每 100 个数循环一次，一个循环里十位为 1 的恰好连续 10 个（
10-19）—— 是整块。0 ~ 47 里没有完整百块（0 个 × 10），但 10-19 这一整块都落在范围内，数出 10。
同一个
n = 47，两个数位合起来
15。注意个位和十位的「形状」完全不同（一个散点、一个整块），但
账本结构一模一样：完整循环数 × 每循环贡献 + 零头里那一截。
把这个账本翻译成公式，就是三件套。对权值为
weight 的数位（个位
weight = 1，十位
10，百位
100……），只看三个值：
higher = n / (weight * 10) 当前位之上的部分
cur = (n / weight) % 10 当前位
lower = n % weight 当前位之下的部分
higher 就是「完整循环数」，
weight 就是「每循环贡献」，零头怎么算看
cur：
完整代码（Python）：
def count_digit_one(n: int) -> int:
if n < 0:
raise ValueError("n 必须是非负整数")
total = 0
weight = 1 # 当前数位的权值：1、10、100……
# 注意是 <=：n 恰好是 10 的幂时，最高位那个数位也必须扫
while weight <= n:
higher = n // (weight * 10)
cur = (n // weight) % 10
lower = n % weight
if cur == 0:
total += higher * weight
elif cur == 1:
total += higher * weight + lower + 1
else:
total += (higher + 1) * weight
weight *= 10
return total
以
n = 13 走一遍：个位
higher = 1, cur = 3, lower = 0，走
cur > 1 分支，贡献
(1 + 1) × 1 = 2（数字 1 和 11）；十位
higher = 0, cur = 1, lower = 3，走
cur = 1 分支，贡献
0 × 10 + 3 + 1 = 4（10、11、12、13）。合计 6，和样例一致。
三、动画怎么看
动画一（n = 1304，10 帧） 演示公式怎么用。取 1304 做主例是因为它四个数位的
cur 分别是
4, 0, 3, 1 ——
三个分支刚好各走一次，看一遍等于看全所有情况。画面分五段：
- 横幅：当前数位（个位 · 权值 1）、本轮动作（拆三件套 / 走哪个分支）、数值（这一位的贡献）；
- 数位条：
n 的每个数字一格，橙 = 当前位，蓝 = 高于它，绿 = 低于它，和等式、卡片同色；
- 拆分等式：
1304 = 130 × 10 + 4 × 1 + 0 —— 三件套的算术长相，三个加数项分别着色；
- 三件套卡片 + 三分支表：卡片给
higher / cur / lower 的值，分支表三行（cur = 0 / 1 / > 1）对号入座，命中行烫金并给出代入结果，比如 (130 + 1) × 1 = 131；
- 累计 chips + 合计：每记完一位亮一个 chip，最后收在「合计 766」。
值得盯的两帧：
第 5 帧（十位，cur = 0） —— 当前块连 1 那一截的边都没碰到，只拿 13 个完整百块的 130 个；
第 9 帧（千位，cur = 1） —— 全程唯一一次
cur = 1，
0 × 1000 + 304 + 1 = 305，
+1 就加在这个地方，也是这题最容易漏的一项。
动画二（n = 47，6 帧） 演示公式从哪来，就是第二节那个数轴：个位帧里
1, 11, 21, 31, 41 五个烫金散点，十位帧里
10-19 一整条烫金块 —— 同一个网格、两种形状，对照着看，「完整循环 × 每循环贡献 + 零头」这句话为什么对两种形状同时成立，一目了然。账本面板会把每个数位算成三行：完整循环几个 × 每个多少、零头数出几个、本位合计。
四、完整推演表
主例
n = 1304，四个数位全部扫完：
官方样例
n = 13：
两个答案都用「逐个数数 '1'」的暴力解校验过：
1 ~ 1304 里确实有 766 个数字 1，
1 ~ 13 里确实有 6 个。
五、变体：换数字、数 0、递归版
换成数别的数字（2-9）：公式一个字都不用改结构，只把比较对象从 1 换成
d：
def count_digit(n: int, d: int) -> int:
total = 0
weight = 1
while weight <= n:
higher = n // (weight * 10)
cur = (n // weight) % 10
lower = n % weight
if cur > d:
total += (higher + 1) * weight
elif cur == d:
total += higher * weight + lower + 1
else:
total += higher * weight
weight *= 10
return total
注意三条分支从「
cur = 0 / 1 / > 1」变成了「
cur < d / = d / > d」。
d = 1 时
cur < d 就是
cur = 0，所以第一节的三分支只是它的特例。
n = 13 时
count_digit(13, 2) = 2（2 和 12），可以拿这组小数字手验。
数字 0 是唯一的例外：前导零不算（
007 不是一个七位数的写法），所以
cur = 0 时完整循环要少算一个：
def count_digit_zero(n: int) -> int:
total = 0
weight = 1
while weight <= n:
higher = n // (weight * 10)
cur = (n // weight) % 10
lower = n % weight
if cur == 0:
total += (higher - 1) * weight + lower + 1
else:
total += higher * weight
weight *= 10
return total
(higher - 1) 减掉的就是「00X 不算数」的那些前导零。
n = 101 时数 0 得 12、数 1 得 23 ——
同一个 n，0 和 1 的答案能差将近一倍，面试官很爱拿这个追问「你的公式对 0 也成立吗」。
递归版（按最高位切）：不从个位往上扫，而是从最高位往下切，也是常见写法：
def count_digit_one_rec(n: int) -> int:
if n <= 0:
return 0
if n < 10:
return 1
s = str(n)
high = int(s[0])
power = pow(10, len(s) - 1)
rest = n - high * power
if high == 1:
# 最高位贡献 rest + 1 个；低位模式完整出现 1 次 + 尾巴上再出现一次
return rest + 1 + count_digit_one_rec(power - 1) + count_digit_one_rec(rest)
# 最高位贡献 power 个；低位模式完整出现 high 次 + 尾巴上再出现一次
return power + high * count_digit_one_rec(power - 1) + count_digit_one_rec(rest)
以
n = 1304 为例：最高位贡献
304 + 1 = 305 个（1000 ~ 1304 的千位都是 1）；低位模式
000-999 完整出现 1 次，贡献
count(999) = 300；尾巴
300-304 的低三位再递归一次
count(304) = 161。合计
305 + 300 + 161 = 766。递归版和迭代版在
n ≤ 3000 全量一致，在
2147483647 上也一致 —— 但迭代版
O(1) 空间、没有递归深度问题，
面试推荐写迭代版。
六、Java 版：两处 int 溢出
这题在 Java 里有两个独立的溢出点，都是面试里实打实的加分项：
public class CountDigitOne {
// 统计 1 ~ n 中数字 1 出现的次数
public static long countDigitOne(int n) {
if (n < 0) {
throw new IllegalArgumentException("n 必须是非负整数，收到 " + n);
}
long total = 0;
// weight 必须用 long：n 接近 int 上限时循环会走到 10^9，
// 下一步 weight *= 10 就是 10^10，int 装不下会回绕成负数，循环直接失控
long weight = 1;
while (weight <= n) {
long higher = n / (weight * 10);
int cur = (int) ((n / weight) % 10);
long lower = n % weight;
if (cur == 0) {
total += higher * weight;
} else if (cur == 1) {
total += higher * weight + lower + 1;
} else {
total += (higher + 1) * weight;
}
weight *= 10;
}
return total;
}
}
weight 的类型。 n = 2147483647 时循环要走到
weight = 10^9，下一步
weight *= 10 = 10^10 超出 int 范围。int 回绕后
weight 变负数，
weight <= n 仍然成立 ——
死循环。所以
weight 必须是
long。
溢出点二：答案本身的类型。 数 1 的次数可以超过 int 上限：
n ≥ 1633388155 时答案就越界，所以返回类型只能是
long。顺带一个数量级感受：答案大约是
n × log10(n) / 10，
n 到 21 亿时答案接近 30 亿，天然超出 int。
Python 和 JavaScript 不用操心这两点（任意精度 / 双精度在 2^53 内精确），但如果用 C/C++ 写，
weight 同样要
long long。
七、边界情况
10 的幂 那一行值得单独说：它同时是「公式正确性的试纸」和「错法的照妖镜」。
n = 10^k 时正确答案比
k × 10^(k-1) 正好多 1（就是最高位那个 1 本身），写错循环条件的实现会恰好漏掉这 1 个。
八、复杂度
O(log n) 的来路：循环变量
weight 每轮 ×10，从 1 涨到超过
n 只需
log10(n) 轮，每轮 O(1)。
n 从 1304 换成 21 亿，轮数只从 4 变成 10。
答案的量级也有个粗估公式：
每个数位大约贡献 n / 10 个 1，所以总数约等于
n × log10(n) / 10。在
n = 10^k - 1 上这个估计精确成立（
k × 10^(k-1)），可以用来快速 sanity check：
n = 999999 时估 60 万，实际 600000，一位不差。
九、常见坑：官方样例抓不住的三个 bug
这题是「官方样例掩盖 bug」的经典案例。样例
n = 13 的两个数位，
cur 分别是
3 和 1 —— 意味着
cur = 0 的分支在整个样例里
一次都没有执行。三个错误实现都能原样通过样例：
10.1 循环条件写成 weight < n
while weight < n: # 错，应该是 <=
n = 13 上碰巧正确：最高位在十位，
weight = 10 < 13，照样进循环。但
n 恰好是 10 的幂时最高位被漏掉：
最小反例
n = 10。漏掉的恰好是最高位那一份，而
n = 10^k 时最高位只贡献 1 个 1，所以错版总是「差 1」。
10.2 cur = 0 时多给一整块
if cur == 0:
total += (higher + 1) * weight # 错，cur=0 时当前循环不该算
同样的问题：样例里
cur 从不为 0，分支不执行，答案照旧正确。
n = 10 时得 3，正确是 2。
10.3 cur = 0 时直接算 0
# 三分支只写 cur == 1 和 cur > 1，cur == 0 什么也不加
和 10.2 是镜像错误：把 13 个完整百块的 130 个全丢了。
n = 10 时得 1，正确是 2。
测法：补
n = 10, 20, 100, 101 这组「数位中间有 0」的用例。
n = 101 尤其好 —— 三个数位的
cur 是
1, 0, 1，
cur = 0 和
cur = 1 两个分支同时走到，答案是 23（百位 2 + 十位 10 + 个位 11）。
10.4 cur = 1 时忘了 + lower + 1
这个错法国师样例
能抓住（
n = 13 会算出 2 而不是 6），列出来是因为它是手写时最高频的遗漏：
cur = 1 时零头是「从 1 开始数到
lower」，一共
lower + 1 个数，
+1 加的是 1 本身。
10.5 Java 里 weight 用 int
见第七节：
weight *= 10 回绕成负数，
weight <= n 恒成立，
死循环。这是这题在 Java 面试里最致命的形态 —— 不是答案错，是程序挂住。
十、面试怎么答
30 秒版本：
暴力是 O(n log n)，n 到 21 亿不可行。找规律的点在于：按数位统计，不按数字统计 —— 每个数位上 1 的个数只由高于它、当前位、低于它三个值决定。个位上每 10 个数出 1 个 1，十位上每 100 个连出 10 个，这就是权值 weight 的含义；零头部分看当前位：是 0 就不多给，是 1 就数到 lower（lower + 1 个），大于 1 就满额。总时间 O(log n)、空间 O(1)。
如果还有时间，主动补三句，分别是三个加分点：
- 边界：
n = 0 返回 0；循环条件必须是 weight <= n，否则 n 是 10 的幂时漏最高位；
- 溢出：Java 里
weight 和返回值都得是 long —— n = 2147483647 的答案是 2971027783，超出 int；
- 变体：数 2-9 只改比较对象；数 0 要特殊处理前导零（
cur = 0 时完整循环少算一个）。
这套题的完整状态机、渲染层和 27 个单测（含与暴力解的全量交叉验证）都在仓库里，动画对应文章里的两个占位符。