LeetCode题解(0788)：进制转换的奇技淫巧

题目

我们称一个数 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]。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/rotated-digits

解法

首先，看到这道题，最容易想到的方法，就是遍历从1到N的所有数，并判断他们是不是好数。在这种思路下， 无论我们怎么优化，最后的效率都不会超过O(NlogN)，其中log的底数为10，log10即数字的位数。

但是，通过观察我们可以发现，数字中如果包含3、4、7，则会因为这些数字翻转后不再是数字而被剔除；而数字如果只包含0、1、8，则会因为这些数字翻转后数值不变，而被剔除。

在前100个正整数中，不包含3、4、7的数一共有49个，正好是七进制下的100对应的十进制数；而仅包含0、1、8的数一共有9个，也正好是三进制下的100对应的十进制数。（通过动态规划的方法也可以得到类似的思路）

由此，我们想到使用进制来计算。

简单来说，我们将十进制的数当做七进制和三进制，转换成十进制，即将100视作七进制的100，转换为十进制的49。并将七进制转换的数减去三进制转换的数，直接得到好数的数量。

在具体的操作上，在计算七进制时，七进制的0、1、2、5、6、8、9分别映射七进制的0、1、2、3、4、5、6；在计算三进制时，三进制的0、1、8分别映射三进制的0、1、2。如果出现了不存在于上述映射表中的数n，则取小于n的最大的数的映射，例如三进制的5，则取1的映射1

例如：

10 —— 作为七进制的10，转换为十进制的7；作为三进制的10，转换为十进制的3；最终结果：7 - 3 = 4
12 —— 作为七进制的12，转换为十进制为9；作为三进制的11，转换为十进制的4；最终结果：9 - 4 = 5

但是，在这种朴素的对应方式下，会出现如下问题：

10 -- 作为三进制的10，转换为3
12 -- 作为三进制的11，转换为4
18 -- 作为三进制的12，转换为5
20 -- 作为三进制的10，转换为3（这显然是错误的）

为了纠正这个问题，我们在转换时做出如下调整：

如果在高位上出现了不存在于映射表中的数，则低位直接取最大值。例如，130在转换为三进制时，因为十位的3不存在于映射表中，所以个位直接取最大值2，即112。

具体的Python实现如下：

def rotatedDigits(self, N: int) -> int:
    d7 = {
        "0": "0",
        "1": "1",
        "2": "2",
        "3": "2",
        "4": "2",
        "5": "3",
        "6": "4",
        "7": "4",
        "8": "5",
        "9": "6"
    }
    o7 = {"3", "4", "7"}
    d3 = {
        "0": "0",
        "1": "1",
        "2": "1",
        "3": "1",
        "4": "1",
        "5": "1",
        "6": "1",
        "7": "1",
        "8": "2",
        "9": "2"
    }
    o3 = {"2", "3", "4", "5", "6", "7", "9"}

    S = str(N)
    S7 = S3 = ""
    off = False
    for s in S:
        if off:
            S3 += "2"
        else:
            off = s in o3
            S3 += d3[s]

    off = False
    for s in S:
        if off:
            S7 += "6"
        else:
            off = s in o7
            S7 += d7[s]

    return int(S7, base=7) - int(S3, base=3)

最后

以上就是过时含羞草为你收集整理的LeetCode题解(0788)：进制转换的奇技淫巧的全部内容，希望文章能够帮你解决LeetCode题解(0788)：进制转换的奇技淫巧所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。