0935._Knight_Dialer.md

935. Knight Dialer

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/knight-dialer/

内容描述

This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1 hops.  Each hop must be from one key to another numbered key.

Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing N digits total.

How many distinct numbers can you dial in this manner?

Since the answer may be large, output the answer modulo 10^9 + 7.

 

Example 1:

Input: 1
Output: 10
Example 2:

Input: 2
Output: 20
Example 3:

Input: 3
Output: 46
 

Note:

1 <= N <= 5000

解题方案

思路 1 - 时间复杂度: O(10^N)- 空间复杂度: O(1)******

递归，超时

class Solution:
    def knightDialer(self, N):
        """
        :type N: int
        :rtype: int
        """
        lookup = {
            0: [4, 6],
            1: [6, 8],
            2: [7, 9],
            3: [4, 8],
            4: [3, 9, 0],
            5: [],
            6: [1, 7, 0],
            7: [2, 6],
            8: [1, 3],
            9: [2, 4]
        }
        
        M = 10 ** 9 + 7
        self.res = 0
        def dfs(step, cur):
            if step == N:
                self.res += 1
                self.res %= M
                return
            for nxt in lookup[cur]:
                dfs(step+1, nxt)
        
        for i in range(10):   
            dfs(1, i)
        return self.res

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

找到规律，beats 100%

代码用了haitao7哥的，我的代码太丑了

class Solution(object):
    def knightDialer(self, N):
        """
        :type N: int
        :rtype: int
        """
        moves = {
            0: [4, 6],
            1: [6, 8],
            2: [7, 9],
            3: [4, 8],
            4: [0, 3, 9],
            5: [],
            6: [0, 1, 7],
            7: [2, 6],
            8: [1, 3],
            9: [2, 4] 
        }
        M = 10 ** 9 + 7
        cur = [1] * 10
        for i in range(N-1):
            nxt = [0] * 10
            for dia, neighbors in moves.items():
                for m in neighbors:
                    nxt[m] += cur[dia]
                    nxt[m] %= M
            cur = nxt
        return sum(cur) % M

思路 3 - 时间复杂度: O(N)- 空间复杂度: O(1)******

preprocess，40 ms 秒杀一切

class Solution(object):
    moves = {
        0: [4, 6],
        1: [6, 8],
        2: [7, 9],
        3: [4, 8],
        4: [0, 3, 9],
        5: [],
        6: [0, 1, 7],
        7: [2, 6],
        8: [1, 3],
        9: [2, 4] 
    }
    M = 10 ** 9 + 7
    cache = [[1] * 10]
    cur = cache[0]
    for i in range(5000):
        nxt = [0] * 10
        for dia, neighbors in moves.items():
            for m in neighbors:
                nxt[m] += cur[dia]
                nxt[m] %= M
        cur = nxt
        cache.append(cur)
    def knightDialer(self, N):
        """
        :type N: int
        :rtype: int
        """
        return sum(self.cache[N-1]) % self.M

思路 4 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******

快速幂, 寒神真的强

68 ms

import numpy as np
class Solution(object):
    def knightDialer(self, N):
        """
        :type N: int
        :rtype: int
        """
        mod = 10**9 + 7
        if N == 1: return 10
        M = np.matrix([[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
                       [0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
                       [0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
                       [0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
                       [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
                       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                       [1, 1, 0, 0, 0, 0, 0, 1, 0, 0],
                       [0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
                       [0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
                       [0, 0, 1, 0, 1, 0, 0, 0, 0, 0]])
        res, N = 1, N - 1
        while N:
            if N & 1:
                res = res * M % mod
            M = M * M % mod
            N /= 2
        return int(np.sum(res)) % mod