题目形容
这是 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 多平台公布