共计 1570 个字符，预计需要花费 4 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 788. 旋转数字 ，难度为 中等。
Tag :「模仿」
咱们称一个数 X 为好数, 如果它的每位数字一一地被旋转 180 度后，咱们仍能够失去一个无效的，且和 X 不同的数。要求每位数字都要被旋转。
如果一个数的每位数字被旋转当前依然还是一个数字，则这个数是无效的。0, 1, 和 8 被旋转后依然是它们本人；2 和 5 能够相互旋转成对方（在这种状况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其余的数字旋转当前都不再是无效的数字。
当初咱们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？
示例：
输出: 10
输入: 4
解释:
在 [1, 10] 中有四个好数：2, 5, 6, 9。留神 1 和 10 不是好数, 因为他们在旋转之后不变。提醒：
N的取值范畴是 $[1, 10000]$。
模仿
利用 $n$ 的范畴为 $1e4$，咱们能够间接查看 $[1, n]$ 的每个数。
因为每一个位数都须要翻转，因而如果以后枚举到的数值 x 中蕴含非无效翻转数字（非 0125689）则必然不是好数；而在每一位均为有效数字的前提下，若以后枚举到的数值 x 中蕴含翻转后可能产生数值上变动的数值（2569），则为好数。
Java 代码：
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;
}
}TypeScript 代码：
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
};Python3 代码：
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 ans- 工夫复杂度：共有 $n$ 个数须要枚举，查看一个数须要遍历其每个数字，复杂度为 $O(\log{n})$。整体复杂度为 $O(n\log{n})$
- 空间复杂度：$O(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.788 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
