LeetCode 233题解析：从暴力枚举到数位统计的高效解法

1. 项目概述一道“数位统计”的经典难题如果你刷过LeetCode大概率会对“233. Number of Digit One”这道题有印象。它常年躺在困难题列表里标签是“数学”和“递归”但很多朋友第一次看到题目描述时可能会觉得它像一道“脑筋急转弯”给定一个整数n计算所有小于等于n的非负整数中数字1出现的总次数。比如n 13从 1 到 13 的数字是1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13。其中数字 1 出现在 1, 10, 11, 12, 13 中注意 11 这个数字包含了两个 1所以总次数是 1来自数字1 1来自10 2来自11 1来自12 1来自13 6 次。乍一看这题不是很简单吗写个循环从 1 遍历到 n把每个数转成字符串数一下里面有几个‘1’不就行了没错对于小的 n这种暴力法完全可行。但题目给出的 n 范围可以大到 10^9甚至更大。当 n 10^9 时你需要循环十亿次每次还要进行数位转换和字符匹配这个计算量是任何在线判题系统都无法接受的必然会导致超时。所以这道题真正的难点和价值就在于如何绕过这种“直观但低效”的暴力枚举找到一种基于数位规律、时间复杂度为 O(log n) 的“数位统计”方法。这不仅仅是解一道算法题更是理解“计数问题”核心思想的一次绝佳训练。在计算机科学和组合数学中如何高效、无遗漏地统计满足特定条件的对象个数是一个基础且重要的问题。这道题将这种思想浓缩在了“数字1的出现次数”这个具体场景里。掌握它你收获的不仅是一个解法更是一种将大问题分解、按位贡献计算的思维模式这种模式在解决更复杂的数位动态规划Digit DP问题时至关重要。2. 核心思路拆解从暴力枚举到分位贡献我们先从最直观的暴力解法开始理解问题再一步步推导出高效解法的核心逻辑。2.1 暴力法的局限与启示暴力解法的伪代码如下def countDigitOne_bruteforce(n: int) - int: count 0 for i in range(1, n 1): num i while num 0: if num % 10 1: # 检查个位是否为1 count 1 num // 10 # 去掉个位检查下一位 return count或者用字符串处理def countDigitOne_bruteforce_str(n: int) - int: count 0 for i in range(1, n 1): count str(i).count(1) return count为什么暴力法不行时间复杂度是 O(n * log₁₀ n)。对于 n 10^9循环次数是 10^9 量级每次循环内部还有对数级别的操作数位拆分或字符串遍历总操作次数轻松突破百亿级别这是不可接受的。这迫使我们必须寻找一个与 n 的位数即 log n相关的算法。暴力法给我们的启示是什么它揭示了问题的本质我们需要统计的是每一个数位上出现数字1的次数的总和。例如对于数字 2134我们关心它的千位、百位、十位、个位上分别出现过多少次1然后将这些次数相加。这就是“分位贡献”思想的基础不逐个数字去检查而是逐个数位去计算这个数位上1出现的总次数。2.2 分位贡献法的核心思想我们将数字 n 表示为一个 k 位的数字d_k d_{k-1} ... d_2 d_1其中d_k是最高位d_1是个位。我们的目标是计算在 1 到 n 的所有数字中某一个固定的数位比如第 i 位从个位开始记为第1位上数字1出现的总次数。最后把每一位上统计的次数加起来就是答案。那么如何计算第 i 位上1出现的次数呢这需要根据当前位d_i的值分为三种情况来讨论。我们以一个具体的数位为例比如 n 3101592我们来计算它的百位第3位d_3 1上1出现的次数。我们把数字分成三个部分高位Higherd_k ... d_{i1}。在例子中对于百位高位是3101。当前位Currd_i。例子中是1。低位Lowerd_{i-1} ... d_1。例子中是92。因子Factor10^{i-1}。它代表了当前位的“权值”或“周期长度”。对于百位i3因子是 10^(3-1) 100。这意味着从 000 到 999 的一个完整周期中任意一个固定数位上的每个数字0-9都会出现因子/10 10^(i-2)次不更准确地说在一个完整的000...999共因子*10个数周期里每个数位上数字0-9出现的次数是均等的都是因子次。例如在 000-999 这1000个数中百位上数字0、1、2...9各出现了100次。现在我们根据当前位Curr的值分三种情况计算当前数位出现1的次数情况一Curr 0当d_i 0时例如 n3101592计算它的千位第4位d_40。 这意味着在 1 到 n 的数字中当前位为1的数字其高位部分最大只能到Higher - 1。 为什么因为如果高位等于Higher那么当前位至少是0这是给定的但为了当前位是1我们需要让高位更小这样在构造数字时当前位才能自由地设为1。 所以当前位为1的数字形如[0...0 到 (Higher-1)] [1] [任意Lower]。高位的选择有Higher种从0到 Higher-1。当前位固定为11种选择。低位的选择有Factor种从0到 Factor-1因为低位可以取任意值。 因此总次数 Higher * Factor。在千位的例子中Higher 310,Curr0,Lower592,Factor1000。 次数 310 * 1000 310,000。 这意味着在1到3101592之间千位上是1的数字有31万个从1000到1999, 21000到21999, ..., 3091000到3091999等注意这里的高位是从0开始计数的包含了数字0XXX的情况但题目是从1开始这里计算的是数位模式最终结果是正确的。情况二Curr 1当d_i 1时这就是我们例子中的百位Higher3101,Curr1,Lower92,Factor100。 这种情况比Curr0更复杂一些因为高位部分可以取两种范围当高位取[0, Higher-1]时当前位可以固定为1低位可以取[0, Factor-1]的任意值。这部分贡献了Higher * Factor次。当高位取Higher时当前位固定为1因为Curr就是1但此时低位不能任意取了它受到原始数字 n 的低位限制只能取[0, Lower]之间的值。这部分贡献了Lower 1次因为从0到Lower共有Lower1个数。 因此总次数 Higher * Factor (Lower 1)。在百位的例子中 次数 3101 * 100 (92 1) 310100 93 310193。情况三Curr 1当d_i 1时例如 n3101592 的十位第2位d_29。Higher31015,Curr9,Lower2,Factor10。 此时高位部分可以取[0, Higher]注意这里可以取到Higher因为即使高位等于Higher当前位是9也大于1所以那些当前位为1的数字是包含在范围内的。高位的选择有Higher 1种从0到Higher。当前位固定为11种选择。低位的选择有Factor种从0到Factor-1。 因此总次数 (Higher 1) * Factor。在十位的例子中 次数 (31015 1) * 10 31016 * 10 310160。2.3 算法流程与实现理解了核心的三种情况算法流程就非常清晰了初始化计数器count 0因子factor 1代表个位的权值。当n // factor ! 0时即还有数位需要处理循环 a. 计算高位higher n // (factor * 10)。 b. 计算当前位curr (n // factor) % 10。 c. 计算低位lower n % factor。 d. 根据curr的值按照上述三种情况更新count。 e. 将factor乘以 10准备处理下一个更高位。循环结束返回count。对应的Python代码实现非常简洁def countDigitOne(n: int) - int: count 0 factor 1 while factor n: higher n // (factor * 10) curr (n // factor) % 10 lower n % factor if curr 0: count higher * factor elif curr 1: count higher * factor lower 1 else: # curr 1 count (higher 1) * factor factor * 10 return count时间复杂度循环次数等于数字 n 的位数即 O(log₁₀ n)。对于 n 高达 10^9位数仅为10效率极高。空间复杂度O(1)只使用了几个变量。3. 关键细节与边界处理虽然算法核心只有几行但其中包含了许多容易出错的细节和边界情况。理解这些细节才能写出健壮、正确的代码。3.1 数位遍历的终止条件循环条件while factor n是正确且安全的。为什么不是while n // factor ! 0两者在 n0 时是等价的但factor n更直观地表达了“我们正在处理不超过 n 的数位”。当factor超过 n 时higher会变为0curr也会变为0循环将不再产生新的贡献可以终止。使用factor n能清晰地表达这一意图。注意务必注意整数溢出的问题。在Python中整数可以任意大所以factor * 10不会溢出。但在C或Java等语言中factor需要用长整型如long long来定义防止在计算factor * 10时溢出。例如当 n 接近 2^31 - 1 时factor 在循环后期会变得很大。3.2 高位、当前位、低位的计算技巧这三行计算是算法的精髓需要准确理解higher n // (factor * 10) curr (n // factor) % 10 lower n % factorn // (factor * 10)整除操作直接去掉了当前位及更低的所有位得到的就是高位数字。例如 n3101592, factor100处理百位factor*1010003101592 // 1000 3101。(n // factor) % 10先通过n // factor将当前位移到个位再% 10取个位数字就得到了当前位的值。接上例3101592 // 100 3101531015 % 10 5等等这里我们之前举例的百位是1。哦我犯了一个错误。当factor100时n // factor 3101592 // 100 31015其个位数字5实际上是原数字的十位。我们需要的是百位。所以正确的当前位索引应该是(n // factor) % 10吗让我们重新思考。这里是一个极其关键的易错点我们定义的factor是10^{i-1}其中 i 是从1个位开始的数位索引。当factor1(i1个位)n // factor n其个位就是原数的个位。(n//1)%10正确。当factor10(i2十位)n // 10的结果其个位对应原数的十位。(n//10)%10正确。当factor100(i3百位)n // 100的结果其个位对应原数的百位。(n//100)%10正确。所以计算curr的公式(n // factor) % 10是正确的。我之前的例子n3101592, factor100n//1003101531015%105。这说明原数的百位是5但我们之前假设百位是1。看来是我记忆中的例子数字出错了。让我们重新设定一个清晰的例子n 31056计算其百位第3位。factor 100higher n // (100*10) 31056 // 1000 31curr (n // 100) % 10 (31056 // 100) % 10 310 % 10 0。所以百位是0。lower n % 100 31056 % 100 56。 情况一Curr0次数 higher * factor 31 * 100 3100。我们可以验证一下在1到31056之间百位是1的数字范围是100-199, 1100-1199, 2100-2199, ..., 30100-30199。高位从0到30共31种每种对应100个数低位00-99所以是3100个。正确。所以计算公式是正确的。关键在于清晰地定义factor和数位索引的关系。3.3 边界情况n 0 和 n 为负数n 0根据题目描述n 是非负整数。当 n0 时小于等于0的非负整数只有0本身。数字0中不包含任何1所以结果应为0。我们的算法中while factor n初始时factor11 0为假循环不会执行直接返回count0。正确。n 为负数题目通常约定 n 是非负整数。如果输入可能为负需要特别处理。通常的做法是如果 n 0直接返回 0因为统计的是非负整数。可以在函数入口处添加判断。3.4 从0开始计数与从1开始计数的统一你可能注意到在我们的推导中高位部分包含了0。例如高位取0时数字形如0...01xx这对应的是一个很小的数比如百位为1高位为0就是1-99之间的数吗不是001xx即1xx也就是100-199之间的数这里有点混乱。实际上我们统计的是数位模式。高位从0开始计数涵盖了所有可能的前导零情况。当我们计算1到n之间某个数位为1的数字个数时这种计数方式恰好是正确且完备的它自动处理了数字位数不足的情况。最终累加的结果就是题目要求的总次数。这是一个非常巧妙的地方也是数位统计类问题的通用技巧在按位贡献计算时可以安全地考虑包含前导零的所有数字因为最终统计的是模式出现的次数而不是数字本身。4. 从具体例子到通用公式的推导验证理论可能有些抽象我们通过几个具体的例子手动计算并验证我们的算法公式以加深理解。例1n 13 (暴力法结果是6)个位 (factor1):higher 13 // 10 1curr (13 // 1) % 10 13 % 10 3lower 13 % 1 0curr 1 count (higher 1) * factor (11)*1 2 解释个位为1的数字1, 11。共2个十位 (factor10):higher 13 // 100 0curr (13 // 10) % 10 1 % 10 1lower 13 % 10 3curr 1 count higher * factor lower 1 0*10 3 1 4 解释十位为1的数字10, 11, 12, 13。注意11的十位也是1。共4个总次数 2 4 6。正确。例2n 99暴力法1-9有1个110-19有11个110,11,...,19其中11有两个1共11个20-99中每10个数20-29,30-39,...,90-99的个位会出现1次1即21,31,...,91共8个。另外20-99中十位为1的数字没有。所以总数 1 11 8 20。 公式计算个位 (f1): higher9, curr9, lower0. curr1 count (91)*110十位 (f10): higher0, curr9, lower9. curr1 count (01)*1010总次数20。正确。例3n 101个位(f1): higher10, curr1, lower0. curr1 count 10*1 0 1 11十位(f10): higher1, curr0, lower1. curr0 count 1*10 10百位(f100): higher0, curr1, lower1. curr1 count 0*100 1 1 2总次数1110223。 验证1-9:1个10-19:11个20-99:8个个位为1100:1个101:1个。合计11181122等等这里出错了。我们手动列一下 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 31, 41, 51, 61, 71, 81, 91, 100, 101。 数一下1的个数数字1(1), 10(1), 11(2), 12(1), 13(1), 14(1), 15(1), 16(1), 17(1), 18(1), 19(1), 21(1), 31(1), 41(1), 51(1), 61(1), 71(1), 81(1), 91(1), 100(1), 101(1)。加起来1 1211111111 111111111 1 1 23。正确。我之前的“20-99:8个”是对的21,31,...,91但漏算了100和101。所以公式计算正确。通过这些例子我们可以确信公式的正确性。5. 算法扩展与变种思考掌握了“数字1”的计数我们可以很自然地将思路扩展到其他数字甚至是任意数字的出现次数统计。5.1 统计数字 k (1-9) 的出现次数算法几乎完全一样只需要修改判断条件。原来我们统计的是当前位curr等于1的情况。现在要统计数字k则当curr k时次数 higher * factor当curr k时次数 higher * factor lower 1当curr k时次数 (higher 1) * factor注意这里k是 1 到 9。为什么不是0因为数字0的处理更特殊不能有前导零我们稍后讨论。Python实现def countDigitK(n: int, k: int) - int: if k 1 or k 9: return 0 # 或者根据需求处理 count 0 factor 1 while factor n: higher n // (factor * 10) curr (n // factor) % 10 lower n % factor if curr k: count higher * factor elif curr k: count higher * factor lower 1 else: # curr k count (higher 1) * factor factor * 10 return count5.2 统计数字 0 的出现次数统计0需要格外小心因为数字的最高位不能是0即没有前导零。所以我们的计算需要调整仍然从个位开始遍历。对于最高位我们不应该考虑高位为0的情况即数字位数不足的情况。在我们的通用公式中higher是从0开始计的这包含了前导零。对于0我们需要排除这种情况。更简单的思路是统计0出现的次数可以转换为统计“每一位上该位为0的数字有多少个”但要排除那些以0开头的数字即位数不足的数字。一种常见的计算方法是对于每一位从个位开始factor1,10,100,...higher n // (factor * 10)curr (n // factor) % 10lower n % factor如果当前位不是最高位即higher 0如果curr 0次数 (higher - 1) * factor lower 1如果curr 0次数 higher * factor如果当前位是最高位higher 0则跳过因为最高位不能是0。这个逻辑稍微复杂一些核心是去掉了高位为0的那种情况即higher0的情况。你也可以用另一种方式理解统计1-9的总次数然后用所有数位的数字总数减去它再减去前导零带来的影响。但直接推导公式更直观。5.3 与数位动态规划Digit DP的联系“Number of Digit One”是数位动态规划的一个经典入门例题。数位DP通常用于解决在某个区间[L, R]内满足特定条件的数字有多少个的问题。这类问题通常有巨大的数据范围如 1 L R 10^18无法枚举。数位DP的核心思想也是“按位处理”并结合记忆化搜索。对于本题数位DP的状态可以设计为dp[pos][count][limit]表示处理到第pos位时已经出现了count个数字1当前是否受到上限limit的限制。然后通过DFS从高位向低位搜索。我们这里介绍的“分位贡献”法实际上是数位DP在这种特定问题统计单个数字出现次数上的一个高度优化和特解。它利用了数字1出现次数的可加性以及每一位贡献的独立性推导出了直接的数学公式从而将时间复杂度降到了 O(log n)并且不需要递归和记忆化空间复杂度为 O(1)。可以说这道题是连接“数学巧解”和“通用数位DP”的一座桥梁。理解了本题再去学习数位DP你会对“按位计数”有更深刻的认识。6. 常见错误与调试技巧即使理解了算法在实现时也可能遇到一些陷阱。下面是一些常见的错误和调试方法。6.1 整数溢出问题如前所述在C/Java等语言中factor在循环中不断乘以10当 n 很大时比如 2^31 - 1 2147483647factor在最后几次循环中会超过 2^31导致32位整数溢出。因此factor必须使用64位整数如long long或long。在Python中则无需担心。6.2 循环条件与因子更新顺序错误的写法while n // factor ! 0: # 或者 while factor n: # ... 计算 ... factor * 10 # 更新count这个顺序问题不大。但更清晰的写法是将因子更新放在循环末尾。务必确保在计算higher,curr,lower时使用的是当前迭代的factor值。6.3 对“低位”和“高位”理解的偏差最容易出错的就是higher,curr,lower的计算公式。务必记住factor代表当前位的“单位”。个位是1十位是10百位是100。higher n // (factor * 10)除以factor*10是为了把当前位和低位都去掉。curr (n // factor) % 10除以factor把当前位移到个位再模10取出来。lower n % factor模factor得到比当前位更低的所有位。可以用一个小例子反复验证比如 n1234, factor10 (处理十位)higher 1234 // 100 12curr (1234 // 10) % 10 123 % 10 3lower 1234 % 10 4 结果符合数字1234高位是12当前位十位是3低位个位是4。6.4 验证算法正确性的方法对于这类问题最可靠的调试方法是对拍Compare and Debug实现一个绝对正确但低效的暴力算法用于小范围n。实现我们优化后的算法。在一个循环中例如 for n in range(1, 10000)比较两个算法的输出。如果发现不一致就打印出出错的 n 值然后手动或通过调试器逐步执行优化算法查看每一步的中间变量higher, curr, lower, count与自己的理解进行对比。例如写一个简单的测试脚本def brute_force(n): count 0 for i in range(1, n1): count str(i).count(1) return count def optimal(n): # 实现上述算法 pass for i in range(1, 10000): if brute_force(i) ! optimal(i): print(fError at n{i}: brute{brute_force(i)}, optimal{optimal(i)}) break else: print(All tests passed up to 9999.)这是验证算法正确性的黄金标准。7. 性能分析与优化空间我们的算法时间复杂度已经是 O(log n)对于题目约束绰绰有余。从工程角度还有哪些可以考虑的点呢7.1 时间复杂度与常数优化算法主体是一个循环循环次数是 n 的十进制位数即 ⌊log₁₀ n⌋ 1。对于 n10^9循环10次对于 n10^18循环19次。这是一个常数极小的 O(log n) 算法几乎没有优化必要。在极端追求性能的场景下例如需要处理海量查询可以注意到循环内的操作是简单的整数除、模和乘法。在现代CPU上这些操作很快。进一步的“优化”可能得不偿失会损害代码的可读性。7.2 空间复杂度算法只使用了几个整型变量空间复杂度 O(1)已经是最优。7.3 针对特定范围的预处理如果问题不是单次查询而是多次查询不同的 n比如 Q 次查询每次给出一个 n_i我们的算法每次都需要 O(log n_i) 的时间。总时间复杂度为 O(Q log max(n))。在这种情况下有没有可能优化理论上由于每次查询是独立的且 n 的范围可能很大很难有通用的预处理方法能显著降低单次查询的复杂度。我们的 O(log n) 算法对于单次查询已经非常高效即使 Q 很大比如 Q10^5总操作量也在可接受范围内10^5 * 20 ≈ 2e6 次运算。一个可能的“优化”是使用记忆化记录一些中间结果但对于这种纯数学计算每一步都直接依赖于输入的 n记忆化没有意义。所以对于多次查询直接对每个 n 独立运行我们的算法就是最佳策略。7.4 语言特性带来的差异在Python中整数运算虽然方便但相比C的本地整数运算会慢一些。在LeetCode等平台上Python版本的运行时间通常比C长但得益于算法高效的复杂度依然能轻松通过。如果是在性能极其苛刻的环境可以考虑用C实现。C实现示例int countDigitOne(int n) { long long count 0; for (long long factor 1; factor n; factor * 10) { long long higher n / (factor * 10); long long curr (n / factor) % 10; long long lower n % factor; if (curr 0) { count higher * factor; } else if (curr 1) { count higher * factor lower 1; } else { count (higher 1) * factor; } } return count; }注意这里factor,higher等变量需要使用long long防止溢出。8. 实战心得与总结这道“数字1的个数”题我最初遇到时也是被它的困难标签吓到尝试暴力法超时后才开始认真寻找规律。经过推导和实现我有几点很深的体会第一不要畏惧数学推导。很多算法题的本质是数学问题。这道题就是一个典型的例子。与其漫无目的地尝试各种数据结构不如静下心来从最简单的例子开始n1, 10, 13, 99, 101在纸上写一写、数一数观察每一位上1出现的规律。当你发现“分位贡献”这个突破口后问题就迎刃而解了。第二掌握“分治”和“贡献法”思想。这是算法竞赛和面试中极其重要的思想。不要总想着一次性解决整个问题。像这道题把“统计所有数字中1的个数”这个大问题分解为“统计每一位上1出现的次数”这个小问题每个小问题又可以根据当前位的值分为三种情况。这种“分解-解决-合并”的思路是解决复杂问题的利器。第三边界条件和细节决定成败。算法思路可能5分钟就想通了但实现时higher、curr、lower的计算公式循环的终止条件factor的数据类型这些细节一处出错满盘皆输。务必用多个小例子包括0、个位数、整十数、像99、101这样的边界数反复测试你的代码。第四理解背后的本质才能举一反三。不要满足于AC这道题。问问自己如果统计的是数字2呢如果统计的是数字0呢如果问题变成“计算1到n中二进制表示下1的个数总和”呢这些问题都可以用类似的思路解决。掌握了“按位贡献”这个内核你就掌握了一类问题。最后这道题在面试中出现的频率不低因为它能很好地考察候选人的逻辑思维、数学归纳和编码严谨性。在面试中你可以先提出暴力解法并分析其复杂度然后引导面试官思考更优解逐步推导出公式最后写出代码并讨论边界情况。这个过程能充分展示你的问题解决能力。