旋转数字(Leetcode 788)

发表于 | 分类于 ， ， ， ， | | 本文总阅读数 次
| 字数统计: 1.6k | 阅读时长 ≈ 7
Leetcode 788

1

题目分析

   看到本题，我的第一反应是一个数学问题，首先模拟一下解题过程。首先数字不能出现3、4、7，因为一旦出现，一定是不能被旋转的。然后再分析2、5、6、9，这四个数字是必须至少出现一次的，如果一次都不出现，那么剩下的数字是0、1、8，无论如何旋转都是原数字。

递归+数学+模拟

所以本题的思想就是，在diff = [2, 5, 6, 9]中至少选择一个，然后其他数字均在same = [0, 1, 8]中。我们从最高位X开始

  • 最高位在diff中的情况

如果X等于2、5、6、9时，因为最高位已经出现了一次diff数组的元素，因此剩下的位数可以任意选择。要统计去掉最高位时，数字仅由all集合组成的个数，比如654，就需要统计54中数字仅由all集合组成的个数。因为其他数字的选择不受限制，创建一个名为noLimit的函数，表示可以取all中的所有元素。

  • 最高位在same中的情况

如果X等于0、1、8时，因为最高位没有出现diff数组的元素，因此剩下的位数是受限制的。要统计去掉最高位时，出现一次diff数组的数字，那就是本题自身，因此递归调用本方法即可。如果854，就需要统计54中至少出现一次diff的元素。

  • 考虑最高位小于X，并且出现在diff中的情况

那么X以下的2、5、6、9，低位是可以表示从0到全9的。比如854的最高位是8，那么对于2、5、6来说，可以统计99中数字仅由all集合组成的个数。

  • 考虑最高位小于X，并且出现在diff中的情况

那么X以下的1、2、8，低位是可以表示从0到全9的。比如854的最高位是8，那么对于1、2来说，可以统计99中至少出现一次diff的元素。

记n的最高位数字是x，除去最高位的数字为y，除了最高位其他全9的数字为z。记本题方法名为rotatedDigits，不受限的方法名为noLimit。小于X的元素，在diff中的个数为p，在same中的个数为q

$$ rotatedDigits(n) = p x noLimit(z) + q x rotatedDigits(z) + diff.contains(x) ? noLimit(y) : rotatedDigits(y) $$

算法的**时间复杂度为O(log(n))，空间复杂度为O(log(n))**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution {
    private HashSet<Integer> same = new HashSet<>(Arrays.asList(0, 1, 8));
    private HashSet<Integer> diff = new HashSet<>(Arrays.asList(2, 5, 6, 9));
    private HashSet<Integer> all = new HashSet<>(Arrays.asList(0, 1, 2, 5, 6, 8, 9));
    private HashMap<Integer, Integer> sameMem = new HashMap<>() {
        {
            put(0, 0);
            put(1, 0);
            put(2, 1);
            put(3, 1);
            put(4, 1);
            put(5, 2);
            put(6, 3);
            put(7, 3);
            put(8, 3);
            put(9, 4);
        }
    };

    private HashMap<Integer, Integer> allMem = new HashMap<>() {
        {
            put(0, 1);
            put(1, 2);
            put(2, 3);
            put(3, 3);
            put(4, 3);
            put(5, 4);
            put(6, 5);
            put(7, 5);
            put(8, 6);
            put(9, 7);
        }
    };

    public int rotatedDigits(int n) {
        if (sameMem.containsKey(n)) {
            return sameMem.get(n);
        }
        String s = String.valueOf(n);
        int high = s.charAt(0) - '0';
        int remain = Integer.parseInt(s.substring(1));
        int low = (int) Math.round(Math.pow(10, s.length() - 1)) - 1;
        int res = 0;
        for (int i = 0; i <= high; i++) {
            int x = i == high ? remain : low;
            if (same.contains(i)) {
                if (!sameMem.containsKey(x)) {
                    sameMem.put(x, rotatedDigits(x));
                }
                res += sameMem.get(x);
            } else if (diff.contains(i)) {
                if (!allMem.containsKey(x)) {
                    allMem.put(x, noLimit(x));
                }
                res += noLimit(x);
            }
        }
        return res;
    }

    private int noLimit(int n) {
        if (allMem.containsKey(n)) {
            return allMem.get(n);
        }
        String s = String.valueOf(n);
        int high = s.charAt(0) - '0';
        int remain = Integer.parseInt(s.substring(1));
        int low = (int) Math.round(Math.pow(10, s.length() - 1)) - 1;
        int res = 0;
        for (int i = 0; i <= high; i++) {
            int x = i == high ? remain : low;
            if (all.contains(i)) {
                if (!allMem.containsKey(x)) {
                    allMem.put(x, noLimit(x));
                }
                res += allMem.get(x);
            }
        }
        return res;
    }
}

数位DP

上述方法是一个很好的方法，其中包含着一些求解数学问题的技巧，本题还可以使用数位DP来求解。

根据递归方法中的递推公式，其实可以看出，本题是可以使用DP来做的，只不过DP比较复杂，无法通过一维来表示。这里给出一种通用的DP算法，使用三维DP(本题是可以优化到二维的)

因为数字可以在集合same中、也可以在集合diff中，因此需要一个维度来表示，0表示没有出现在diff中，1表示已经有元素出现在diff中了。

因为数字的最大值会限制后面的取值，如果当前遍历的数字等于最大值，那么后面的元素也是受限的，比如854，遍历第一位到8时，后面只能考虑到54，如果遍历到7，则后面可以考虑到99。因此也需要一个维度来表示，0表示不受限，1表示受限。

这里有两个位运算的逻辑，如果containDiff已经是1了，那么遍历后面的元素时，无论是否为0，都是1。因为已经出现过一次了，哪怕后面不出现，也表示出现过一次了。

如果limit已经是0了，那么遍历后面的元素时，无论是否等于最大值，都是0。因为最高位已经不被限制了，那么低位被限制也不会是最大值。如854、如果最高位取7时，次高位取最大9，也不会影响最后一位取值为9。

算法的**时间复杂度为O(log(n))，空间复杂度为O(n)**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    private static final int[] table = new int[]{0, 0, 1, -1, -1, 1, 1, -1, 0, 1};

    private char[] s;

    private int len;

    private int[][][] dp;

    public int rotatedDigits(int n) {
        s = String.valueOf(n).toCharArray();
        len = s.length;
        dp = new int[2][2][len];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        return helper(0, 1, 0);
    }

    private int helper(int containDiff, int limit, int n) {
        if (n >= len) {
            return containDiff;
        }
        if (dp[containDiff][limit][n] != -1) {
            return dp[containDiff][limit][n];
        }
        int h = limit == 1 ? s[n] - '0' : 9;
        int res = 0;
        for (int i = 0; i <= h; i++) {
            if (table[i] != -1) {
                res += helper(table[i] | containDiff, limit & (i == h ? 1 : 0), n + 1);
            }
        }
        dp[containDiff][limit][n] = res;
        return res;
    }
}

刷题总结

  数位DP也是一种比较难想到的动态规划，有时间给小伙伴们多介绍几个题目。

-------------本文结束感谢您的阅读-------------
0%