2015年春季互联网实习招聘的笔试刚全面转向在线答题刷人率比现在还要狠。我记得当时坐在考场里前面的选择题和基础编程题做完还剩大半个小时翻到最后一页看到“附加题”三个字心跳还是快了半拍——附加题从来不是送分题它的存在意义就是把“能进面试的人”和“暂时还差点意思的人”区分开。后来这些年网上关于“百度2015春季实习生招聘附加题”的讨论一直没断过流传最广的版本是这道给出一个正整数N统计从1到N的所有整数中数字1出现的次数。乍一看这不就是数数题吗但你要是真的写个循环从1数到N笔试系统会教你做人。这道题后来成了LeetCode第233题也是《剑指Offer》面试题43的原型很多公司算法面试题库里的常客。这篇文章我就把这道题从头到尾拆一遍顺便聊聊我当时在考场上是怎么从“暴力遍历”一路改到“按位统计”的以及这类附加题背后到底想筛什么。1. 先把这个附加题的真实面貌盘清楚1.1 网上流传的版本与完整题目描述先说清楚一件事当年那套题里附加题不止一道网上流传的版本也确实存在差异。我在论坛和博客里看到的复盘帖有人回忆的是“两个栈实现队列”这类数据结构题也有人回忆的是“给定一个数组把所有数字拼接起来组成一个最大数”而讨论热度最高、几乎每年校招季都会被翻出来的是“统计数字1出现次数”这道。后来我专门查过它在LeetCode上的编号是233英文原题叫Number of Digit One中文一般叫“数字1的个数”。2015年前后它在国内校招笔试里出现频率极高百度只是众多使用者之一。我把流传版本整理成规范一点的题目描述输入一个正整数NN可以大到10^9甚至更大输出1到N之间所有整数中数字字符“1”出现的总次数。注意是次数不是个数——比如11贡献的是2次不是1次。给两个小例子N12时从1到12这些数里1、10、11、12里面出现的“1”分别有1、1、2、1个合计5所以输出5N13时加上13里面的1就是6。这两个小例子必须心算清楚后面写对拍程序时还要用到。1.2 附加题在整场笔试里的特殊位置说回附加题本身。头部公司的实习生笔试卷子一般分三段前面是选择填空考察基础扎不扎实中间是两到三道编程题考察能不能在规定时间里写出可运行的代码最后的附加题考察的是你在没有标准答案的情况下怎么拆解一个看起来没什么思路的问题。附加题通常不计入总分或者只占很少比重但它有个隐藏作用——面试官翻卷子的时候一眼扫过去看的就是它。基础题会背就能过而附加题能反映一个人面对未知问题时真实的第一反应。如果你时间够附加题值得正面刚如果时间不够至少把暴力解法写出来并在注释里写清楚复杂度分析这比交白卷强太多。这道题之所以被反复提起我觉得不是因为难——它的代码实现只有十几行——而是因为它完美踩中了一个大多数人都有的思维惯性顺序遍历。人看到“从1到N”这种字眼下意识就会想循环而不去想数学结构。这种“题面简单、解法有层次”的特征恰恰是附加题该有的样子。2. 暴力解为什么必挂先算一笔复杂度账2.1 最直觉的写法人人都会先把几乎所有考生都会第一时间想到的暴力解贴出来。逻辑非常简单从1循环到N对每一个数字不断除以10取余判断当前位是不是1累加。写成Java大概是这个样子public int countDigitOneBruteForce(int n) { int count 0; for (int i 1; i n; i) { int temp i; while (temp 0) { if (temp % 10 1) { count; } temp / 10; } } return count; }这段代码正确性没有任何问题N等于12算出5N等于13算出6拿去和手算结果对拍完全一致。问题只出在规模上。笔试的测试数据不会只给你12这么友好的数字附加题更是出了名地喜欢把数据范围拉满。一旦N来到10^9级别暴力循环的代价就完全失控了。2.2 把账算透O(N×位数)到底有多慢设N有d位那么1到N之间最长数字是d位平均位数大约是d。总的位数检查量就是N×d这个量级。具体点说N10^9时d10检查次数大约是100亿次。一台普通笔试用的服务器Java每秒钟能执行的简单循环判断也就几千万到上亿次100亿次意味着几十秒到几分钟。而笔试系统里大部分题目的时限是1秒到2秒超出时限就是0分。我用一张表给你直观感受一下规模变化N数字个数大致位数检查量暴力解法预估耗时10^41万约5万位毫秒级能过10^71000万约7000万位秒级边缘10^910亿约100亿位数十秒必超时10^18百亿亿约1.8×10^19位不可能跑完笔试系统如果拿10^9甚至更大的数据来测暴力解就是死路一条。很多人在这一步栽跟头不是不知道复杂度这个概念而是没有养成“写代码前先问一句数据范围多大”的习惯。附加题的价值就在这里——它逼着你养成这个习惯。2.3 面试官真正想看的是你愿不愿意做这一步跳转我后来问过参与校招命题的朋友他们说这类题在出题时并不指望考生一上来就写出最优解而是希望看到一条清晰的推演路径先暴力再意识到复杂度过高再尝试找规律最终落到数学解法。能不能走到最后一步取决于你愿不愿意停下来多想一会儿。一个很关键的考察点是复杂度分析——有些人甚至不知道自己的暴力解是O(N logN)还是O(N)这比做不出最优解还要致命。写代码前先在草稿纸上写上“暴力法复杂度O(N×位数)优化目标O(logN)”这句话写出来你已经在思维上领先一大截了。后面你会发现这道题的最优解真就只需要循环位数那么多次连10次都不到。3. 按位拆解把数数问题变成小学数学题3.1 从个位出发的小实验要理解最优解我建议你跟我做一个很小的实验。先单独看个位0到9这10个数里个位出现1的次数是10到19里个位出现1的次数是21和110到99里个位出现1的次数是101、11、21一直到91。规律很清楚个位上每10个数一个循环每轮出现一次1。换句话说只看个位的话1到N之间出现的次数大约是N/10再根据余数补一点。再看十位0到99里十位出现1的次数是1010到190到199里十位出现1的次数是200到999里是100。每100个数一个循环每轮十位连续出现10次1。百位同理每1000个数一个循环每轮百位连续出现100次1。到这一步规律已经浮出水面第i位从低位开始数个位是第1位的循环周期是10^i每个完整周期里这一位出现1的次数是10^(i-1)。按位统计的本质就是把每一位的贡献分开算清楚再加起来。3.2 一个具体例子N 2345怎么拆接下来用N2345把公式走一遍。把数字拆成高位、当前位、低位三部分。比如处理十位时high 2345 / 100 23cur (2345 / 10) % 10 4low 2345 % 10 5。十位为1的情况用“整段余段”的思维来拆。完整的100段有23段0到99、100到199、200到299一直到2200到2299。每一段里十位为1的数有10个比如10到19、110到119、2210到2219所以整段贡献23×10230。剩下2300到2345这一段十位从0走到4已经跨过了1这个位置所以十位为1的数还能再贡献10个也就是2310到2319这样就有23010240。用同样的方式处理其他位结果是这样的个位整段234轮每轮贡献1个余段2340到2345包含个位为1的2341再加1总计235。十位上面算了总计240。百位整段2轮0到999、1000到1999每轮贡献100个余段2000到2345里百位为1的是2100到2199正好100个总计300。千位整段0轮但千位为1的数从1000到1999全部在范围内总计1000。合计23524030010001775。这个数就是N2345的正确答案。你拿暴力程序去跑一遍结果一定是1775。3.3 三种情况的分情况讨论用里程表类比讲透如果你仔细观察上面四个位的计算会发现整段贡献永远等于high×10^(i-1)区别只出现在余段。余段怎么处理取决于当前位cur是0、是1还是大于1。我把这个逻辑用里程表类比一下。把N的每一位想象成一个里程表轮盘。当前处理第i位时它每转完一整圈高位就跳一下。我们要统计的是从0走到N的过程中第i位停在1上的次数。低位部分决定的是“这一位停在1的时候后面能走多远”。当前位cur0说明在这一轮里第i位还没走到1就结束了所以只有前面的high个完整周期有贡献结果是high×10^(i-1)。当前位cur1说明第i位刚好停到1上面但低位只走到low。此时除了前面high个完整周期余段里第i位为1的情况还能贡献low1个低位从0到low。当前位cur1说明第i位已经越过1低位可以从0走到满。余段里第i位为1的数能完整走完10^(i-1)个所以总数是(high1)×10^(i-1)。三种情况整理成一张表写代码时直接对照当前位cur含义该位贡献0当前轮还没走过1high×10^(i-1)1当前轮正停在1低位只走到lowhigh×10^(i-1)low11当前轮已经越过1低位可以走满(high1)×10^(i-1)有了这张表整个算法就变成一个for循环从个位开始依次对每一位套公式累加。循环次数等于N的位数复杂度O(logN)空间O(1)。从“遍历10亿个数”到“循环10次”这道题的核心跳跃就在这里。4. 代码落地与边界陷阱4.1 可以直接抄的实现按位统计的代码非常短。我把Java版本贴出来这也是笔试时最容易写对的一版public int countDigitOne(int n) { int count 0; long factor 1; while (factor n) { long high n / (factor * 10); long cur (n / factor) % 10; long low n % factor; if (cur 0) { count high * factor; } else if (cur 1) { count high * factor low 1; } else { count (high 1) * factor; } factor * 10; } return count; }想换成C把int换成long long其他不用动想用Python就更省心整数没有溢出问题直接翻译就行def count_digit_one(n: int) - int: count 0 factor 1 while factor n: high n // (factor * 10) cur (n // factor) % 10 low n % factor if cur 0: count high * factor elif cur 1: count high * factor low 1 else: count (high 1) * factor factor * 10 return count代码逻辑和推导公式一一对应没有什么trick。真正容易出问题的是边界条件和数据类型。4.2 最容易翻车的三个边界问题第一个坑是factor的类型。n是int最高能到21亿左右factor在循环里会从1一路乘到10亿。如果用int存factor当factor1,000,000,000时factor×10会直接溢出成负数循环条件判断就会出错甚至死循环。所以Java和C里factor必须用long。这是血的教训我面试过的一个候选人就在这里栽了代码逻辑全对就是int溢出最后跑出来的结果完全不对。第二个坑是循环边界。while (factor n)这个条件保证最后能处理到最高位。比如n9时factor1处理个位factor10时发现109不成立退出n10时factor1处理个位factor10处理十位factor100退出。如果你把条件写成factorn/10n10时十位就漏掉了这是很隐蔽的错。我的习惯是保持factor从1开始用while (factor n)老老实实写。第三个坑是负数和零。题目说正整数但LeetCode 233的n是非负整数测试用例里可能有0。0应该返回0循环根本不会进入直接返回初始值0天然正确。当n2147483647int最大值时factor最大到10亿factor×10在long里不会溢出。用int存n没问题但所有中间计算结果最好都用long避免任何隐式溢出的可能。4.3 对拍验证证明你的优化解没写错数学推导再漂亮代码也可能是错的。最有效的验证方式是对拍写一个绝对正确的暴力版本然后随机生成小数据用两个函数结果互相对比。这里给一个最小可用的对拍脚本思路import random def brute(n): return sum(str(i).count(1) for i in range(1, n 1)) def formula(n): count 0 factor 1 while factor n: high n // (factor * 10) cur (n // factor) % 10 low n % factor if cur 0: count high * factor elif cur 1: count high * factor low 1 else: count (high 1) * factor factor * 10 return count for _ in range(10000): n random.randint(1, 10000) assert brute(n) formula(n), n print(all ok)把N限制在1到10000暴力解很快。跑一万个随机用例全部通过才能比较放心地提交。这个“对拍”思维不只是对这一道题有用——任何笔试、面试里的算法题写完优化解之后都应该用小数据暴力解验证一遍这是最廉价的debug手段。我见过太多人优化算法写得漂漂亮亮结果在小数据上就错了原因往往是边界情况没过。5. 一道附加题背后的通用笔试方法论5.1 附加题常考的三种思维方向我把那几年各大公司实习笔试的附加题归了一下类发现翻来覆去就是三种套路。第一种是计数类典型代表就是本文这道统计数字1核心是把枚举改成数学归纳用公式把大规模问题压到O(logN)。第二种是排序加贪心比如“给定若干数字拼成一个最大数”核心是自定义比较器而且要能说清楚比较器的传递性。第三种是动态规划比如最大连续子段和、编辑距离核心是写对状态转移方程。考场上遇到附加题先别急着写代码花30秒问自己它属于哪一类如果是计数类我能不能拆位如果是拼数类我能不能排序如果有重叠子问题我能不能DP这一个分类动作就能帮你把陌生题变成熟悉题。5.2 考场上的时间分配策略很多人做附加题失败不是不会做而是时间分配出了问题。我的建议是如果整套题总时长90分钟前60分钟把基础题和编程题全部填满、跑通接下来20分钟留给附加题最后10分钟检查前面的答案。附加题遇到瓶颈时先把暴力解法写上并在注释里标注复杂度这个保底分能拿一定要拿。还有个小技巧笔试系统往往支持按点给分你可以在代码注释里写清楚优化思路哪怕没有实现完整的最优解阅卷时也能看到你的思考过程。我一直觉得附加题考察的是“在压力下解题的路径”而不是“标准答案”。你把暴力解、复杂度分析、优化方向写全即使最终公式实现有bug面试官也能看出你是会做的只是时间不够。5.3 从这道题延伸出去面试连环追问如果你在面试环节被问到这道题面试官大概率会连续追问。第一问统计数字1改成统计数字2公式怎么变答案是cur和1的判断换成2但要注意边界条件因为21的情况永远走第三个分支。第二问统计0出现的次数难度直接上一个台阶——0不能出现在最高位前面不能有前导零所以0的出现次数不是简单套公式需要额外扣掉最高位为0的那些情况。第三问如果N是10^100这种超大数怎么办把N当作字符串处理逐位计算公式不变但要用字符串运算代替乘除法。第四问转成K进制求数字1出现的次数把10^(i-1)换成K^(i-1)思路完全一样。能接住这些问题说明你真的理解了这一套按位统计的逻辑而不是背过一道题。LeetCode上的233题、1067题范围内的数字计数、《剑指Offer》的面试题43都是这道题的不同马甲刷题多的同学应该很眼熟。我自己后来带实习生的时候特别喜欢拿这道题做第一轮技术面试的开场。原因很简单一道题能同时看出一个人愿不愿意先想再写、会不会做复杂度分析、能不能处理边界条件、有没有验证代码的习惯。就信息量而言比很多绕来绕去的难题强多了。回头再看2015年那场笔试我最大的收获不是当天写出了这道附加题而是学会了在拿到任何一道“看起来简单”的题目时先问自己一句数据范围拉满我的解法还活着吗就这一句后来帮我避掉了无数个坑。