1. 从一道“数1”的难题说起为什么它值得你花时间如果你刷过LeetCode大概率见过这道题233. Number of Digit One。题目描述很简单给定一个整数n计算所有小于等于n的非负整数中数字1出现的次数。比如n 13从 0 到 13数字 1 出现在 1, 10, 11, 12, 13 中总共出现了 6 次。乍一看这题似乎毫无难度一个简单的循环遍历每个数再逐位判断不就行了但当你看到题目难度标签是“困难”并且n的取值范围可以高达10^9时你就该意识到事情没那么简单。暴力遍历的时间复杂度是O(n * log10(n))对于n10^9来说计算量是天文数字必然超时。这道题真正的价值远不止于让你通过一个测试用例。它是一道经典的数位统计问题其核心解法——按位贡献法或称为数位DP的简化形式——是解决一大类“数字统计”问题的钥匙。这类问题包括但不限于统计某个数字出现的次数、统计特定数字模式的个数、计算数字的某种特性之和等等。掌握这道题的思路你就能触类旁通解决诸如“数字 2 出现的次数”、“数字范围内不含 4 的数字个数”等一系列问题。今天我们就来彻底拆解这道“困难”题不仅告诉你“怎么做”更要讲清楚“为什么这么做”以及在实际编码和面试中你会遇到哪些意想不到的坑。2. 暴力法的死胡同为什么遍历每一位也不行面对统计问题我们最直接的思路是模拟。最朴素的暴力法就是写一个循环从 1 遍历到 n对每个数字 i将其转换为字符串或者通过取模运算逐位检查是否为 1然后累加计数。def countDigitOne_naive(n: int) - int: count 0 for i in range(1, n 1): while i 0: if i % 10 1: count 1 i // 10 return count这个方法在n13时工作良好但正如前面所说当n很大时其时间复杂度为O(n * log n)完全不可接受。一个常见的优化想法是既然要统计所有数字中 1 出现的次数我能不能直接遍历每一位个位、十位、百位...分别计算这一位上会出现多少次 1最后把各位的贡献加起来这个思路是对的也是我们最终解法的方向。但很多人的第一版“优化”会写成这样对于每一位固定一个数字比如个位的1然后看有多少个数字在这个位上是1。他们可能会尝试用除法或取模来分组计算但如果没有清晰的数学模型很容易把自己绕进去写出逻辑复杂且容易出错的代码。实际上暴力法的失败给我们指明了出路必须找到一种不依赖于逐个数字检查的方法而是直接通过数学规律计算出在 0 到 n 的所有数字中每一位十进制位上出现 1 的次数的总和。这就是“按位贡献法”的精髓。我们需要放弃“枚举数字”的视角转而采用“枚举数位”和“贡献值”的视角。接下来我们就来建立这个关键的数学模型。3. 核心思路拆解如何计算某一位上的“1”我们以数字n 3101592为例目标是计算所有小于等于 n 的数字中百位从右往左数第3位即5所在的位上出现数字 1 的次数。我们把当前位记为cur其左边的数字记为high右边的数字记为low当前位的因子即 10^kk 从0开始记为digit。对于n 3101592分析百位cur 5,digit 100high 3101百位左边的数字cur 5百位当前数字low 92百位右边的数字现在我们考虑在 0 到 3101592 之间百位为 1 的数字有多少个。我们可以把这些数字的百位固定为 1然后看高位和低位有多少种组合。情况一当cur 0时如果当前位是 0比如我们要分析的数字是3100_92这里_表示当前位当前位是 0。要想让当前位变成 1我们必须通过高位来“借位”。具体来说高位的取值范围只能是0 到 (high-1)。因为如果高位等于high即 3101那么整个数就会大于等于3101_92而由于当前位是 0这个数的最小值310100已经大于原数310092了因为高位相同当前位0原数当前位这里需要统一我们以固定当前位为1来思考。更准确的说法是当cur 0时高位不能取到high否则数字会超过 n。例如高位取 3101当前位固定为1得到数字3101_1_92这显然大于3100_92因为高位相同但当前位1 0。所以高位有high种选择0 到 high-1。低位则可以取0 到 99因为digit100低位有100种可能。因此总贡献为high * digit。情况二当cur 1时如果当前位是 1比如我们分析3101_92的百位此时cur1。这时情况要分两种高位取0 到 high-1此时无论低位怎么取最终数字一定小于 n因为高位已经更小了。所以这部分贡献是high * digit。高位取high此时数字的前几位已经和 n 相同了。要保证整个数字不大于 n低位只能取0 到 low。所以这部分贡献是low 1。 因此总贡献为high * digit (low 1)。情况三当cur 1时如果当前位大于 1比如我们例子中的cur 5。那么高位取0 到 high-1贡献为high * digit。高位取high此时因为当前位cur (5) 1即使我们固定当前位为 1得到的数字3101_1_92也一定小于3101_5_92即原数 n所以低位可以自由取0 到 99。贡献为digit。 但注意当高位取high时当前位固定为1这个数肯定小于 n因为 1 5所以低位可以取满digit个值。因此总贡献为high * digit digit即(high 1) * digit。注意这里最容易混淆的是high和digit的取值。high是当前位左边的数字digit是当前位的位权1, 10, 100...。low是当前位右边的数字它的范围是0 到 digit-1。在计算时务必在纸上画出一个数字的结构high cur low并清晰地标出cur的位置。我们可以把上述三种情况合并成一个公式吗可以但我不建议初学者死记硬背公式。更好的方法是理解其推导过程然后根据cur的值分情况处理。不过为了代码简洁我们可以观察到贡献中high * digit这一部分在cur 1时是high * digit在cur 1时是(high 1) * digit。这可以统一为(high (cur 1)) * digit不完全是因为当cur 1时我们加的是整个digit而不仅仅是high变成了high1。实际上更通用的写法是当前位1的贡献来自于高位的变化和低位的组合。我们可以计算高位在0 到 high-1时的贡献high * digit。然后再加上高位等于high时的贡献这取决于cur若cur 0贡献为 0。若cur 1贡献为low 1。若cur 1贡献为digit。 因此总贡献 high * digit contribution_when_high_is_high。其中contribution_when_high_is_high根据cur的值确定。这是最清晰、最不易出错的思考方式。4. 算法实现与逐行代码解析理解了核心思路后我们来看代码实现。我们将从最低位个位开始逐步向高位移动计算每一位的贡献并累加。def countDigitOne(n: int) - int: if n 0: return 0 count 0 digit 1 # 从个位开始位权为1 while n // digit 0: # 当高位还存在时继续循环 high n // (digit * 10) # 当前位左边的数字 cur (n // digit) % 10 # 当前位的数字 low n % digit # 当前位右边的数字 # 根据当前位 cur 的值计算贡献 if cur 0: # 高位只能取 0 到 high-1低位可以取 0 到 digit-1 count high * digit elif cur 1: # 高位取 0 到 high-1 时贡献为 high * digit # 高位取 high 时低位只能取 0 到 low count high * digit (low 1) else: # cur 2 # 高位取 0 到 high-1 时贡献为 high * digit # 高位取 high 时因为 cur 1固定当前位为1后数字肯定小于n低位可以取满 count (high 1) * digit digit * 10 # 移动到下一位十位、百位... return count让我们逐行解析关键部分并解释一些容易出错的细节循环条件while n // digit 0这个条件确保我们处理完所有有效的位。digit是当前位的位权。n // digit得到的是当前位及其高位的数字。当这个数字大于 0说明还有高位需要处理。例如n13,digit100时n//digit 0循环结束。这比计算数字的位数更简洁。计算high,cur,lowhigh n // (digit * 10)要得到当前位左边的数字需要用n除以当前位权的 10 倍。比如n3101592,digit100百位digit*101000n // 1000 3101这正是百位左边的数字。cur (n // digit) % 10先通过n // digit把当前位及高位“挪”到低位再% 10取个位数就得到了当前位的数字。继续上例n//100 3101531015 % 10 5。low n % digit直接取模得到当前位右边的部分。n % 100 92。 这三个变量的计算是核心务必保证正确。一个常见的错误是high的计算用了digit而不是digit*10。分情况累加count这里完全对应我们第三节的推导。注意low 1是因为低位可以从 0 取到low共low 1个数。更新digitdigit * 10将位权提升十倍处理下一位。这个算法的时间复杂度是O(log10(n))因为循环次数等于n的十进制位数。空间复杂度是O(1)。对于n高达10^9循环次数仅为 10 次左右效率极高。5. 从特例到通解如何验证和调试你的逻辑在实现这类数学性强的算法时最怕的就是“想当然”和“边界情况”。我们不能只依赖题目给出的几个示例必须自己设计测试用例来验证逻辑的完备性。以下是我推荐的一套测试用例覆盖了各种边界和容易出错的情况基础案例n 0- 0。我们的代码通过if n 0: return 0处理。个位为1n 1- 1。n 10- 2 (1, 10)。检查个位计算是否正确。十位为1n 20- 12。手动计算1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19。共12个1十位10个个位2个。包含连续1n 111。这是一个很好的测试因为高位、当前位、低位都涉及1容易在计算high和low时混淆。当前位为0n 100。重点测试cur 0的分支。当前位大于1n 222。测试cur 2的分支。大数边界n 10^9。确保循环不会溢出或死循环。在Python中整数不会溢出但要注意digit的增长。幂次边界n 999n 1000。这些数字在进位点容易出错。我强烈建议你在编写代码时同时写一个暴力法的函数仅用于小范围测试。然后写一个测试循环比如for i in range(1000): assert countDigitOne(i) countDigitOne_naive(i)。当小范围测试通过后你对算法的信心会大大增强。调试时可以在循环内加入打印语句观察每一步的high,cur,low,digit和累加中的count值。例如对于n13digit1, high1, cur3, low0 - cur1: count (11)*1 2 digit10, high0, cur1, low3 - cur1: count 0*10 (31) 4 总count6。通过这样的跟踪你可以清晰地看到每一位的贡献是如何计算的。6. 举一反三解决“数字 2 出现的次数”与数位DP思想如果你彻底理解了 LeetCode 233 的解法那么解决同类问题就易如反掌。比如题目改成“统计数字 2 出现的次数”代码需要改哪里答案是几乎不用改我们之前计算的是当前位为 1 的贡献。如果要计算当前位为k例如 2的贡献逻辑完全一样只需要把分情况判断中的“固定当前位为 1”改成“固定当前位为k”即可。更具体地说在分情况讨论时当cur k时高位不能取到high否则数字会超贡献为high * digit。当cur k时贡献为high * digit (low 1)。当cur k时贡献为(high 1) * digit。 看只是比较的对象从 1 变成了k。这体现了我们解法的高度通用性。更进一步这其实是一种简化版的**数位动态规划Digit DP**思想。标准的数位DP通常用于解决“区间 [L, R] 内满足某种条件的数字个数”问题其核心是将数字按位拆分并考虑“前几位是否已经小于上限”这个状态即tight状态。而我们这道题的解法巧妙地避开了DP的状态转移直接通过数学分析得到了封闭解。因为它统计的是“出现次数”而不是“数字个数”并且条件某一位为1相对简单。理解了这个联系当你遇到更复杂的问题比如“统计 [1, n] 中数字 1 出现次数为偶数的数字有多少个”时你就会知道需要引入更完整的状态当前位、是否紧贴上界、当前已统计的1的个数的奇偶性并使用记忆化搜索来实现。LeetCode 233 可以说是通往数位DP世界的一块绝佳的敲门砖。7. 面试实战要点与高频易错点剖析这道题是国内外大厂面试中的高频题尤其是对中级及以上岗位的考察。面试官不仅想看到你写出代码更想考察你的思维过程、沟通能力和对细节的把握。以下是我总结的面试实战要点和候选人最容易翻车的地方面试叙述逻辑先澄清问题复述题目确认输入输出和边界条件n 的范围、非负整数、从1开始还是从0开始。分析暴力法及其局限明确指出O(n log n)复杂度不可行点明需要数学优化。引入核心视角“我们可以换个角度不枚举每个数字而是枚举每一位个、十、百...分别计算这一位上出现1的次数然后求和。”举例推导拿一个具体数字如3101592选一位如百位在白板上画出high | cur | low的结构。分cur0,1,1三种情况详细解释每种情况下高位和低位的组合方式如何贡献了当前位为1的数字个数。这一步是重中之重一定要讲得慢而清晰。归纳公式将三种情况用条件语句描述出来而不是强行合并成一个晦涩的公式。描述算法步骤说明如何从低位到高位循环提取high, cur, low根据cur值累加贡献。复杂度分析时间复杂度O(log n)空间复杂度O(1)。编写代码边写边讲特别是high, cur, low的计算公式。测试用n13, n20, n111等例子快速验证。高频易错点high和low计算错误这是最最常见的错误。记住high n // (digit*10)low n % digit。很多人会写成high n // digit // 10这在逻辑上等价但不如直接除以digit*10直观且不易错。循环条件错误使用while digit n在某些情况下会导致多循环一次当 n 的位数很高时。使用while n // digit 0更安全它直接判断是否还有高位需要处理。整数溢出在 C 或 Java 中digit * 10可能导致int溢出尽管本题n 10^9digit最大为10^9再乘10就溢出了。安全的做法是使用long long类型来定义digit。在 Python 中则无需担心。忽略 n0 的情况题目要求统计小于等于 n 的非负整数。当 n0 时结果为 0。需要在函数开头处理。对“贡献”理解不透彻尤其是在cur 1的情况下low 1这个部分很多人会忘记1因为低位从 0 开始计数。提示在面试编码时即使你心里知道公式也建议显式地写出if cur 0: ... elif cur 1: ... else: ...这样的分支结构。这比写一个浓缩的、难以解释的一行表达式更能体现你清晰的逻辑也方便面试官理解。代码的可读性在面试中至关重要。8. 性能对比与算法选择背后的思考最后我们来直观感受一下不同方法的性能差异并思考为什么“按位贡献法”是此类问题的最优解。假设n 10^9十亿暴力法需要循环 10^9 次每次循环内部还有一个while循环平均约 log10(n) ≈ 9 次操作。总操作数约 10^10 量级。在任何编程语言中这都需要数秒甚至数分钟在 OJ 系统上必然超时通常时间限制为 1-2 秒。按位贡献法只需要循环 log10(n) ≈ 10 次。每次循环进行几次除法、取模和乘法运算都是O(1)操作。总操作数在 100 次以内瞬间完成。这种性能上的天壤之别正是算法设计的魅力所在。它告诉我们面对一个看似需要“遍历”的问题如果能够找到问题的内在数学规律将计算量从与输入值n线性或更差的关系降低到与n的位数即log n相关这就是质的飞跃。这类“数位统计”问题在计算机科学中属于“组合数学”或“数论”与算法的交叉领域。其核心思想是分类计数和乘法原理。我们通过固定某一位的数字将问题分解为高位和低位的独立选择问题再利用乘法原理计算组合数。这种“分而治之”的思想在算法设计中无处不在。掌握 LeetCode 233 这道题其意义远超过一道题本身。它训练了你以下几种关键能力问题转化能力将“统计所有数字”转化为“统计每一位的贡献”。数学建模能力用high, cur, low精确描述数字结构并分析组合情况。边界处理能力细致处理cur等于 0、1、大于 1 的三种情况以及n0的边界。从特例到通解的抽象能力理解了本题就能轻松解决统计其他数字0-9的问题。在实际工作中这种通过寻找数学规律来优化暴力解法的思维模式极其宝贵。它可能出现在性能优化、数据分析、甚至是系统设计的场景中。下次当你遇到一个需要遍历大量数据的任务时不妨先停下来想一想我是否必须逐个处理数据之间是否存在某种规律或公式可以让我批量计算这道“数1”的难题就是培养这种思维习惯的绝佳起点。