第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0935. 骑士拨号器
题目地址 (935. 骑士拨号器）
题目描述
1
国际象棋中的骑士可以按下图所示进行移动：
Copied!
Could not load image
1
这一次，我们将 “骑士” 放在电话拨号盘的任意数字键（如上图所示）上，接下来，骑士将会跳 N-1 步。每一步必须是从一个数字键跳到另一个数字键。
2
3
每当它落在一个键上（包括骑士的初始位置），都会拨出键所对应的数字，总共按下 N 位数字。
4
5
你能用这种方式拨出多少个不同的号码？
6
7
因为答案可能很大，所以输出答案模 10^9 + 7。
8
9
10
11
示例 1：
12
13
输入：1
14
输出：10
15
示例 2：
16
17
输入：2
18
输出：20
19
示例 3：
20
21
输入：3
22
输出：46
23
24
25
提示：
26
27
1 <= N <= 5000
Copied!
前置知识
- DFS
- 记忆化搜索
公司
- 暂无
深度优先遍历（DFS）
思路
这道题要求解一个数字。并且每一个格子能够跳的状态是确定的。 因此我们的思路就是“状态机”（动态规划），暴力遍历（BFS or DFS），这里我们使用 DFS。（注意这几种思路并无本质不同）
对于每一个号码键盘，我们可以转移的状态是确定的，我们做一个”预处理“，将这些状态转移记录到一个数组 jump，其中 jump[i] 表示 i 位置可以跳的点（用一个数组来表示）。问题转化为：
- 从 0 开始所有的路径
- 从 1 开始所有的路径
- 从 2 开始所有的路径
- ...
- 从 9 开始所有的路径
不管从几开始思路都是一样的。 我们使用一个函数 f(i, n) 表示
骑士在 i 的位置，还剩下 N 步可以走的时候可以拨出的总的号码数。那么问题就是求解 f(0, N) + f(1, N) + f(2, N) + ... + f(9, N)。对于 f(i, n)，我们初始化 cnt 为 0，由于 i 能跳的格子是 jump[i]，我们将其 cnt += f(j, n - 1)，其中 j 属于 jump[i]，最终返回 cnt 即可。不难看出，这种算法有大量重复计算，我们使用记忆化递归形式来减少重复计算。 这种算法勉强通过。
代码
1
class Solution:
2
def knightDialer(self, N: int) -> int:
3
cnt = 0
4
jump = [[4, 6], [6, 8], [7, 9], [4, 8], [
5
0, 3, 9], [], [0, 1, 7], [2, 6], [1, 3], [2, 4]]
6
visited = dict()
7
8
def helper(i, n):
9
if (i, n) in visited: return visited[(i, n)]
10
if n == 1:
11
return 1
12
cnt = 0
13
for j in jump[i]:
14
cnt += helper(j, n - 1)
15
visited[(i, n)] = cnt
16
return cnt
17
for i in range(10):
18
cnt += helper(i, N)
19
return cnt % (10**9 + 7)
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
朴素遍历
思路
我们使用迭代的形式来优化上述过程。我们初始化十个变量分别表示键盘不同位置能够拨出的号码数，并且初始化为 1。接下来我们只要循环 N - 1 次，不断更新状态即可。不过这种算法和上述算法并无本质不同。
代码
1
class Solution:
2
def knightDialer(self, N: int) -> int:
3
a0 = a1 = a2 = a3 = a4 = a5 = a6 = a7 = a8 = a9 = 1
4
for _ in range(N - 1):
5
a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 = a4 + a6, a6 + a8, a7 + \
6
a9, a4 + a8, a0 + a3 + a9, 0, a0 + a1 + a7, a2 + a6, a1 + a3, a2 + a4
7
return (a0 + a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9) % (10**9 + 7)
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
Could not load image
最近更新 1yr ago