菩提风1. 问题背景与核心挑战
这道题目来自《剑指Offer II》系列的第162题，要求统计从1到n的所有整数中数字1出现的总次数。乍看简单，但直接遍历每个数字逐位统计的暴力解法时间复杂度高达O(nlogn)，在n较大时（比如1e9）会严重超时。
我在上周的LeetCode周赛430中遇到了类似变种题，当时就因为没掌握高效解法而错失AC。后来研究《编程之美》和《剑指Offer》才发现，这类问题需要从数位规律入手，用数学方法将时间复杂度降到O(logn)。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 暴力解法与性能瓶颈
2.1 直观实现方案
最直接的思路是对每个数字进行逐位检查：
python复制def countDigitOne(n):
count = 0
for i in range(1, n+1):
while i > 0:
if i % 10 == 1:
count += 1
i //= 10
return count
当n=12时，计算过程如下：
1 → 1 (count=1)
2 → 2
...
10 → 1,0 (count=2)
11 → 1,1 (count=4)
12 → 1,2 (count=5)
2.2 复杂度分析
- 外层循环执行n次
- 内层while循环执行次数等于数字位数，即log10(n)次
- 总时间复杂度O(nlogn)
当n=1e9时，需要约1e9 * log10(1e9) ≈ 9e9次操作，远超OJ的时间限制（通常1e8次操作为上限）。
3. 数位动态规划解法
3.1 核心思路分解
我们按十进制位从低到高逐位统计1出现的次数。对于第k位（从右往左数，个位为第0位）：
- 当前位数字为curr
- 高位部分为high
- 低位部分为low
- 位权为digit=10^k
根据curr的值分三种情况计算当前位的1出现次数：
情况1：curr == 0
当前位出现1的次数由高位决定：
count = high * digit
示例：n=2304, 计算十位(k=1)时：
high=23, curr=0, low=4, digit=10
count = 23 * 10 = 230
（0010-0019, 0110-0119,..., 2210-2219）
情况2：curr == 1
当前位出现1的次数为：
count = high * digit + low + 1
示例：n=2314, 计算十位时：
high=23, curr=1, low=4
count = 23*10 + 4 + 1 = 235
（除了情况1的230次，还有2310-2314）
情况3：curr > 1
当前位出现1的次数为：
count = (high + 1) * digit
示例：n=2324, 计算十位时：
high=23, curr=2, low=4
count = (23+1)*10 = 240
（0010-0019,..., 2310-2319）
3.2 完整算法实现
python复制def countDigitOne(n):
count = 0
digit = 1 # 从个位开始
high, curr, low = n // 10, n % 10, 0
while high != 0 or curr != 0:
if curr == 0:
count += high * digit
elif curr == 1:
count += high * digit + low + 1
else:
count += (high + 1) * digit
# 更新各变量
low += curr * digit
curr = high % 10
high //= 10
digit *= 10
return count
3.3 复杂度分析
- 循环次数等于数字n的位数，即log10(n)
- 每次循环执行常数次操作
- 总时间复杂度O(logn)
- 空间复杂度O(1)
处理n=1e9时仅需9次循环，相比暴力解法有指数级提升。
4. 测试用例与边界处理
4.1 典型测试用例
| 输入n | 输出 | 说明 |
|---|---|---|
| 0 | 0 | 最小边界 |
| 1 | 1 | 单个数字 |
| 10 | 2 | 1和10 |
| 13 | 6 | 1,10,11,12,13 |
| 99 | 20 | 重点测试进位 |
| 100 | 21 | 包含100的情况 |
4.2 特殊场景验证
- 连续进位：n=999→1000
- 全1数字：n=111→36
- 大数测试：n=1e8→确认不超时
5. 算法推导与数学证明
5.1 数位贡献理论
对于第k位（权重digit=10^k），数字1出现的频率遵循：
- 每完整周期（high变化）出现digit次1
- 当curr=1时，额外增加low+1次
- 当curr>1时，当前周期完整计入
5.2 递推公式
定义f(n)为1到n的1总数，则有：
f(n) = f(n-1) + count1_in(n)
其中count1_in(n)表示数字n本身包含的1的个数
不过我们采用的解法直接计算累计值，避免了递归带来的额外开销。
6. 同类问题扩展
6.1 数字k的个数
将算法中的判断条件改为curr == k即可统计任意数字k（0-9）的出现次数。注意当k=0时需要特殊处理最高位。
6.2 二进制1的个数
LeetCode 338题要求计算0≤i≤n每个数字的二进制1个数。可采用类似的位运算思想：
python复制def countBits(n):
res = [0]*(n+1)
for i in range(1, n+1):
res[i] = res[i & (i-1)] + 1
return res
6.3 回文数统计
LeetCode 906题统计范围内的超级回文数，同样需要数位分解技巧配合回文判断。
7. 实际应用场景
7.1 系统资源预估
在分布式系统中统计日志里错误码1出现的频率，优化监控系统资源分配。
7.2 数字电路设计
计算二进制表示中1的个数（汉明重量）是CRC校验、哈希算法的基础操作。
7.3 游戏开发
某些数字谜题游戏需要快速统计特定数字出现次数来实现计分逻辑。
8. 常见错误与调试技巧
8.1 易错点警示
- 位权digit更新时机错误（应在循环末尾更新）
- 处理curr=0时误加low值
- 循环终止条件遗漏high和curr同时为0的情况
8.2 调试建议
- 打印每次循环的high/curr/low/digit值
- 用n=13等小数据手工验证中间结果
- 特别注意n=0, n=10^k等边界情况
9. 性能优化进阶
9.1 预处理技术
如果需要多次查询，可以预处理建立数位DP表：
python复制# 预处理0-999的计数
BASE = 1000
precompute = [countDigitOne(i) for i in range(BASE)]
def query(n):
count = 0
for k in range(0, len(str(n)), 3):
segment = (n // (10**k)) % BASE
count += precompute[segment]
# 处理跨段影响...
return count
9.2 并行计算
对于极大的n（如1e18），可将数字分段后多线程处理各段的统计结果。
10. 语言特性优化
10.1 Python优化技巧
- 使用divmod函数同时获取商和余数：
python复制high, curr = divmod(n, 10)
- 用math.log10预计算位数减少循环次数
10.2 C++位运算优化
cpp复制int countDigitOne(int n) {
long digit = 1;
int res = 0;
while (digit <= n) {
int high = n / (digit * 10);
int curr = (n / digit) % 10;
int low = n % digit;
// ...三种情况处理
digit *= 10;
}
return res;
}
11. 学习路径推荐
- 基础：先掌握《剑指Offer》原书第43题解法
- 进阶：研究《编程之美》2.4节"1的数目"
- 扩展：LeetCode 233（本题英文版）、1067（数字0的个数）
- 相关：数位DP专题（如600. 不含连续1的非负整数）