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位从个位开始k0表示个位k1表示十位依此类推。我们需要一个“因子”factor来表示当前位的权重即factor 10^k。例如对于十位k1factor 10。对于任意一个数字n我们可以根据当前位factor将其拆分为三个部分高位highn // (factor * 10)当前位cur(n // factor) % 10低位lown % factor以n 31025, factor 100 (即考察百位k2)为例high 31025 // 1000 31cur (31025 // 100) % 10 0low 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, factor100此时high31, cur1, low25。 这种情况下数字可以分成两部分高位从0 ~ (high - 1)这部分和情况一相同贡献为high * factor。高位等于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, factor100此时high31, cur2, low25。 此时高位可以从0 ~ high中取值注意这里包括了high。因为即使高位取到high31当前位是2仍然大于1所以高位为high时当前位取1是允许的即数字31100~31199。 对于每一个确定的高位有high 1种选择0,1,...,31低位可以取0 ~ (factor - 1)之间的任意值。 因此总贡献为(high 1) * factor。 在我们的例子中贡献 (31 1) * 100 3200。核心理解这三种情况的核心区别在于高位取到最大值high时是否还能保证当前位为1。cur0时不能cur1时部分能取决于低位cur1时完全能。把握住这一点公式就很好记忆了。3. 算法实现与逐行解析理解了数学原理代码实现就非常清晰了。我们将使用迭代的方式从个位开始逐位计算贡献直到遍历完n的所有位。def countDigitOne(n: int) - int: count 0 factor 1 # 从个位开始因子为10^01 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逐行解析与注意事项初始化 (high, cur, low)我们初始时将n的个位作为cur其余部分作为highlow初始为0。这种初始化让循环逻辑统一。循环条件 (while high ! 0 or cur ! 0)这个条件确保了即使n0循环也会因为cur0且high0而直接跳过返回count0这是正确的。对于任何n0循环都会处理到最高位。核心计算部分直接对应我们前面分析的三种情况。这是算法的核心务必理解每个变量的含义。更新部分最容易出错的地方low cur * factor这是关键。当前轮次的cur和factor决定了当前位的实际数值。在下一轮处理更高位时当前位就变成了“低位”的一部分。例如处理完个位后个位的值cur需要加入到low中以便在处理十位时low代表的就是原始的个位数。cur high % 10获取新的当前位原高位的最后一位。high // 10去掉原高位的最后一位得到新的高位。factor * 10因子进位准备处理下一位十位、百位...。边界情况处理该算法天然处理了n0和n为最大整数如2^31-1的情况因为循环逻辑和数学公式是普适的。一个完整的计算示例n13我们来手动模拟一下验证结果是否为6。初始factor1, high1, cur3, low0第一轮处理个位factor1:cur3 1贡献 (high 1) * factor (11)*1 2。这对应个位为1的数字1, 11。注意此时11的十位还未处理。更新low 0 3*1 3,cur high%10 1%10 1,high 1//10 0,factor10。第二轮处理十位factor10:cur1贡献 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,factor100。循环结束high0且cur0。总贡献 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的贡献。分为几种情况如果d ! 0当cur d时高位只能取0 ~ (high - 1)贡献为high * factor。当cur d时贡献为high * factor low 1。当cur d时高位可以取0 ~ high贡献为(high 1) * factor。 这和“数1”的公式完全一致因为“数1”就是d1的特例。如果d 0这是唯一需要特殊处理的情况因为数字不能有前导零。例如数字05通常被视为5其十位上的0不应被计数。当cur 0时高位可以取0 ~ (high - 1)等等这里需要小心。对于d0当高位为0时当前位是0属于前导零不应计数。因此高位实际上只能从1开始取。所以贡献为(high - 1) * factor (low 1)不更严谨的分析如下高位部分高位至少为1。当cur 0高位可以从1 ~ high取值如果high 0。但注意当高位取high时当前位是cur它大于0所以当前位为0的情况只可能发生在高位小于high的时候。因此贡献为(high) * factor让我们用例子检验。 实际上对于d0且cur 0当前位为0意味着这个数字的高位部分不能等于当前的high否则当前位就是cur而不是0。所以高位只能取0 ~ (high-1)但高位为0时可能产生前导零问题吗不会因为当前位是0但高位是0整个数字可能就是像0...0xyz这样的形式其中第一个非零位在当前位之后。例如n1024考察十位(factor10,cur2)统计十位为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的情况进行后处理减去前导零的计数。或者直接修改公式当d0时高位的有效范围是1 ~ high如果当前位不是最高位则高位可以从0开始但高位为0时表示这个数字的位数比当前位少当前位上的0是有效的中间位零吗是有效的例如数字5在十位上看就是0。这很绕。鉴于d0情况的复杂性一个更稳妥、更清晰的通用解法是分别统计1~n中每个数字0~9的出现次数可以调用countDigitOne的函数逻辑但对d0做特殊判断或者直接遍历统计。对于面试而言能清晰阐述d0的通用性并指出d0的特殊性已经足够展示深度。4.2 算法复杂度与优化空间我们实现的countDigitOne算法时间复杂度是O(log n)因为循环次数等于数字n的位数以10为底。空间复杂度是O(1)只使用了几个整型变量。这已经是这个问题的最优解法。潜在的优化与注意事项整数溢出在 Python 中不存在整数溢出问题但在 Java、C 等语言中factor和(high 1) * factor这类计算在n很大时如n2^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就已经是下一轮的值了必然出错。调试技巧对于n10, 11, 101, 110这样的边界值使用纸笔或调试器一步一步跟踪high,cur,low,factor,count的变化与手动计算的结果对比。5.2 问题二如何处理输入 n0 的情况我们的算法中循环条件while high ! 0 or cur ! 0在n0时初始high0, cur0循环不会进入直接返回count0这是符合要求的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的出现次数是本题的难点。在面试中如果被问到建议采取以下策略首先给出统计d1~9的通用解法强调其与本题解法的同构性。指出d0的特殊性在于“前导零”不应计数。可以提供两种思路思路A推荐分别统计1~n中每一位上0~9的出现次数。对于非最高位0可以正常出现对于最高位0不会出现。这需要更细致的分类讨论。思路B取巧利用总和不变的性质。先计算1~n所有数字的位数总和即total_digits sum(len(str(i)) for i in range(1, n1))然后计算数字1~9出现的总次数sum_count_1_to_9那么数字0出现的次数就是total_digits - sum_count_1_to_9。但这个方法需要计算位数总和可能并不比直接统计简单。实操建议如果面试官追问可以和他/她确认“您希望我详细推导d0的复杂情况还是先确保d1~9的通用解法完全正确” 这既展示了你的沟通能力也体现了你对问题复杂度的认知。最后这道“困难”题的价值不在于记住一个公式而在于掌握将大规模计数问题分解为独立数位贡献的思想。下次当你遇到需要统计满足某种条件的数字个数且条件与数位相关时不妨想想我能不能像解这道题一样单独考虑每一位这种思维训练远比AC一道题本身重要得多。我在解决一些实际的数据分析任务时就曾运用这种思想高效统计了日志中特定模式出现的频次其核心就是将模式匹配转化为按位独立的概率或计数问题。