企业官网建设流程全解析

一次模拟面试里，对方给我出了LeetCode 788旋转数字。我第一反应是：这不就是个Easy题吗？结果写的时候，边界条件错了两处，写完又被追问“N到10^9还能不能跑”，一句话把我问住了。后来我把这道题重新梳理了一遍，才发现它被列为“面试必看”是有道理的——它正好压在“模拟能力、数位建模、复杂度预判”三个考点的交叉点上，而且不同解法之间的差距，恰恰反映了候选人是在背题还是在理解题。这篇文章我就把这道题从暴力到数位DP的完整思路、代码、以及面试现场容易被追问的点，一次性讲透。

1. 为什么面试官偏爱这道“旋转数字”：从题目设置看考点

1.1 题目到底在问什么

先看原题描述：给定一个正整数N，统计从1到N之间有多少个数，把这个数每一位旋转180度之后，仍然是一个有效数字，并且旋转后的数不等于原数，这样的数称为“好数”。

旋转规则是固定的：

换句话说，每一位数字只会落入三种状态：旋转后是自己（0/1/8）、旋转后变成另一个有效数字（2/5/6/9）、旋转后直接失效（3/4/7）。一个数要成为“好数”，必须满足两个条件：所有位都落在前两类里（没有3/4/7），并且至少有一位落在第二类里（否则旋转后等于原数）。这两个条件缺一不可，很多人第一次写就挂在第二个条件上。

1.2 三个隐藏考点：映射建模、双条件判断、复杂度意识

面试官选这道题，通常不是考你知不知道旋转规则，而是看三件事。

第一，能不能把一个“新定义的规则”快速翻译成代码逻辑。旋转映射本质上是自定义了一个函数f(d)，输入0到9的数字，输出是数字或非法标记。你需要决定用什么数据结构表示这个映射：数组、字典、还是switch分支。这个选择反映出你的建模习惯，数组下标映射通常最直接。

第二，能不能识别出“旋转后不等于原数”是一个需要单独维护的状态。不少候选人遍历每个数时只检查了“每位旋转后有效”，然后直接把所有由0/1/8组成的数也算了进去，导致答案偏大。这个错误非常典型，因为示例里N=10时，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的位数。比如N=10^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，那么后续所有分支都会带上changed=True。注意这里是逻辑或，一旦某一位出现过改变，整个数的changed状态就固定为True。

第四，tight的传递。只有当前tight为True且d恰好等于N的当前位，next_tight才为True。一旦某一位取了更小的值，后面所有位都不受N限制了。这个逻辑是所有数位DP的通用骨架，面试里其他题目也能复用。

3.3 边界情况：前导零、数字0、全程未进入“变数”

跑几个边界用例验证代码正确性：

• N=10时，逐个看1到10：1旋转后是1，不是好数；2旋转后是5，好数；5旋转后是2，好数；6旋转后是9，好数；9旋转后是6，好数；10里包含1和0，旋转后还是10，不是好数；3/4/7无效。所以答案是4。
• N=1时，1旋转后等于自己，答案0。
• N=2时，1不是好数，2是好数，答案1。
• N=100时，可以先手算一部分：所有只由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误计入答案。

另外还有一个隐藏的边界：N=0。题目说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，比如N=9999，那么所有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是“通法”，几乎所有“统计区间内满足某性质数字个数”的题都能套；组合计数更偏“灵光一闪”，写对了很加分，但实现过程中状态容易漏。我的建议是数位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映射成5，changed永远为False，在N较小时的样例里（比如N=10，答案4）就会挂。而如果把2映射成5、5映射成2但6映射成6、9映射成9，答案会多算6和9，同样出错。所以写完一定要用N=10验证答案是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，答案会被严重高估。写完之后用一个简单的测试：N=20，手动列出好数：2、5、6、9、12、15、16、19。答案是8。如果你的程序算出更多，大概率就是漏了changed条件。

5.3 前导零对changed状态的影响

前导零是另一个隐蔽的坑。假设N=105，数字5本身是好数。在数位DP中，数字5的枚举路径是pos=0选0（前导零）、pos=1选0（前导零）、pos=2选5。如果在枚举pos=1时，你把0当成有效的“数字位”并更新changed，由于0不是改变数字，changed仍然是False，不会出错；但如果你把0当作“和自身相同”的数字并更新了某类状态，问题就来了——比如有人会把greater0误置为True，导致pos=2结束时把“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。转移矩阵可以写成：

三行转移可以编码成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)来理解，把“好数”定义拆成两个独立条件，再想状态转移。这样即使面试官临时改条件，你也能基于理解而不是记忆给出新的递推关系。最后可以再用一个N=20的小样例验证答案是否为8，确认无误后再提交，能少走很多弯路。