LeetCode 788旋转数字：从暴力到数位DP，面试必看解法全解析

一次模拟面试里对方给我出了LeetCode 788旋转数字。我第一反应是这不就是个Easy题吗结果写的时候边界条件错了两处写完又被追问“N到10^9还能不能跑”一句话把我问住了。后来我把这道题重新梳理了一遍才发现它被列为“面试必看”是有道理的——它正好压在“模拟能力、数位建模、复杂度预判”三个考点的交叉点上而且不同解法之间的差距恰恰反映了候选人是在背题还是在理解题。这篇文章我就把这道题从暴力到数位DP的完整思路、代码、以及面试现场容易被追问的点一次性讲透。1. 为什么面试官偏爱这道“旋转数字”从题目设置看考点1.1 题目到底在问什么先看原题描述给定一个正整数N统计从1到N之间有多少个数把这个数每一位旋转180度之后仍然是一个有效数字并且旋转后的数不等于原数这样的数称为“好数”。旋转规则是固定的原数字旋转180度后类型00旋转后等于自身11旋转后等于自身88旋转后等于自身25旋转后变成另一个数字52旋转后变成另一个数字69旋转后变成另一个数字96旋转后变成另一个数字3无效旋转后不是数字4无效旋转后不是数字7无效旋转后不是数字换句话说每一位数字只会落入三种状态旋转后是自己0/1/8、旋转后变成另一个有效数字2/5/6/9、旋转后直接失效3/4/7。一个数要成为“好数”必须满足两个条件所有位都落在前两类里没有3/4/7并且至少有一位落在第二类里否则旋转后等于原数。这两个条件缺一不可很多人第一次写就挂在第二个条件上。1.2 三个隐藏考点映射建模、双条件判断、复杂度意识面试官选这道题通常不是考你知不知道旋转规则而是看三件事。第一能不能把一个“新定义的规则”快速翻译成代码逻辑。旋转映射本质上是自定义了一个函数f(d)输入0到9的数字输出是数字或非法标记。你需要决定用什么数据结构表示这个映射数组、字典、还是switch分支。这个选择反映出你的建模习惯数组下标映射通常最直接。第二能不能识别出“旋转后不等于原数”是一个需要单独维护的状态。不少候选人遍历每个数时只检查了“每位旋转后有效”然后直接把所有由0/1/8组成的数也算了进去导致答案偏大。这个错误非常典型因为示例里N10时0、1、8三个数都会被误计入。第三能不能主动分析复杂度。暴力解法需要遍历1到N每个数对每个数逐位取模检查时间复杂度是O(N log N)。如果N是10^4无所谓但如果面试官把N改成10^9暴力就一定超时。这时候你有没有能力切换到数位DP或组合统计是这道题真正的分水岭。2. 暴力解法踩坑实录不是不能写而是写完后答不上来2.1 逐位检查的第一版实现暴力解法本身不复杂但它是理解后续优化方案的基石。先看我第一次写的代码def rotatedDigits(n: int) - int: # rotate[d] 表示数字 d 旋转之后的结果 # -1 表示旋转后不是有效数字 rotate [0, 1, -1, -1, -1, 2, 9, -1, 8, 6] ans 0 for x in range(1, n 1): y x valid True changed False while y 0: d y % 10 if rotate[d] -1: valid False break if rotate[d] ! d: changed True y // 10 if valid and changed: ans 1 return ans逻辑很简单对每个数x不断取最低位d查映射表。如果某一位旋转后无效直接标记valid为False并退出内层循环如果某一位旋转后和自己不同说明这个数旋转后会发生变化置changed为True。最后只有valid和changed同时为True才计数。这一步最容易错的点是内层循环里的break。一旦发现某一位是3/4/7这个数已经不可能成为好数后面的位不用再看了直接跳出。如果不break只是把valid置False结果其实一样但会多做一些无用取模运算。面试时可以顺手提一句“这里可以提前退出”显得对性能敏感。2.2 剪枝优化与“提前退出”暴力解法也不是完全没优化空间。除了内层提前退出之外还可以在外层加一个条件如果某个数含有3/4/7它的任何整数倍或高位扩展也都含有这些位这个观察不严格因为乘法和拼接不同不能直接用来剪枝。真正有效的优化思路是反过来做与其遍历所有数再判断不如枚举所有“每位都在{0,1,2,5,6,8,9}中”的数再从中排除“每位都在{0,1,8}中”的数。这样候选集从N个数缩小到7^k数量级k是N的位数。比如N10^6时暴力要遍历100万个数而候选集合只有7^7约82万个虽然量级没变但常数小一些而且这个思路天然指向后面的数位DP。还有一种更常见的优化是位数剪枝如果N本身只有k位那么所有位数小于k的数都直接按组合数学公式计算只有k位数需要真正逐位检查。这也是第4节会展开的做法。2.3 复杂度不达标时该怎么坦诚回答这里说点面试技巧。如果你先写了暴力解法面试官问“能不能优化”千万不要说“这个解法够了”或者“我想想但没想出来”这两种都减分。比较稳的回答方式是“暴力解法的时间复杂度是O(N log N)空间O(1)。当N到10^4时完全没问题但N变大后主要瓶颈是遍历了太多不可能成为好数的数字。接下来我可以从高位到低位做数位DP把状态压缩成‘每一位是否可用’和‘是否已经出现改变数字’两个维度复杂度降到O(log N)。需要我写一下吗”这段话展示了你对复杂度的敏感也对优化方向有清晰判断。相比之下直接甩出数位DP代码但不解释为什么这样做反而容易被追问到原理时卡壳。3. 数位DP正解把“逐个数检查”压缩成“逐位状态叠加”3.1 状态设计tight、greater0、changed三个维度的含义数位DP的核心思路是不要再逐个检查数字而是从高位到低位一位一位地“构造”数字同时维护几个关键状态pos当前处理到第几位从0开始。tight前几位是否已经和N的对应前缀完全相等。如果tight为True当前位最大只能取N在当前位的数字如果为False当前位可以取0到9。greater0是否已经出现过非零位用来处理前导零。数字0本身不是好数旋转后等于自己且没有改变位所以前导零不能参与changed状态的计算。changed到目前为止是否已经出现过2/5/6/9中的任意一个数字。如果整个数都由0/1/8组成旋转后等于自己不是好数。有人会问为什么需要greater0这个维度因为前导零在数字表示上不占位例如数字5在三位数表示下是“005”但旋转“005”时前导零不应该被计入“旋转后等于自身”的判断。如果直接把0当作一位有效数字那么数字5会被错误地认为包含一个0位虽然对changed状态没有影响0不是改变数字但在结束判断时会影响“是否出现了非零数字”。为了避免这种混淆常规做法是用greater0标记是否已经开始记录有效位。3.2 记忆化搜索代码与逐行解析用Python的lru_cache实现记忆化搜索是目前最易读的写法from functools import lru_cache def rotatedDigits(n: int) - int: s str(n) # 旋转映射表 rotate { 0: 0, 1: 1, 8: 8, 2: 5, 5: 2, 6: 9, 9: 6 } invalid {3, 4, 7} lru_cache(None) def dfs(pos: int, tight: bool, greater0: bool, changed: bool) - int: # 所有位都处理完了 # 是一个有效数字greater0为True且至少有一位发生了改变 if pos len(s): return 1 if greater0 and changed else 0 up int(s[pos]) if tight else 9 total 0 for d in range(up 1): ch str(d) if ch in invalid: continue next_tight tight and (d up) # 前导零还没开始正式的数字位 if not greater0 and d 0: total dfs(pos 1, next_tight, False, False) continue # 普通数字位 nd rotate[ch] total dfs( pos 1, next_tight, True, changed or (ch ! nd) ) return total return dfs(0, True, False, False)逐个说明几个关键点第一invalid数字直接跳过。3/4/7旋转后不是数字所以任何包含它们的数都没有资格成为好数在枚举当前位时直接continue。第二前导零处理。如果greater0为False且当前选0那么这一位只是占位不能把changed置为True因为0不是改变数字也不把greater0改为True。等真正遇到第一个非零位时才表示数字开始。第三changed的传递。当前位的旋转结果nd和自身ch不同说明这一位是个“改变位”ch ! nd为True那么后续所有分支都会带上changedTrue。注意这里是逻辑或一旦某一位出现过改变整个数的changed状态就固定为True。第四tight的传递。只有当前tight为True且d恰好等于N的当前位next_tight才为True。一旦某一位取了更小的值后面所有位都不受N限制了。这个逻辑是所有数位DP的通用骨架面试里其他题目也能复用。3.3 边界情况前导零、数字0、全程未进入“变数”跑几个边界用例验证代码正确性N10时逐个看1到101旋转后是1不是好数2旋转后是5好数5旋转后是2好数6旋转后是9好数9旋转后是6好数10里包含1和0旋转后还是10不是好数3/4/7无效。所以答案是4。N1时1旋转后等于自己答案0。N2时1不是好数2是好数答案1。N100时可以先手算一部分所有只由0/1/8组成的两位数比如11、18、81、88等都不能算而像12、15、16、19等只要带一个2/5/6/9并且不含3/4/7就是好数。尤其要注意数字0本身。0旋转后是0而且没有任何一位发生改变所以0不是好数。在dfs结束条件里如果greater0为False即整个数字都是0最后返回0这正好排除了0。很多暴力解法如果从0开始遍历且没做排除会把0误计入答案。另外还有一个隐藏的边界N0。题目说N是正整数但如果你在本地测试传0返回值应该是0因为1到0之间没有任何数。dfs会正常处理这个情况返回0不会有越界问题。4. 线性递推与分类统计另一种应付追问的写法4.1 “好数 可用数字组成 – 纯自身旋转数字”的数学视角数位DP不是唯一正解还有一种更偏数学的统计方法在面试追问“还有没有别的办法”时非常好用。把所有数字分成三个集合A {0, 1, 2, 5, 6, 8, 9}旋转后仍是合法数字B {0, 1, 8}旋转后等于自身且本身合法G {2, 5, 6, 9}旋转后变成另一个合法数字那么“好数”可以看成每一位都在A中并且至少有一位在G中。如果某数每一位都在B中旋转后等于原数不是好数如果某数有一位在G中其余位在A中就是好数。所以长度为k允许前导零的A类数字集合中好数数量等于A类数字总数 - B类数字总数 7^k - 3^k注意这里的“长度k”指的是严格的k位数字且第一位不能是0。如果第一位可以是0那么等号右边的公式要调整为第一位的情况。4.2 长度统计法的递推实现如果N正好是10^k - 1比如N9999那么所有k位及以下的数字都可以直接用公式算。但N是任意数时需要从高位到低位累加。一个可行的递推实现如下枚举每一位时统计当前位取小于N当前位的可选数字后剩余位数有多少种补全方式。这里关键在于维护“已经出现过G中数字”的状态def rotatedDigits_math(n: int) - int: s str(n) m len(s) # 预处理幂次powA[k] 7^k, powB[k] 3^k powA [1] * (m 1) powB [1] * (m 1) for i in range(1, m 1): powA[i] powA[i - 1] * 7 powB[i] powB[i - 1] * 3 A {0, 1, 2, 5, 6, 8, 9} B {0, 1, 8} G {2, 5, 6, 9} ans 0 appeared_g False # 前面已经出现过的位中是否有 G 数字 for i, ch in enumerate(s): limit int(ch) remain m - i - 1 # 当前位之后还有多少位 for d in range(limit): if d not in A: continue # 当前这位选了 d剩余 remain 位任意填 A 中数字 # 情况1之前或当前已经出现过 G 数字 # 那么剩余位随便填 A 中数字即可共 7^remain 种 if appeared_g or d in G: ans powA[remain] # 情况2之前和当前都没有 G 数字 # 那么剩余位必须至少出现一个 G 数字 # 总数 - 全是 B 数字的数量 else: ans powA[remain] - powB[remain] # 当前位如果只能取 limit 本身继续处理下一位 if limit not in A: break if limit in G: appeared_g True return ans这个方法的时间复杂度是O(m * 10)空间O(m)本质上和数位DP相同但代码更难读懂因为它把“枚举当前位”和“组合数计算”混在了一起。我在面试中不会优先写这个版本更推荐用它来验证数位DP的结果是否正确——尤其是N随机取几个值两个方法跑出来一致代码就基本可信。4.3 与数位DP对比什么场景下用哪个维度暴力遍历数位DP数学组合计数时间复杂度O(N log N)O(log N * 10)O(log N * 10)空间复杂度O(1)O(log N)缓存O(log N)幂表实现难度低中高可扩展性差强中适合场景N很小N很大、规则复杂N是整幂次、需要快速估算从面试角度数位DP是“通法”几乎所有“统计区间内满足某性质数字个数”的题都能套组合计数更偏“灵光一闪”写对了很加分但实现过程中状态容易漏。我的建议是数位DP作为主解组合计数作为口头补充向面试官展示你能从两个角度理解同一道题。5. 现场易错点与自查清单写代码时最容易翻车的三个地方5.1 映射表必须区分方向2变5而不是5变2旋转映射看起来简单但方向很容易弄反。数字2旋转180度后是5反过来5旋转180度后是2两者都合法但如果你在映射表里写成rotate[2]2、rotate[5]5那changed状态就永远不会被正确标记。我的习惯是把映射表写成四个“改变对”2-5、5-2、6-9、9-6再加三个自映射0、1、8。写代码前先把这个表在纸上列出来再动手。实测下来方向错误是这类题最高发的错误而且很难用少量样例测出来因为2和5都好数判定依然成立只是旋转后的值不对——但本题不要求你输出旋转后的数只要求判断是否“不等于原数”所以方向反了有时反而能过样例。这里要注意如果你把2映射成2、5映射成5changed永远为False在N较小时的样例里比如N10答案4就会挂。而如果把2映射成5、5映射成2但6映射成6、9映射成9答案会多算6和9同样出错。所以写完一定要用N10验证答案是4而不是其他数。5.2 changed条件千万不能丢全是0/1/8的数字是陷阱很多暴力解法犯的错误是只判断“每位旋转后是否有效”忘记了“旋转后必须不等于原数”。这样会把1、10、11、18、81、100等全部误判为好数。在数位DP里这个条件体现在结束判断里必须有changed为True或者最后一位的changed状态必须为1。在前面的记忆化搜索中结束条件是if pos len(s): return 1 if greater0 and changed else 0如果你把changed删掉只判断greater0答案会被严重高估。写完之后用一个简单的测试N20手动列出好数2、5、6、9、12、15、16、19。答案是8。如果你的程序算出更多大概率就是漏了changed条件。5.3 前导零对changed状态的影响前导零是另一个隐蔽的坑。假设N105数字5本身是好数。在数位DP中数字5的枚举路径是pos0选0前导零、pos1选0前导零、pos2选5。如果在枚举pos1时你把0当成有效的“数字位”并更新changed由于0不是改变数字changed仍然是False不会出错但如果你把0当作“和自身相同”的数字并更新了某类状态问题就来了——比如有人会把greater0误置为True导致pos2结束时把“0”这种前导零当成了一个实际位数字5会被错误地认为包含了一个0位虽然0不影响changed但会影响一些依赖位数的统计逻辑。我的习惯是前导零分支单独处理不进入常规数字位逻辑。这样代码虽然多一行但思路清晰面试时也更容易向面试官解释“前导零永远不会被当作数字的一部分”。6. 从788向外扩散面试追问里的变形与扩展6.1 变形一统计旋转后小于原数的个数面试官可能不满足于原题顺手把条件改成“统计1到N中旋转180度后得到的数小于原数的个数”。这个变形会改变判定逻辑原来你只需要关心“是否不等于原数”现在要逐位比较旋转结果和原数的大小。思路仍然是数位DP但状态里要增加两个标志相等前缀是否保持、以及当前位旋转后与原位的大小关系。具体来说从高位往低位走维护一个状态表示“前面所有位的旋转结果和原数前缀是否完全相等”。如果相等当前位需要比较旋转后的数字nd和原数字d如果nd d那么后面无论怎么填旋转结果都会大于原数这个分支可以直接剪掉如果nd d后面任意填都满足小于如果nd d继续往后看。这样状态里加一个tie标志就够了。这个变形的难度比原题高一档因为它要求你真正理解“旋转”这个动作是对每一位做映射而不仅是判断是否相等。6.2 变形二N超大时的矩阵快速幂思路如果N达到10^18甚至10^100数位DP的O(log N)仍然可行只要N用字符串表示。但如果你想统计的不是“1到N”而是“长度为k的所有好数数量”且k非常大比如10^9那你需要把递推关系写成矩阵的幂。具体来说状态只有两个维度当前已构造前缀中是否已经出现过改变数字G。转移矩阵可以写成当前状态下一位选什么新状态无G选B数字(0/1/8)无G无G选G数字(2/5/6/9)有G有G选A数字(0/1/2/5/6/8/9)有G三行转移可以编码成2x2矩阵然后用快速幂在O(log k)时间内算出长度为k的好数个数。这个方向属于拔高题一般面试不会现场要求但如果你主动提出来会是个很好的加分点。6.3 对比题组反转数字、回文数、数位1的个数把788放进更大的题组里看它和几道经典题共享同一套数位思维LeetCode 7“整数反转”翻转整个数字而不是逐位旋转考察溢出的处理。LeetCode 9“回文数”判断正反读是否相同和788一样需要处理“旋转后等于自己”的情况但回文只要求整体比较。LeetCode 233“数字1的个数”同样是数位DP的经典题状态维度变成“当前位是否为1”和“前面1的个数”。LeetCode 902“最大为N的数字组合”给了digit集合和N统计由集合中数字组成的小于等于N的数量和788的候选集合方法几乎同构。如果你能把788和902放在一起看就能提炼出一个通用套路给定数字集合和N统计满足条件的数——第一步判断集合中每个数字是否可用第二步从高位到低位数位DP第三步处理前导零和边界。这个套路掌握之后再遇到任何“数字组成”类题目十分钟内都能写出框架。我个人在实际面试辅导中见过很多候选人暴力解法五分钟写完数位DP二十分钟卡壳最后在changed条件和前导零之间反复改。我自己的建议是不要直接背模板先把“旋转规则”当作一个函数f(d)来理解把“好数”定义拆成两个独立条件再想状态转移。这样即使面试官临时改条件你也能基于理解而不是记忆给出新的递推关系。最后可以再用一个N20的小样例验证答案是否为8确认无误后再提交能少走很多弯路。