M788.旋转数字

digit dp, https://leetcode.cn/problems/rotated-digits/

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

这个问题可以通过枚举 $1$ 到 $N$ 的每一个整数并检查其是否符合“好数”的定义来解决。

题目分析

一个数 $X$ 是“好数”，必须满足以下两个条件：

旋转后有效：数中的每一位数字在旋转 180 度后必须仍然是一个有效的数字。
- 有效数字：0, 1, 8（旋转后不变），2, 5, 6, 9（旋转后变味另一个数字）。
- 无效数字：3, 4, 7。
旋转后不同：旋转后的整个数字必须与原数字 $X$ 不同。
- 这意味着 $X$ 中必须包含至少一个旋转后会改变的数字（即 2, 5, 6, 9 中的任意一个）。
- 同时， $X$ 中不能包含任何旋转后无效的数字（即 3, 4, 7）。

算法步骤

遍历从 $1$ 到 $N$ 的每个数字。
对于每个数字，检查其每一位：
- 如果包含 3, 4, 7，则该数无效。
- 如果只包含 0, 1, 8，旋转后数字不变，不符合“好数”定义。
- 如果不包含 3, 4, 7 且包含至少一个 2, 5, 6, 9，则该数是“好数”。
统计“好数”的总数。

Python 代码实现

python

class Solution:
    def rotatedDigits(self, n: int) -> int:
        count = 0
        
        # 定义集合以便快速查询
        invalid = {'3', '4', '7'}
        diff_change = {'2', '5', '6', '9'}
        
        for i in range(1, n + 1):
            s = str(i)
            # 条件 1: 不能包含 3, 4, 7
            is_valid = True
            has_diff = False
            
            for char in s:
                if char in invalid:
                    is_valid = False
                    break
                if char in diff_change:
                    has_diff = True
            
            # 条件 2: 必须包含至少一个能改变数值的数字 (2, 5, 6, 9)
            if is_valid and has_diff:
                count += 1
                
        return count

复杂度分析

时间复杂度： $O (N \log N)$ 。我们需要遍历从 $1$ 到 $N$ 的所有数字，对于每个数字，我们需要检查它的每一位。数字 $i$ 的位数是 $\log_{10} i$ 。由于 $N$ 最大为 $10000$ ，总计算量大约为 $10^{4} \times 5 = 50, 000$ 次操作，这在 Python 中执行非常快。
空间复杂度： $O (\log N)$ ，主要是将数字转换为字符串所需的空间。

进阶优化（数位 DP）

如果 $N$ 的取值范围变得非常大（例如 $10^{9}$ ），上述暴力枚举法将超时。此时可以使用数位动态规划 (Digit DP)。

对于本题 $N = 10000$ 的规模，上述简单遍历是最直接且符合面试要求的解法。

当 $N$ 的范围很大时（例如 $N = 10^{9}$ ），暴力枚举每个数字的方法会超时。此时最标准、最高效的解法是使用 数位动态规划 (Digit DP)。

数位 DP 的核心思想

数位 DP 逐位填写数字，通过递归和记忆化搜索来统计符合条件的个数。

在本题中，我们需要关注两个状态：

是否已经出现了“变色”数字（即 2, 5, 6, 9）。只要出现过一个，且最终所有数字都在 {0, 1, 8, 2, 5, 6, 9} 中，这个数就是好数。
是否存在无效数字（即 3, 4, 7）。这种数字一旦出现，整个数直接作废。

状态定义

定义函数 dfs(pos, has_diff, is_limit)：

pos: 当前处理到 $N$ 的从左往右第几位。
has_diff: 布尔值，表示前面填过的数字中是否已经包含过 2, 5, 6, 9 中的任意一个。
is_limit: 布尔值，表示当前位填写的数字是否受 $N$ 的限制（标准的数位 DP 逻辑）。

状态转移逻辑

遍历可选数字 $d$ 从 $0$ 到 upper_bound（如果 is_limit 为真，上限是 $N$ 对应位的数字，否则是 9）：
- 如果 $d \in {3, 4, 7}$ ，直接跳过。
- 如果 $d \in {2, 5, 6, 9}$ ，递归下一位，has_diff 设为 True。
- 如果 $d \in {0, 1, 8}$ ，递归下一位，has_diff 保持不变。

Python 代码实现

python

from functools import lru_cache

class Solution:
    def rotatedDigits(self, n: int) -> int:
        s = str(n)
        
        # 使用记忆化搜索
        @lru_cache(None)
        def dfs(pos: int, has_diff: bool, is_limit: bool) -> int:
            # 递归终点：填完了所有位数
            if pos == len(s):
                # 只有当包含至少一个 2, 5, 6, 9 时才是好数
                return 1 if has_diff else 0
            
            res = 0
            # 确定当前位能填的最大数字
            up = int(s[pos]) if is_limit else 9
            
            for d in range(up + 1):
                # 1. 排除无效数字 3, 4, 7
                if d in (3, 4, 7):
                    continue
                
                # 2. 判断新的 has_diff 状态
                # 如果当前位是 2, 5, 6, 9，则 new_has_diff 为 True
                new_has_diff = has_diff or (d in (2, 5, 6, 9))
                
                # 3. 递归到下一位
                res += dfs(
                    pos + 1, 
                    new_has_diff, 
                    is_limit and (d == up)
                )
                
            return res

        # 从第 0 位开始，初始没有变色数字，受限于 N
        return dfs(0, False, True)

复杂度分析

时间复杂度： $O (\log_{10} N \times 2 \times 2 \times 10)$ 。
- 状态总数 = 位数 ( $\log N$ ) $\times$ has_diff (2种) $\times$ is_limit (2种)。
- 每个状态内部循环 10 次。
- 对于 $N = 10^{18}$ ，也只需要处理大约 $18 \times 4 \times 10 = 720$ 次计算，极其高效。
空间复杂度： $O (\log N)$ ，即递归栈的深度和记忆化哈希表的开销。

为什么不需要处理前导零（leading zeros）？

在某些数位 DP 题目（如统计数字出现次数）中，前导零会干扰结果。但本题中：

0 属于旋转后不变的数字（类似于 1 和 8）。
将数字 5 看作 0005 并不影响它的“好数”属性，因为 0 不会使数无效，也不会让 has_diff 提前变真。
最终结果中 $0$ 本身会因为 has_diff 为 False 而被返回 $0$ ，所以不会误增计数。

M788.旋转数字 ​

M788.旋转数字