LeetCode 788. 旋转数字 详细技术解析三种解法题目难度简单题目标签数组、枚举、动态规划、数学一、题目概述1.1 题目定义我们称一个数 X 为好数满足两个核心条件将 X 的每一位数字旋转 180° 后能得到一个有效数字无失效数字旋转后的数字与原数字不相等。数字旋转规则有效旋转数字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数据量较小暴力枚举完全可通过同时可优化动态规划解法适配更大数据。二、解题核心思路想要判断一个数是否为好数必须同时满足两个核心条件无非法数字数字的每一位都不能是 3、4、7数字发生变化数字中至少包含一个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 的所有数字对每个数字逐位校验拆分当前数字的每一位校验是否存在非法数字3、4、7存在则跳过校验是否存在可变数字2、5、6、9存在则判定为好数统计所有符合条件的好数。3.2 完整代码实现classSolution:defrotatedDigits(self,n:int)-int:# 定义非法数字、可变数字集合invalid{3,4,7}change{2,5,6,9}res0# 遍历1到n所有数字fornuminrange(1,n1):tmpnum has_changeFalseis_validTrue# 逐位拆解数字whiletmp0:digittmp%10# 存在非法数字直接无效ifdigitininvalid:is_validFalsebreak# 存在可变数字标记为可变化ifdigitinchange:has_changeTruetmptmp//10# 有效且发生变化是好数ifis_validandhas_change:res1returnres3.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}count0fornuminrange(1,n1):sstr(num)# 包含非法数字直接跳过ifany(cininvalidforcins):continue# 包含可变数字即为好数ifany(cinchangeforcins):count1returncount4.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若个位是非法数字3、4、7dp\[i\] 0若高位无效dp[pre]0当前数字无效dp\[i\] 0若个位是可变数字2、5、6、9当前数字为好数dp\[i\] 2若个位是不变数字0、1、8状态继承高位dp\[i\] dp\[pre\]。5.2 完整代码实现classSolution:defrotatedDigits(self,n:int)-int:# dp数组三种状态0无效数字 1有效但旋转不变 2有效且旋转变化(好数)dp[0]*(n1)# 逐个初始化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():ifnumn:dp[num]state res0# 从1开始遍历所有数字foriinrange(1,n1):# 拆分当前数字的个位和剩余高位digiti%10prei//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:res1returnres5.3 复杂度分析时间复杂度O(n)。仅一次遍历无嵌套循环空间复杂度O(n)。开辟 dp 数组存储状态适合大数据量场景。六、三种解法对比解法时间复杂度空间复杂度代码难度适用场景数学暴力枚举O(n log n)O(1)中等无额外空间要求常规刷题字符串优化枚举O(n log n)O(1)简单快速解题、代码简洁优先动态规划O(n)O(n)较难n 极大、追求最优时间复杂度七、测试验证测试用例1输入n 10输出4合法好数2、5、6、9所有解法均可正确输出。测试用例2输入n 2输出1解释仅数字2为好数。测试用例3输入n 8输出2解释合法好数为 2、5。八、总结本题核心是双重条件校验无非法数字 存在可变旋转数字暴力字符串解法是刷题最优解兼顾简洁性和效率动态规划解法通过状态复用优化时间复杂度是进阶考点适合算法进阶学习本题数据范围小三种解法均可AC可根据场景灵活选择。