算法笔记-lc-788. 旋转数字(中等)

@[TOC](算法笔记-lc-788. 旋转数字(中等))

题目

题干

我们称一个数 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] 的每一个正整数，并以此判断它们是否满足上述要求即可。在下面的代码中，我们用 valid 记录数是否满足第一条要求，diff 记录数是否满足第二条要求。

代码

class Solution {
    static int[] check = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};

    public int rotatedDigits(int n) {
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            String num = String.valueOf(i);
            boolean valid = true, diff = false;
            for (int j = 0; j < num.length(); ++j) {
                char ch = num.charAt(j);
                if (check[ch - '0'] == -1) {
                    valid = false;
                } else if (check[ch - '0'] == 1) {
                    diff = true;
                }
            }
            if (valid && diff) {
                ++ans;
            }
        }
        return ans;
    }
}

复杂度分析

时间复杂度：O(nlogn)。数 n 的数位有 ⌈log10n⌉+1=O(logn) 个，其中⌈⋅⌉ 表示向上取整。因此总时间复杂度为 O(nlogn)。

空间复杂度：O(logn)。使用的空间分为两部分，第一部分为代码中记录每一个数位类型的数组check 需要使用的O(10)=O(1) 的空间，第二部分为将数 i 转化为字符串需要使用的临时空间，大小为 O(logn)。这一部分的空间也可以优化至 O(1)，只需要每次将 i 对10 进行取模，从低位到高位获取 ii 的每一个数位即可。

方法二：数位动态规划

思路与算法

我们也可以用数位动态规划的思路解决本题。由于在一个数之前填加前导零不会改变数本身的好坏，因此我们只需要考虑所有位数与 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/73/4/7，这样可以保证数一定是可以旋转的，只需要额外的状态 diff 就能表示其是否为好数。

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

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

f(pos,bound,diff)=∑f(pos+1,bound’,diff’)

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

‘bound’ 为真，当且仅当 bound 为真，并且选择的数恰好与 n 的第 pos 个数位相同；

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

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

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

代码

class Solution {
    static int[] check = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
    int[][][] memo = new int[5][2][2];
    List<Integer> digits = new ArrayList<Integer>();

    public int rotatedDigits(int n) {
        while (n != 0) {
            digits.add(n % 10);
            n /= 10;
        }
        Collections.reverse(digits);

        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 2; ++j) {
                Arrays.fill(memo[i][j], -1);
            }
        }

        int ans = dfs(0, 1, 0);
        return ans;
    }

    public int dfs(int pos, int bound, int diff) {
        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 != 0 ? digits.get(pos) : 9); ++i) {
            if (check[i] != -1) {
                ret += dfs(
                    pos + 1,
                    bound != 0 && i == digits.get(pos) ? 1 : 0,
                    diff != 0 || check[i] == 1 ? 1 : 0
                );
            }
        }
        return memo[pos][bound][diff] = ret;
    }
}

复杂度分析

时间复杂度：O(logn)。数 n 的数位有⌈log10n⌉+1=O(logn) 个，那么动态规划的状态有 O(logn×2×2)=O(logn) 个，每个状态需要O(10)=O(1) 的时间进行转移，因此总时间复杂度为 O(logn)。

空间复杂度：O(logn)，即为动态规划中存储状态需要使用的空间。