题目形容

这是 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多平台公布