难度: Medium
我们称一个数 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 不是好数, 因为他们在旋转之后不变。
提示：
[1, 10000]。运行时间: 26 ms
内存: 16.2 MB
class Solution:
def rotatedDigits(self, n: int) -> int:
s = str(n)
m = len(s)
# 合法情况：包含至少一个 [2, 5, 6, 9] 且 不包含 [3, 4, 7]
nums = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1]
@lru_cache(None)
def f(i, has_mir, is_limit, is_num):
if i == m: return int(is_num and has_mir)
res = 0 if is_num else f(i + 1, has_mir, False, False)
lo, hi = 0 if is_num else 1, int(s[i]) if is_limit else 9
for j in range(lo, hi + 1):
if nums[j] != -1:
res += f(i + 1, has_mir or nums[j] == 1, is_limit and j == hi, True)
return res
return f(0, False, True, False)
这个题解使用了记忆化搜索的思路。通过递归函数 f(i, has_mir, is_limit, is_num) 来搜索所有可能的好数，其中参数含义如下： - i 表示当前搜索的数字位置 - has_mir 表示之前的数字中是否包含 2/5/6/9 - is_limit 表示当前是否受到了 N 的约束 - is_num 表示当前是否搜索到了一个合法数字 搜索过程中，依次枚举当前位置可能的数字，递归搜索下一个位置。如果枚举的数字合法，则更新 has_mir 状态；如果当前已经搜索到最后一位，则根据 is_num 和 has_mir 的状态来判断是否找到一个好数。 通过记忆化搜索避免了重复计算，最终可以高效地找到 1 到 N 中所有的好数。
时间复杂度: O(logN)
空间复杂度: O(logN)
class Solution:
def rotatedDigits(self, n: int) -> int:
s = str(n)
m = len(s)
# 合法情况：包含至少一个 [2, 5, 6, 9] 且 不包含 [3, 4, 7]
nums = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1]
@lru_cache(None)
def f(i, has_mir, is_limit, is_num):
# 如果已搜索到最后一位，根据状态返回结果
if i == m: return int(is_num and has_mir)
# 如果当前未搜索到合法数字，则跳过当前位，继续搜索下一位
res = 0 if is_num else f(i + 1, has_mir, False, False)
# 根据是否受到 N 的约束，确定枚举的起始数字 lo 和最大数字 hi
lo, hi = 0 if is_num else 1, int(s[i]) if is_limit else 9
# 枚举当前位的数字 j
for j in range(lo, hi + 1):
# 如果数字 j 合法
if nums[j] != -1:
# 递归搜索下一位，同时更新状态
res += f(i + 1, has_mir or nums[j] == 1, is_limit and j == hi, True)
return res
# 调用递归函数，初始状态为：位置 0，之前没有合法数字，受到 N 的约束，当前未搜索到合法数字
return f(0, False, True, False)
参数`has_mir`用来标识在当前数字之前是否已经出现了至少一个镜像数字（即2, 5, 6, 或9中的任何一个）。其初始值设置为`False`是因为在搜索的起始阶段，我们尚未遍历任何数字，因此显然之前不可能包含镜像数字。这种设定对算法的影响是，它确保了我们只在确实遇到了镜像数字后才将该标志设为`True`。如果没有遇到镜像数字而错误地设置了这个标志，会导致错误地认为某些不符合条件的数字是好数，从而影响最终结果的正确性。
在枚举当前位数字时，`is_num`参数标识当前是否已经选定了一个非零的起始数字。如果`is_num`为`False`，意味着我们还没有开始形成一个有效的数字，因此起始数字`lo`可以为0，即数字可以从0开始。但如果`is_num`为`True`，表示我们已经开始形成数字，此时数字的最高位不能为0（即不能有前导零），因此起始数字`lo`设为1。这种设计避免了生成如010或001这类包含前导零的无效数字。
数组`nums`用来快速判断每个数字是否合法以及是否为镜像数字。使用数组的好处是，它提供了O(1)时间复杂度的访问速度，这对于频繁查询的场景（如递归搜索中的每一步）是非常高效的。数组直接通过索引访问，与数字的值直接相关，无需额外计算或查找，从而极大地提高了效率。尽管也可以使用哈希表来存储这种信息，但考虑到只有10个数字，数组更为简洁且效率更高。在这种情况下，更复杂的数据结构如哈希表或树并没有明显的优势，可能会增加实现的复杂性且可能降低访问速度。