【788. 旋转数字】

来源：力扣（LeetCode）

描述：

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

方法一：枚举每一个数

思路与算法

根据题目的要求，一个数是好数，当且仅当：

数中没有出现 3, 4, 73,4,7；

数中至少出现一次 22 或 55 或 66 或 99；

对于 0, 1, 80,1,8 则没有要求。

因此，我们可以枚举 [1, n][1,n] 的每一个正整数，并以此判断它们是否满足上述要求即可。在下面的代码中，我们用 \textit{valid}valid 记录数是否满足第一条要求，\textit{diff}diff 记录数是否满足第二条要求。

代码：

class Solution {
public:
    int rotatedDigits(int n) {
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            string num = to_string(i);
            bool valid = true, diff = false;
            for (char ch: num) {
                if (check[ch - '0'] == -1) {
                    valid = false;
                }
                else if (check[ch - '0'] == 1) {
                    diff = true;
                }
            }
            if (valid && diff) {
                ++ans;
            }
        }
        return ans;
    }

private:
    static constexpr int check[10] = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
};

执行用时：20 ms, 在所有 C++ 提交中击败了39.46%的用户
内存消耗：5.9 MB, 在所有 C++ 提交中击败了35.14%的用户
复杂度分析
时间复杂度： O(nlogn)。数 n 的数位有 ⌈log₁₀ n⌉ + 1 = O(logn) 个，其中 ⌈ ⋅ ⌉ 表示向上取整。因此总时间复杂度为 O(nlogn)。
空间复杂度： O(logn)。使用的空间分为两部分，第一部分为代码中记录每一个数位类型的数组 check 需要使用的 O(10) = O(1) 的空间，第二部分为将数 i 转化为字符串需要使用的临时空间，大小为 O(logn)。这一部分的空间也可以优化至 O(1)，只需要每次将 i 对 10 进行取模，从低位到高位获取 i 的每一个数位即可。

方法二：数位动态规划

思路与算法

我们也可以用数位动态规划的思路解决本题。由于在一个数之前填加前导零不会改变数本身的好坏，因此我们只需要考虑所有位数与 n 相同并且小于等于 n 的数（可以有前导零）即可。

记 f(pos, bound, diff) 为满足如下要求的好数的个数：

• 只从第 pos 位开始考虑。这里数的最高位为第 0 位，最低位为第 len − 1 位，其中 len 是数 n 的长度。在计算 f(pos, bound, diff) 时，会假设第 0 位到第 pos − 1 位已经固定，并且会用 bound 和 diff 两个布尔变量表示这些数位的「状态」；

• 从第 0 位到第 pos− 1 位的数是否「贴着」 n，记为 bound。例如当 n = 12345， pos = 3 时，如果前面的数位是 123，那就表示贴着 n，如果是 122, 121, ⋯，那就表示没有贴着 n。区分是否「贴着」n 的作用是，如果 bound 为真，第 pos 位只能在 0 到 n 的第 pos 位进行选择，否则构造出的数就超过 n 了；如果 bound 为假，那么第 pos 位可以在 0 到 9 之间任意选择；

• 从第 0 位到第 pos − 1 位的数中是否至少出现了一次 2 或 5 或 6 或 9，记为 diff。在进行状态转移时，我们只会枚举（第 pos 位的数） 0 / 1 / 2 / 5 / 6 / 8 / 9 而不枚举 3 / 4 / 7，这样可以保证数一定是可以旋转的，只需要额外的状态 diff 就能表示其是否为好数。

根据上述的定义，我们需要求出的答案即为 f(0, True, False)。

在进行状态转移时，我们只需要枚举第 pos 位选择的数，其可以选择的范围根据 bound 的不同而不同（上述定义中已经详细阐述过）。我们可以写出如下的状态转移方程：

那么如何根据选择的数，确定 bound’ 和 diff’ 呢？我们可以发现：

• bound’ 为真，当且仅当 \textit{bound}bound 为真，并且选择的数恰好与 nn 的第 \textit{pos}pos 个数位相同；

• diff’ 为真，当且仅当diff 为真，或者选择的数在 2 / 5 / 6 / 9 中。

动态规划的边界情况为出现在 pos 等于 n 的长度时，此时所有数位已经确定，那么我们通过 diff 就可以知道其是否为好数：如果 diff 为真，那么 f(pos, bound, diff) 的值为 1，否则为 0。

该方法使用记忆化搜索编写代码更为方便。

代码:

class Solution {
public:
    int rotatedDigits(int n) {
        vector<int> digits;
        while (n) {
            digits.push_back(n % 10);
            n /= 10;
        }
        reverse(digits.begin(), digits.end());
        
        memset(memo, -1, sizeof(memo));
        function<int(int, bool, bool)> dfs = [&](int pos, bool bound, bool diff) -> int {
            if (pos == digits.size()) {
                return diff;
            }
            if (memo[pos][bound][diff] != -1) {
                return memo[pos][bound][diff];
            }

            int ret = 0;
            for (int i = 0; i <= (bound ? digits[pos] : 9); ++i) {
                if (check[i] != -1) {
                    ret += dfs(
                        pos + 1,
                        bound && (i == digits[pos]),
                        diff || (check[i] == 1)
                    );
                }
            }
            return memo[pos][bound][diff] = ret;
        };
        
        int ans = dfs(0, true, false);
        return ans;
    }

private:
    static constexpr int check[10] = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
    int memo[5][2][2];
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了69.19%的用户
复杂度分析
时间复杂度： O(logn)。数 n 的数位有 ⌈log₁₀n⌉ + 1 = O(logn) 个，那么动态规划的状态有 O(logn × 2 × 2) = O(logn) 个，每个状态需要 O(10) = O(1) 的时间进行转移，因此总时间复杂度为 O(logn)。
空间复杂度： O(logn)，即为动态规划中存储状态需要使用的空间。
author：LeetCode-Solution