LeetCode_935_Knight_Dialer骑士拨号器

發表於 | 分類於 ， |
字數統計: 1.3k | 閱讀時長 ≈ 5

垃圾博主，在线抄作业

骑士拨号器

题目

国际象棋中的骑士可以按下图所示进行移动：

这一次，我们将 “骑士” 放在电话拨号盘的任意数字键（如上图所示）上，接下来，骑士将会跳 N-1 步。每一步必须是从一个数字键跳到另一个数字键。

每当它落在一个键上（包括骑士的初始位置），都会拨出键所对应的数字，总共按下 N 位数字。

你能用这种方式拨出多少个不同的号码？

因为答案可能很大，所以输出答案模 10^9 + 7。

菜鸡做题步骤

当然，是看了题解再来写的代码。

首先，还是得手算前几种情况，以更好地理解这个问题（我后来手算时才发现我对解答还是有错误的理解的）。

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
class Solution {
     public int[][] jump;

    public now_and_next tmp;
    int output=0;

    private class now_and_next{
        int[] now;
        int[] next;

        public now_and_next() {
            this.now = new int[]{1,1,1,1,1,0,1,1,1,1};
            this.next = new int[]{0,0,0,0,0,0,0,0,0,0};
        }

        public void initialize(){
            for (int i = 0; i < 10; i++) {
                now[i] = next[i];
                next[i] =0;
            }
        }
    }

    public Solution() {
        this.jump = new int[][]{{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 3}, {2, 4}};
        tmp = new now_and_next();
    }

    public int knightDialer(int N) {
        if (N == 1){
            return 10;
        }
        for (int i = 1; i < N; i++) {
            one_pass(tmp);
        }
        for(int i:tmp.now){
            output += i;
            
            output%=1000000007;
        }
        return output;
    }

    public int[] getJump1(int num) {
        return jump[num];
    }

    public void one_pass(now_and_next tmp){
        
        for (int i = 0; i < 10; i++) {
            for(int j:getJump1(i)){
                tmp.next[j]+=tmp.now[i]%1000000007;
                tmp.next[j] %= 1000000007;
            }
        }
        tmp.initialize();
    }
}

看到矩阵快速幂，虽然不懂他的意思，但想到可以用矩阵来解决这个问题：

竖着的代表每一个按键，横着代表当前案件跳一次可以到达的按键。
只需用这个矩阵N次左乘就能得到 按N次的所有情况中，最后一位是X（X为0~4、6~9）的次数 的矩阵。

大佬题解1

在N>=2时，除数字5以外的9个数字都是可到达的。

每跳一步，数字的变化如图所示：

图片表示，当骑士处于“1”处时，下一跳将在“6”或“8”；骑士处于“4”处时，下一跳将在“3”或“0”或”9”;骑士处于“0”处时，下一跳将在“4”或“6”…………

我们可以发现，1、3、7、9处于对称位置；2，8处于对称位置;4，6处于对称位置。因此，我们可以将数字分为4个状态，命名为A、B、C、D。其中A:{1,3,7,9},B:{2,8},C:{4,6},D:{0}。

我们用f(X,n)表示：在状态X下，跳跃n步能够得到不同数字的个数。则状态转移方程为：

1
2
3
4
f(A,n)=f(B,n-1)+f(C,n-1)
f(B,n)=2*f(A,n-1)
f(C,n)=2*f(A,n-1)+f(D,n-1)
f(D,n)=2*f(C,n-1)

解释为：
处于状态A中的数字(1,3,7,9)通过一次跳跃要么变成状态B(2,8)，要么变成状态C(4,6)
处于状态B中的数字(2,8)通过一次跳跃有两种方式变成状态A(1,3,7,9)
处于状态C中的数字(4,6)通过一次跳跃有两种方式变成状态A(1,3,7,9)，还有一种方式变成状态D(0)
处于状态D中的数字(0)通过一次跳跃有两种方式变成状态C(4,6)

通过迭代，我们即可求解。

代码

1
2
3
4
5
6
7
8
9
class Solution:
    def knightDialer(self, N: int) -> int:
        if N==1: return 10
        #分别为状态A,B,C,D
        nums=[1,1,1,1]
        for _ in range(N-1):
            nums=[nums[1]+nums[2], 2*nums[0], 2*nums[0]+nums[3], 2*nums[2]]
        #状态A有4个数字，B有2个数字，C有2个数字，D有1个数字
        return (4*nums[0]+2*nums[1]+2*nums[2]+nums[3])%1000000007
复杂度分析
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

矩阵快速幂

如果我们把上面的状态转移过程使用矩阵来表示的话，那么我们可以得到这个式子：

$$
\begin{bmatrix}
A\\
B\\
C\\
D\\
\end{bmatrix}=
\begin{bmatrix}
0 & 1 & 1 & 0\\
2 & 0 & 0 & 0\\
2 & 0 & 0 & 1 \\
0 & 0 & 2 & 0 \\
\end{bmatrix}^{n-1}
\begin{bmatrix}
1\\
1\\
1\\
1\\
\end{bmatrix}
$$

其中，A、B、C、D代表在n-1次迭代结束后，处于状态A、B、C、D的可能个数。

最终的答案即为(4*A+2*B+2*C+D)%1000000007

复杂度分析
  • 时间复杂度：$O(log(n))$ （由于矩阵快速幂的时间复杂度为O(log(n)) ）
  • 空间复杂度：$O(1)$

参考资料：

  1. 4状态，动态规划Python解,时间复杂度O(log(n))
  2. MathJax 快速参考
  3. MathJax基础（2）：矩阵
  4. MathJax在线
  5. [小技巧]让Hexo在使用Mathjax时支持多行公式