题目
我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。
如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。
现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？
示例：
<code>输入:
10
输出:
4
解释:
在[1,
10
]中有四个好数：
2
,
5
,
6
,
9
。
注意
1
和
10
不是好数,
因为他们在旋转之后不变。
/<code>
提示：
- 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
例如：
<code>10
——
作为七进制的10，转换为十进制的7；作为三进制的10，转换为十进制的3；最终结果：7
-
3
=
4
12
——
作为七进制的12，转换为十进制为9；作为三进制的11，转换为十进制的4；最终结果：9
-
4
=
5
/<code>
但是，在这种朴素的对应方式下，会出现如下问题：
<code>10
12
18
20
/<code>
为了纠正这个问题，我们在转换时做出如下调整：
如果在高位上出现了不存在于映射表中的数，则低位直接取最大值。例如，130在转换为三进制时，因为十位的3不存在于映射表中，所以个位直接取最大值2，即112。
具体的Python实现如下：
<code>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 = Falsefor
sin
S:if
off: S3 +="2"
else
: off = sin
o3 S3 += d3[s] off = Falsefor
sin
S:if
off: S7 +="6"
else
: off = sin
o7 S7 += d7[s] return
int
(S7,base
=7
) -int
(S3,base
=3
)/<code>
