本文共 2116 字，大约阅读时间需要 7 分钟。

题目

我们称一个数 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 = 412 —— 作为七进制的12，转换为十进制为9；作为三进制的11，转换为十进制的4；最终结果：9 - 4 = 5

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

10 -- 作为三进制的10，转换为312 -- 作为三进制的11，转换为418 -- 作为三进制的12，转换为520 -- 作为三进制的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)

转载地址：https://dataartist.blog.csdn.net/article/details/107069470 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！