企业官网建设流程全解析

LeetCode 788. 旋转数字 详细技术解析（三种解法）

题目难度：简单

题目标签：数组、枚举、动态规划、数学

一、题目概述

1.1 题目定义

我们称一个数 X 为好数，满足两个核心条件：

1. 将 X 的每一位数字旋转 180° 后，能得到一个有效数字（无失效数字）；

2. 旋转后的数字与原数字不相等。

数字旋转规则：

• 有效旋转数字：0、1、8（旋转后不变）；2、5（互为旋转镜像）；6、9（互为旋转镜像）；

• 失效旋转数字：3、4、7（旋转后不是合法数字，包含这些数字的数直接排除）。

给定正整数n，计算区间\[1, n\]内所有好数的数量。

1.2 示例说明

输入：n = 10

输出：4

解释：合法好数为 2、5、6、9。

排除说明：1、10 旋转后数字不变，不满足好数条件；3、4、7 旋转失效，直接排除。

1.3 数据范围

1 ≤ n ≤ 10000，数据量较小，暴力枚举完全可通过，同时可优化动态规划解法适配更大数据。

二、解题核心思路

想要判断一个数是否为好数，必须同时满足两个核心条件：

1. 无非法数字：数字的每一位都不能是 3、4、7；

2. 数字发生变化：数字中至少包含一个2、5、6、9（保证旋转后与原数不同）。

核心逻辑推导：

• 若数字仅由 0、1、8 组成：旋转后数字不变，不是好数；

• 若数字包含 3、4、7：旋转失效，不是好数；

• 若数字仅由 0、1、8、2、5、6、9 组成，且包含 2/5/6/9：是好数。

三、解法一：暴力枚举（基础版）

3.1 算法思路

遍历 1~n 的所有数字，对每个数字逐位校验：

1. 拆分当前数字的每一位；

2. 校验是否存在非法数字（3、4、7），存在则跳过；

3. 校验是否存在可变数字（2、5、6、9），存在则判定为好数；

4. 统计所有符合条件的好数。

3.2 完整代码实现

classSolution:defrotatedDigits(self,n:int)->int:# 定义非法数字、可变数字集合invalid={3,4,7}change={2,5,6,9}res=0# 遍历1到n所有数字fornuminrange(1,n+1):tmp=num has_change=Falseis_valid=True# 逐位拆解数字whiletmp>0:digit=tmp%10# 存在非法数字，直接无效ifdigitininvalid:is_valid=Falsebreak# 存在可变数字，标记为可变化ifdigitinchange:has_change=Truetmp=tmp//10# 有效且发生变化，是好数ifis_validandhas_change:res+=1returnres

3.3 复杂度分析

• 时间复杂度：O(n log n)。遍历 n 个数字，每个数字最多有 log₁₀n 位；

• 空间复杂度：O(1)。仅使用固定变量和集合，无额外空间开销。

四、解法二：暴力枚举（字符串优化版）

4.1 算法思路

将数字转为字符串，直接遍历字符完成校验，替代数学取模拆解，代码更简洁、可读性更高，效率与基础暴力解法基本一致。

4.2 完整代码实现

classSolution:defrotatedDigits(self,n:int)->int:invalid={'3','4','7'}change={'2','5','6','9'}count=0fornuminrange(1,n+1):s=str(num)# 包含非法数字直接跳过ifany(cininvalidforcins):continue# 包含可变数字即为好数ifany(cinchangeforcins):count+=1returncount

4.3 解法优势

代码极简、逻辑清晰，无需数学运算拆解数字，适合刷题快速解题，在本题数据范围内效率最优。

五、解法三：动态规划（进阶优化版）

5.1 算法思路

上述暴力解法存在重复校验问题，可通过动态规划记录每个数字的状态，实现线性时间复杂度。

状态定义：

• dp\[i\] = 0：数字 i 包含非法数字，无效；

• dp\[i\] = 1：数字 i 有效，但旋转后不变（仅由 0、1、8 组成），非好数；

• dp\[i\] = 2：数字 i 有效，且旋转后变化（包含 2、5、6、9），是好数。

状态转移规则：

对于数字i，拆分出个位digit = i % 10，高位pre = i // 10：

1. 若个位是非法数字（3、4、7）：dp\[i\] = 0；

2. 若高位无效（dp[pre]=0）：当前数字无效，dp\[i\] = 0；

3. 若个位是可变数字（2、5、6、9）：当前数字为好数，dp\[i\] = 2；

4. 若个位是不变数字（0、1、8）：状态继承高位，dp\[i\] = dp\[pre\]。

5.2 完整代码实现

classSolution:defrotatedDigits(self,n:int)->int:# dp数组三种状态：0=无效数字 1=有效但旋转不变 2=有效且旋转变化(好数)dp=[0]*(n+1)# 逐个初始化0-9的基准状态，避免直接赋值越界# 0、1、8：有效但旋转后不变# 2、5、6、9：有效且旋转后变化（好数）# 3、4、7：默认0，无效数字，无需赋值status_map={0:1,1:1,2:2,5:2,6:2,8:1,9:2}# 仅初始化不越界的索引fornum,stateinstatus_map.items():ifnum<=n:dp[num]=state res=0# 从1开始遍历所有数字foriinrange(1,n+1):# 拆分当前数字的个位和剩余高位digit=i%10pre=i//10# 规则1：个位是非法数字，整体无效ifdigitin{3,4,7}:dp[i]=0# 规则2：高位部分无效，整体无效elifdp[pre]==0:dp[i]=0# 规则3：个位是可变数字，一定是好数elifdigitin{2,5,6,9}:dp[i]=2# 规则4：个位是不变数字，继承高位状态else:dp[i]=dp[pre]# 统计所有好数ifdp[i]==2:res+=1returnres

5.3 复杂度分析

• 时间复杂度：O(n)。仅一次遍历，无嵌套循环；

• 空间复杂度：O(n)。开辟 dp 数组存储状态，适合大数据量场景。

六、三种解法对比

七、测试验证

测试用例1

输入：n = 10

输出：4

合法好数：2、5、6、9，所有解法均可正确输出。

测试用例2

输入：n = 2

输出：1

解释：仅数字2为好数。

测试用例3

输入：n = 8

输出：2

解释：合法好数为 2、5。

八、总结

1. 本题核心是双重条件校验：无非法数字 + 存在可变旋转数字；

2. 暴力字符串解法是刷题最优解，兼顾简洁性和效率；

3. 动态规划解法通过状态复用优化时间复杂度，是进阶考点，适合算法进阶学习；

4. 本题数据范围小，三种解法均可AC，可根据场景灵活选择。