 模拟)
教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本文基于 LogicStack-LeetCode 仓库中「刷穿 LeetCode」系列的 788. 旋转数字题解 展开系统讲解好数的判定规则、如何把旋转语义转化为可编码的两个数学条件并给出 Java / C / Python / TypeScript 四种语言的完整模拟实现与复杂度分析。读完本文你将掌握一类按位映射 全量枚举模拟题的通用解题模式并理解当数据范围扩大时如何向数位 DP 思路迁移。题目背景什么是好数我们称一个数X为好数如果它的每位数字逐个被旋转180度后我们仍可以得到一个有效的且和X不同的数要求每位数字都要被旋转。题目给出的旋转规则是这道题唯一的知识点数字旋转 180° 后的结果性质0、1、8仍然是自己有效但旋转前后数值不变25有效数值发生变化互为镜像52有效数值发生变化互为镜像69有效数值发生变化互为镜像96有效数值发生变化互为镜像3、4、7不再是有效数字无效根据定义好数需要同时满足两个条件每一位旋转后仍然是有效数字——即每一位只能取自集合{0, 1, 2, 5, 6, 8, 9}不能出现3、4、7旋转后的数与X不同——即至少存在一位落在{2, 5, 6, 9}中使得整体数值发生变化。示例输入: 10 输出: 4 解释: 在[1, 10]中有四个好数 2, 5, 6, 9。 注意 1 和 10 不是好数, 因为他们在旋转之后不变。数据范围提示N的取值范围是[1, 10000]。这个上限决定了本题可以选择全量枚举 逐位检查的朴素模拟路线这也是原题解Tag「模拟」的核心出发点。解题思路把旋转语义翻译成两个布尔条件利用 $n$ 的范围为 $10^4$我们可以直接检查 $[1, n]$ 的每个数。核心观察如下由于每一位都需要能被翻转因此如果当前枚举到的数值x中包含非有效翻转数字即不属于0125689的数字也就是3、4、7则该数必然不是好数可以直接剪枝跳过在每一位均为有效数字的前提下若当前枚举到的数值x中包含翻转后能够发生数值上变化的数字即2、5、6、9中的任意一个则该数一定是好数。于是判断单个数字是否是好数就变成了一次从低位到高位的逐位扫描过程中维护两个信号ok或 C 中的ok是否至少出现过一次2 / 5 / 6 / 9即旋转后数值是否发生变化所有位是否都落在有效集合{0, 1, 2, 5, 6, 8, 9}内。只有全部位有效且出现过变化位两个条件同时成立答案计数才加一。逐位分解的实现细节对整数逐位取数字的标准手法是循环执行t x % 10取出最低位再x / 10去掉最低位直到x 0。这一步在四份代码中完全一致是模拟解法能够做到 $O(\log n)$ 检查复杂度的关键。需要注意枚举从i 1开始题目要求统计1到N0不在范围内对i 1这类旋转后不变的数字虽然所有位有效但没有任何变化位因此ok保持false不会被计数对10这类同时包含有效位但无变化位的数字同理不计入。多语言实现直接可提交的完整代码以下四份代码均可在对应语言的 LeetCode 环境中直接提交逻辑完全等价只是语法风格略有差异。Java 版本Java 版本使用带标签的out:外层循环配合continue out;一旦发现非法位3、4、7立即跳过当前数字class Solution { public int rotatedDigits(int n) { int ans 0; out:for (int i 1; i n; i) { boolean ok false; int x i; while (x ! 0) { int t x % 10; x / 10; if (t 2 || t 5 || t 6 || t 9) ok true; else if (t ! 0 t ! 1 t ! 8) continue out; } if (ok) ans; } return ans; } }C 版本C 版本用valid标志显式记录所有位均有效并在遇到非法位时break提前结束内层循环语义与 Java 版完全一致class Solution { public: int rotatedDigits(int n) { int ans 0; for (int i 1; i n; i) { bool ok false; bool valid true; int x i; while (x) { int t x % 10; x / 10; if (t 2 || t 5 || t 6 || t 9) { ok true; } else if (t 3 || t 4 || t 7) { valid false; break; } } if (valid ok) ans; } return ans; } };Python 版本Python 版本把ok置为False后直接break用ans ans 1 if ok else ans完成条件计数class Solution: def rotatedDigits(self, n: int) - int: ans 0 for i in range(1, n 1): ok, x False, i while x ! 0: t x % 10 x x // 10 if t 2 or t 5 or t 6 or t 9: ok True elif t ! 0 and t ! 1 and t ! 8: ok False break ans ans 1 if ok else ans return ansTypeScript 版本TypeScript 版本同样使用标签循环注意除法需用Math.floor(x / 10)保证整数结果function rotatedDigits(n: number): number { let ans 0 out:for (let i 1; i n; i) { let ok false let x i while (x ! 0) { const t x % 10 x Math.floor(x / 10) if (t 2 || t 5 || t 6 || t 9) ok true else if (t ! 0 t ! 1 t ! 8) continue out } if (ok) ans } return ans };复杂度分析时间复杂度共有 $n$ 个数需要枚举检查一个数需要遍历其每一位数字一个数最多有 $\log_{10} n 1$ 位复杂度为 $O(\log n)$。整体复杂度为 $O(n \log n)$。在 $n \le 10^4$ 的限制下完全可行。空间复杂度仅使用常数个临时变量ans、ok、x、t等为 $O(1)$。边界情况与易错点梳理结合代码逐行推演以下几点是最容易出错的边界旋转后必须不同只含0、1、8的数字如1、10、88虽然每位都有效但旋转前后数值相同不是好数。这是示例中明确给出的陷阱也是ok标志存在的意义。每位数字都要被旋转任何一位包含3、4、7都直接判负即使其他位全是变化位也不行例如23含3不是好数。枚举起点从1而不是0开始因为统计区间是 $[1, N]$。提前剪枝Java / TypeScript 的continue out与 C 的break都是发现非法位立即放弃当前数避免无谓的剩余位扫描属于纯优化不影响正确性。举一反三模拟思路的适用边界与数位 DP 延伸本题是典型的数据范围决定算法案例$n \le 10^4$ 意味着 $O(n \log n)$ 的暴力枚举在任意语言下都能毫秒级通过因此直接模拟是性价比最高的选择。若把N的上限提升到 $10^9$ 甚至更大$O(n)$ 级别的枚举将不可接受此时应转向数位 DPDigit DP思路从高位到低位逐位放置用状态记录是否已出现过变化位2/5/6/9与是否触顶tight 约束把计数复杂度降到 $O(\log N)$ 级别。本仓库的 Index/数位 DP.md 收录了该类问题的系列题解可作为延伸学习的入口。从方法论上看本题的模拟标签在仓库 Index/模拟.md 题单中收录了 788 题同题单还包括 412. Fizz Buzz、1104. 二叉树寻路、1222. 可以攻击国王的皇后等大量按题意逐步操作的题目——这类题的核心竞争力在于把文字规则准确翻译成循环与条件而本题两张映射表有效位集合 变化位集合的抽象方式正是一种可以复用到其他规则型题目的建模手法。仓库资源与延伸阅读本题完整题解原文LeetCode/781-790/788. 旋转数字中等.md模拟类题单Index/模拟.md数位 DP 类题单延伸思路Index/数位 DP.md仓库简介与刷题系列说明见 README.md如需在本地调试上述代码可直接将任意语言的Solution复制到对应语言的 LeetCode 编辑器中运行或在本地安装对应运行时后以n 10等小数据自测预期输出为4。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LogicStack-LeetCode 剑指 Offer II 003前 n 个数字二进制中 1 的个数从 O(32n) 模拟到严格 O(n) 线性递推LogicStack LeetCode 剑指 Offer II 003前 n 个数字二进制中 1 的个数从 O 32n 模拟到严格 O n 线性递推 本篇基教程文档LogicStack-LeetCode 刷穿 LeetCode 33搜索旋转排序数组——从朴素二分到严格 O(log n) 的两段性二分LogicStack LeetCode 刷穿 LeetCode 33搜索旋转排序数组——从朴素二分到严格 O log n 的两段性二分 本篇文章以 Logic教程文档LogicStack-LeetCode 题解1224. 最大相等频率——O(n) 计数模拟与三情况分治LogicStack LeetCode 题解1224. 最大相等频率——O n 计数模拟与三情况分治 本篇技术指南以「刷穿 LeetCode」系列第 1224教程文档上一篇OrcaSlicer 批量打印工作流终极指南多模型排列优化与任务队列管理技巧下一篇5分钟掌握Zettlr正则搜索从入门到精准定位复杂内容模式创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
