LeetCode 233 数位1计数：从数位DP到通用计数问题的算法精解

1. 项目概述：从一道“困难”题看计数问题的本质

看到“LeetCode 233. Number of Digit One”这个标题，很多人的第一反应可能是：又是一道数学题，还是困难级别，直接跳过吧。我最初也是这么想的，直到在一次模拟面试中被问到，硬着头皮分析后才发现，这道题远不止是“数1”那么简单。它本质上是一个基于数位拆解的计数模拟问题，是理解计算机如何处理“数”的绝佳案例，也是面试中区分候选人思维深度的经典题目。这道题要求我们计算在非负整数n以内（即0 ≤ x ≤ n）的所有数字中，数字1在所有数位上出现的总次数。例如，n = 13，我们需要统计0,1,2,3,...,13这些数字的十位和个位上，一共出现了多少个1（结果是6个：1, 10, 11, 12, 13）。

为什么这道“困难”题值得深究？因为在日常开发中，类似的“分治”与“按位统计”思想无处不在，比如日志分析中统计特定特征出现的频率、设计分页逻辑、甚至是某些压缩算法的核心。它考察的不是复杂的算法模板，而是将一个大问题分解为对每一个数位独立贡献的计算能力。如果你能清晰地说出“当前位”、“高位”、“低位”以及“因子”这几个概念在这道题里的作用，那么你对整数处理的理解就已经超过了大多数死记硬背刷题的人。接下来，我将彻底拆解这道题，不仅给出解法，更会深入探讨其背后的数位DP思想、如何避免整数溢出、以及如何将这种思路迁移到其他计数问题中。

2. 核心思路拆解：为什么不能暴力枚举？

最直观的想法是暴力法：遍历从1到n的每一个数，将其转换为字符串，然后统计其中字符‘1’的个数，最后累加。这个方法简单直接，代码如下：

def countDigitOne_bruteforce(n: int) -> int: count = 0 for i in range(1, n + 1): count += str(i).count('1') return count

为什么这个方法行不通？问题就出在时间复杂度上。对于每个数i，我们需要将其转换为字符串，这个操作的时间复杂度是O(log i)（因为数字的位数约为log10 i）。那么，总的时间复杂度就是O(n log n)。当n很大时，比如n = 10^9，这个计算量是无法接受的，在LeetCode上必然会超时（Time Limit Exceeded）。因此，我们必须寻找一种与数字位数相关，而非与数值大小直接相关的算法，即时间复杂度为O(log n)的算法。

这就引出了我们的核心策略：按数位贡献计算。我们不再逐个数字检查，而是单独考虑每一位（个位、十位、百位……）上出现1的次数，然后将所有位上的次数加起来。这种“分而治之”的思想是解决此类计数问题的关键。

2.1 数位贡献法的基本框架

我们设当前正在考察第k位（从个位开始，k=0表示个位，k=1表示十位，依此类推）。我们需要一个“因子”factor来表示当前位的权重，即factor = 10^k。例如，对于十位（k=1），factor = 10。

对于任意一个数字n，我们可以根据当前位factor，将其拆分为三个部分：

1. 高位（high）：n // (factor * 10)
2. 当前位（cur）：(n // factor) % 10
3. 低位（low）：n % factor

以n = 31025, factor = 100 (即考察百位，k=2)为例：

• high = 31025 // 1000 = 31
• cur = (31025 // 100) % 10 = 0
• low = 31025 % 100 = 25

接下来，我们的目标就是计算在0 ~ n的所有数字中，当前这一位（百位）上出现数字1的次数。计算规则取决于当前位cur的值。

2.2 当前位cur的三种情况分析

这是整个算法的精髓所在，需要仔细理解。

情况一：cur == 0当当前位为0时，例如上面例子中的百位是0。那么，当前位为1的数字，其高位部分只能从0 ~ (high - 1)中取值。 为什么？因为如果高位等于high（即31），那么当前位至少是0（实际上就是0），不可能为1。要想当前位为1，高位必须小于31。 对于每一个确定的高位（有high种选择：0,1,...,30），低位low可以取0 ~ (factor - 1)之间的任意值（即0~99），共有factor种选择。 因此，总贡献为：high * factor。 在我们的例子中，贡献 =31 * 100 = 3100。这意味着在0到31025之间，百位上是1的数字有3100个（例如 00100~00199, 01100~01199, ..., 30100~30199）。

情况二：cur == 1当当前位为1时，例如n = 31125, factor=100，此时high=31, cur=1, low=25。 这种情况下，数字可以分成两部分：

1. 高位从0 ~ (high - 1)：这部分和情况一相同，贡献为high * factor。
2. 高位等于high：此时当前位固定为1，但低位low不能超过给定的low（即25）。因此，低位可以取0 ~ low，共有(low + 1)种选择。 因此，总贡献为：high * factor + low + 1。 在我们的例子中，贡献 =31 * 100 + 25 + 1 = 3126。这包括了所有百位是1的数字，从00100~00199, ..., 30100~30199，以及31100~31125。

情况三：cur > 1当当前位大于1时，例如n = 31225, factor=100，此时high=31, cur=2, low=25。 此时，高位可以从0 ~ high中取值（注意，这里包括了high）。因为即使高位取到high（31），当前位是2，仍然大于1，所以高位为high时，当前位取1是允许的（即数字31100~31199）。 对于每一个确定的高位（有high + 1种选择：0,1,...,31），低位可以取0 ~ (factor - 1)之间的任意值。 因此，总贡献为：(high + 1) * factor。 在我们的例子中，贡献 =(31 + 1) * 100 = 3200。

核心理解：这三种情况的核心区别在于，高位取到最大值high时，是否还能保证当前位为1。cur=0时不能，cur=1时部分能（取决于低位），cur>1时完全能。把握住这一点，公式就很好记忆了。

3. 算法实现与逐行解析

理解了数学原理，代码实现就非常清晰了。我们将使用迭代的方式，从个位开始，逐位计算贡献，直到遍历完n的所有位。

def countDigitOne(n: int) -> int: count = 0 factor = 1 # 从个位开始，因子为10^0=1 high, cur, low = n // 10, n % 10, 0 # 初始化高位、当前位、低位 while high != 0 or cur != 0: # 当高位和当前位都为零时，说明所有位已处理完 # 根据当前位cur的值，应用三种情况的公式 if cur == 0: count += high * factor elif cur == 1: count += high * factor + low + 1 else: # cur > 1 count += (high + 1) * factor # 准备处理下一位：因子乘以10，低位更新，当前位变成新的低位，高位取余 low += cur * factor # 当前位加入到低位中，构成下一轮的低位 cur = high % 10 # 原高位的最后一位成为新的当前位 high //= 10 # 原高位去掉最后一位，成为新的高位 factor *= 10 # 因子进位 return count

逐行解析与注意事项：

1. 初始化 (high, cur, low)：我们初始时将n的个位作为cur，其余部分作为high，low初始为0。这种初始化让循环逻辑统一。
2. 循环条件 (while high != 0 or cur != 0)：这个条件确保了即使n=0，循环也会因为cur=0且high=0而直接跳过，返回count=0，这是正确的。对于任何n>0，循环都会处理到最高位。
3. 核心计算部分：直接对应我们前面分析的三种情况。这是算法的核心，务必理解每个变量的含义。
4. 更新部分（最容易出错的地方）：
   • low += cur * factor：这是关键。当前轮次的cur和factor决定了当前位的实际数值。在下一轮处理更高位时，当前位就变成了“低位”的一部分。例如，处理完个位后，个位的值（cur）需要加入到low中，以便在处理十位时，low代表的就是原始的个位数。
   • cur = high % 10：获取新的当前位（原高位的最后一位）。
   • high //= 10：去掉原高位的最后一位，得到新的高位。
   • factor *= 10：因子进位，准备处理下一位（十位、百位...）。
5. 边界情况处理：该算法天然处理了n=0和n为最大整数（如2^31-1）的情况，因为循环逻辑和数学公式是普适的。

一个完整的计算示例（n=13）：我们来手动模拟一下，验证结果是否为6。

• 初始：factor=1, high=1, cur=3, low=0
• 第一轮（处理个位，factor=1）:
  • cur=3 > 1，贡献 =(high + 1) * factor = (1+1)*1 = 2。这对应个位为1的数字：1, 11。注意，此时11的十位还未处理。
  • 更新：low = 0 + 3*1 = 3,cur = high%10 = 1%10 = 1,high = 1//10 = 0,factor=10。
• 第二轮（处理十位，factor=10）:
  • cur=1，贡献 =high * factor + low + 1 = 0*10 + 3 + 1 = 4。这对应十位为1的数字：10, 11, 12, 13。注意，11在个位和十位各被统计了一次，这正是我们需要的。
  • 更新：low = 3 + 1*10 = 13,cur = 0%10 = 0,high = 0//10 = 0,factor=100。
• 循环结束（high=0且cur=0）。
• 总贡献 = 2 + 4 = 6。结果正确。

4. 深度扩展：从“数1”到通用“数位计数”

掌握了“数1”的精髓后，我们可以将其推广到更一般的问题：计算数字0~9在1~n中出现的次数。这是一个经典的面试题变种。思路完全一致，只是公式需要根据目标数字d和当前位cur的关系进行微调。

4.1 通用公式推导

设目标数字为d(0 ≤ d ≤ 9)。我们依然考察第k位（因子为factor），将n分解为high, cur, low。

我们需要计算当前位等于d的贡献。分为几种情况：

1. 如果d != 0：

   • 当cur < d时：高位只能取0 ~ (high - 1)，贡献为high * factor。
   • 当cur == d时：贡献为high * factor + low + 1。
   • 当cur > d时：高位可以取0 ~ high，贡献为(high + 1) * factor。 这和“数1”的公式完全一致，因为“数1”就是d=1的特例。

2. 如果d == 0：这是唯一需要特殊处理的情况，因为数字不能有前导零。例如，数字05通常被视为5，其十位上的0不应被计数。

   • 当cur > 0时：高位可以取0 ~ (high - 1)？等等，这里需要小心。对于d=0，当高位为0时，当前位是0属于前导零，不应计数。因此，高位实际上只能从1开始取。所以贡献为(high - 1) * factor + (low + 1)？不，更严谨的分析如下：
     • 高位部分：高位至少为1。当cur > 0，高位可以从1 ~ high取值（如果high > 0）。但注意，当高位取high时，当前位是cur，它大于0，所以当前位为0的情况只可能发生在高位小于high的时候。因此，贡献为(high) * factor？让我们用例子检验。 实际上，对于d=0且cur > 0，当前位为0意味着这个数字的高位部分不能等于当前的high（否则当前位就是cur而不是0）。所以，高位只能取0 ~ (high-1)，但高位为0时可能产生前导零问题吗？不会，因为当前位是0，但高位是0，整个数字可能就是像0...0xyz这样的形式，其中第一个非零位在当前位之后。例如n=1024，考察十位(factor=10,cur=2)，统计十位为0的数字。像1000~1009这些数字，其十位是0，高位是10（即百位及以上是10），这是允许的。高位为0的例子是0000~0009，即个位数，它们的十位确实是0，也应该被统计吗？在统计1~n中0的出现次数时，前导零不计数，但数中间的零要计数。0005就是5，其十位是“不存在”的，而不是0。因此，在统计非最高位时，高位可以为0；在统计最高位时，d不能为0。这是一个非常容易混淆的点。 更通用的方法是：统计0时，高位部分的取值范围需要排除掉高位为0且当前位是最高位的情况。一个更清晰的实现方式是：将问题转化为统计1~n中每个数位上0~9的出现，然后对0的情况进行后处理，减去前导零的计数。或者，直接修改公式，当d=0时，高位的有效范围是1 ~ high（如果当前位不是最高位，则高位可以从0开始，但高位为0时表示这个数字的位数比当前位少，当前位上的0是有效的中间位零吗？是有效的，例如数字5，在十位上看就是0）。这很绕。

   鉴于d=0情况的复杂性，一个更稳妥、更清晰的通用解法是：分别统计1~n中每个数字0~9的出现次数，可以调用countDigitOne的函数逻辑，但对d=0做特殊判断，或者直接遍历统计。对于面试而言，能清晰阐述d>0的通用性并指出d=0的特殊性，已经足够展示深度。

4.2 算法复杂度与优化空间

我们实现的countDigitOne算法时间复杂度是O(log n)，因为循环次数等于数字n的位数（以10为底）。空间复杂度是O(1)，只使用了几个整型变量。这已经是这个问题的最优解法。

潜在的优化与注意事项：

• 整数溢出：在 Python 中不存在整数溢出问题，但在 Java、C++ 等语言中，factor和(high + 1) * factor这类计算在n很大时（如n=2^31-1）可能导致int类型溢出。需要使用long long类型来存储中间结果。
• 循环终止条件：我们的条件是while high != 0 or cur != 0。也可以写成while factor <= n，但前者在处理过程中更新变量更清晰。
• 对称性：有同学可能会想，能否从最高位向最低位处理？理论上可以，但实现起来需要维护一个“剩余范围”，不如从低位到高位处理直观。

5. 常见问题与调试技巧

即使理解了算法，在实现时也可能遇到一些陷阱。下面是我在多次实现和教学中总结的常见问题。

5.1 问题一：结果比预期少，特别是对于末尾包含0或1的数字

原因：最可能的原因是变量更新顺序错误。注意我们代码中的更新顺序：

low += cur * factor # 先更新low，使用当前的cur和factor cur = high % 10 # 再更新cur high //= 10 # 最后更新high

如果顺序错了，比如先更新high和cur，再更新low，那么用于计算low的cur和factor就已经是下一轮的值了，必然出错。

调试技巧：对于n=10, 11, 101, 110这样的边界值，使用纸笔或调试器，一步一步跟踪high,cur,low,factor,count的变化，与手动计算的结果对比。

5.2 问题二：如何处理输入 n=0 的情况？

我们的算法中，循环条件while high != 0 or cur != 0在n=0时，初始high=0, cur=0，循环不会进入，直接返回count=0，这是符合要求的（0到0之间，数字1出现的次数为0）。这是一个优雅的处理。

5.3 问题三：公式记忆混乱，三种情况容易搞混

记忆口诀：

• cur == 0：高位不敢顶满，只能取0 ~ (high-1)，所以是high * factor。
• cur == 1：高位不顶满的情况 + 高位顶满时低位受限的情况，所以是high * factor + low + 1。
• cur > 1：高位可以顶满，取0 ~ high，所以是(high + 1) * factor。 关键在于思考：当高位取到最大值high时，当前位有没有可能为1？这个可能性决定了高位的取值范围。

5.4 问题四：推广到其他数字（d）时，对0的处理总是出错

正如第4部分所讨论的，统计数字0的出现次数是本题的难点。在面试中，如果被问到，建议采取以下策略：

1. 首先给出统计d=1~9的通用解法，强调其与本题解法的同构性。
2. 指出d=0的特殊性在于“前导零”不应计数。
3. 可以提供两种思路：
   • 思路A（推荐）：分别统计1~n中每一位上0~9的出现次数。对于非最高位，0可以正常出现；对于最高位，0不会出现。这需要更细致的分类讨论。
   • 思路B（取巧）：利用总和不变的性质。先计算1~n所有数字的位数总和（即total_digits = sum(len(str(i)) for i in range(1, n+1))），然后计算数字1~9出现的总次数sum_count_1_to_9，那么数字0出现的次数就是total_digits - sum_count_1_to_9。但这个方法需要计算位数总和，可能并不比直接统计简单。

实操建议：如果面试官追问，可以和他/她确认：“您希望我详细推导d=0的复杂情况，还是先确保d=1~9的通用解法完全正确？” 这既展示了你的沟通能力，也体现了你对问题复杂度的认知。

最后，这道“困难”题的价值，不在于记住一个公式，而在于掌握将大规模计数问题分解为独立数位贡献的思想。下次当你遇到需要统计满足某种条件的数字个数，且条件与数位相关时，不妨想想：我能不能像解这道题一样，单独考虑每一位？这种思维训练，远比AC一道题本身重要得多。我在解决一些实际的数据分析任务时，就曾运用这种思想，高效统计了日志中特定模式出现的频次，其核心就是将模式匹配转化为按位独立的概率或计数问题。