Medium

题目描述

如果一个整数 x 的每个数字都旋转 180 度后，我们得到一个有效的数字且与 x 不同，那么这个整数 x 就是好数。每个数字都必须旋转 - 我们不能选择保持某个数字不变。

如果每个数字在旋转后仍然是一个数字，那么这个数字就是有效的。例如：

  • 0、1 和 8 旋转后还是它们自己
  • 2 和 5 互相旋转（在这种情况下，它们朝不同方向旋转，换句话说，2 或 5 会被镜像）
  • 6 和 9 互相旋转
  • 其余数字不会旋转成任何其他数字，因此无效

给定一个整数 n，返回在范围 [1, n] 内好数的个数。

示例 1：

输入：n = 10
输出：4
解释：在范围 [1, 10] 内有四个好数：2, 5, 6, 9。
注意 1 和 10 不是好数，因为它们旋转后保持不变。

示例 2：

输入：n = 1
输出：0

示例 3：

输入：n = 2
输出：1

提示：

  • 1 <= n <= 10^4

解题思路

解题思路

这道题的核心是理解什么是"好数"：

  1. 数字旋转后必须是有效的（不包含 3、4、7）
  2. 旋转后的数字必须与原数字不同（至少包含一个 2、5、6、9）

方法一：暴力枚举 对于范围 [1, n] 内的每个数字，检查其是否为好数：

  • 遍历数字的每一位
  • 如果包含 3、4、7，则无效
  • 如果只包含 0、1、8，旋转后不变，不是好数
  • 如果包含 2、5、6、9 中至少一个，且不包含 3、4、7，则是好数

方法二：数位动态规划（进阶） 可以用数位 DP 优化，但对于此题的数据规模（n ≤ 10^4），暴力方法已足够高效。

我们采用暴力枚举的方法，因为它简单直观且在给定约束下效率足够。

具体实现：

  1. 定义有效数字集合：{0, 1, 2, 5, 6, 8, 9}
  2. 定义会改变的数字集合：{2, 5, 6, 9}
  3. 对每个数字检查其所有位是否都有效，且至少有一位会改变

代码实现

class Solution {
public:
    int rotatedDigits(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (isGood(i)) {
                count++;
            }
        }
        return count;
    }
    
private:
    bool isGood(int num) {
        bool hasChange = false;
        while (num > 0) {
            int digit = num % 10;
            if (digit == 3 || digit == 4 || digit == 7) {
                return false;
            }
            if (digit == 2 || digit == 5 || digit == 6 || digit == 9) {
                hasChange = true;
            }
            num /= 10;
        }
        return hasChange;
    }
};

class Solution:
    def rotatedDigits(self, n: int) -> int:
        def is_good(num):
            has_change = False
            for digit in str(num):
                if digit in '347':
                    return False
                if digit in '2569':
                    has_change = True
            return has_change
        
        count = 0
        for i in range(1, n + 1):
            if is_good(i):
                count += 1
        return count

public class Solution {
    public int RotatedDigits(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (IsGood(i)) {
                count++;
            }
        }
        return count;
    }
    
    private bool IsGood(int num) {
        bool hasChange = false;
        while (num > 0) {
            int digit = num % 10;
            if (digit == 3 || digit == 4 || digit == 7) {
                return false;
            }
            if (digit == 2 || digit == 5 || digit == 6 || digit == 9) {
                hasChange = true;
            }
            num /= 10;
        }
        return hasChange;
    }
}

var rotatedDigits = function(n) {
    function isGood(num) {
        let hasChange = false;
        const str = num.toString();
        for (let char of str) {
            if ('347'.includes(char)) {
                return false;
            }
            if ('2569'.includes(char)) {
                hasChange = true;
            }
        }
        return hasChange;
    }
    
    let count = 0;
    for (let i = 1; i <= n; i++) {
        if (isGood(i)) {
            count++;
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
暴力枚举O(n × log n)O(1)

说明：

  • 时间复杂度：遍历 [1, n] 范围内的每个数字，每个数字需要检查其所有位数，最多 log n 位
  • 空间复杂度：只使用常数额外空间