1345. 跳跃游戏 IV
题目描述
1
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
2
3
每一步，你可以从下标 i 跳到下标：
4
5
i + 1 满足：i + 1 < arr.length
6
i - 1 满足：i - 1 >= 0
7
j 满足：arr[i] == arr[j] 且 i != j
8
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
9
10
注意：任何时候你都不能跳到数组外面。
11
12
13
14
示例 1：
15
16
输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
17
输出：3
18
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。
19
示例 2：
20
21
输入：arr = [7]
22
输出：0
23
解释：一开始就在最后一个元素处，所以你不需要跳跃。
24
示例 3：
25
26
输入：arr = [7,6,9,6,9,6,9,7]
27
输出：1
28
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
29
示例 4：
30
31
输入：arr = [6,1,9]
32
输出：2
33
示例 5：
34
35
输入：arr = [11,22,7,7,7,7,7,7,7,22,13]
36
输出：3
37
38
39
提示：
40
41
1 <= arr.length <= 5 * 10^4
42
-10^8 <= arr[i] <= 10^8
Copied!
前置知识
- BFS
思路
求最少的题目，考虑动态规划，贪心 和 BFS。
这道题没有想到贪心的做法，于是考虑到了动态规划。不过由于arr[i] == arr[j] 且 i != j也可以转移，因此这里涉及到了一个连通性变更的问题，代码会比较难写。
于是继续考虑 BFS。BFS 解题需要考虑三点：
- 初始点。 这里是 0
- 终点。这里是 n - 1，其中 n 为数组长度。
- 节点状态转移。这里是题目列举的三种情况。前两个非常简单，最后一个只需要建立一个 hashtable，将相同值的索引合并到一个 list 即可。具体请看代码。
这里我直接使用 BFS 的模板提交了，结果超时了。用例卡在了 [7,7,7,7,7,7............] 无数个 7 上。
如果使用标准模板的 BFS，那么每一个 7 都会遍历到其他的所有 7，算法在这种情况下时间复杂度会退化到 $O(N^2)$。其实这里有一个上面讲的连通性的问题。如果 7 的 steps 求出来是 x，那么所有的 7 都是 x（不会比 7 大，也不会比 7 小），没有必要继续找了。因此一个剪枝就是遍历到 7 之后就将同值从 hashtable 中都清空。这个剪枝可将时间复杂度直接从 $N^2$ 降低到 $O(N)$。
代码
代码支持： Python3
1
class Solution:
2
def minJumps(self, A: List[int]) -> int:
3
dic = collections.defaultdict(list)
4
n = len(A)
5
6
for i, a in enumerate(A):
7
dic[a].append(i)
8
visited = set([0])
9
q = collections.deque([0])
10
steps = 0
11
12
while q:
13
for _ in range(len(q)):
14
i = q.popleft()
15
visited.add(i)
16
if i == n - 1: return steps
17
for neibor in dic[A[i]] + [i - 1, i + 1]:
18
if 0 <= neibor < n and neibor not in visited:
19
q.append(neibor)
20
# 剪枝
21
dic[A[i]] = []
22
steps += 1
23
return -1
Copied!
复杂度分析
- 时间复杂度：$O(N)$，其中 N 为数组长度。
- 空间复杂度：$O(N)$，其中 N 为数组长度。
大家也可以关注我的公众号《力扣加加》获取更多更新鲜的 LeetCode 题解
最近更新 1yr ago