LC 1345. 跳跃游戏 IV
题目描述
这是 LeetCode 上的 1345. 跳跃游戏 IV ，难度为 困难。
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标：
i + 1满足：i + 1 < arr.lengthi - 1满足：i - 1 >= 0j满足：arr[i] == arr[j]且i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意：任何时候你都不能跳到数组外面。
示例 1：1
2
3
4
5输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。
示例 2：1
2
3
4
5输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。
示例 3：1
2
3
4
5输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
示例 4：1
2
3输入：arr = [6,1,9]
输出：2
示例 5：1
2
3输入：arr = [11,22,7,7,7,7,7,7,7,22,13]
输出：3
提示：
- $1 <= arr.length <= 5 * 10^4$
- $-10^8 <= arr[i] <= 10^8$
单向 BFS
根据跳跃规则，我们能够进行「前后跳」和「等值跳」，问题为到达结尾位置的最少步数，容易想到 BFS。
为了方便进行「等值跳」，我们可以先使用「哈希表」记录某个值有哪些下标。
在进行 BFS 时，假如当前走到的位置为 $t$，我们尝试将 $t - 1$、$t + 1$ 和与 $arr[t]$ 等值的位置进行入队，为了防止重复同队，我们可以使用 $dist$ 数组记录到达某个位置的最小步数（初始化为 INF），只有 $dist[ne]$ 为 INF 时，该点没有被遍历过，可以入队并更新最小步数。
但光使用 $dist$ 还不能确保复杂度为 $O(n)$，因为每次都需要遍历与 $arr[t]$ 等值的下标，为确保等值下标的遍历只会发生一次，我们需要在将等值下标添加到队列后，将 $arr[t]$ 从哈希表中移除。
容易证明每次将于 $arr[t]$ 的等值元素添加到队列后，将 $arr[t]$ 从哈希表中移除的正确性：
首次检索到 $arr[t]$ 值时，必然是最小步数，记为 $step$，此时 BFS 做法将其他等值下标距离更新为 $step + 1$：
- 若 $arr[t]$ 与结尾元素值相等，且 $t$ 为 $n - 1$，此时 $step$ 即是答案；
若 $arr[t]$ 与结尾元素值相等，但 $t$ 不为 $n - 1$，此时会再跳一步到达结尾位置，即 $step + 1$ 为答案。那么是否可能存在使用比 $step + 1$ 更小的步数，也能到达结尾的位置呢？
答案是：可能存在，但如果最后是通过「等值跳」到达结尾位置的话，不可能存在比 $step + 1$ 更小的步数。
由于我们每次加入等值时都会进行哈希表的移除，因此到达 $t$ 的方式不可能是「等值跳」，而只能是「前后跳」。假设是通过前跳到达位置 $t$，即点分布如图，步数满足等于 $step + 1$：
假设是通过后跳到达位置 $t$，即点分布如图，步数满足「如果是等值跳到达结尾，步数为 $step + 1$」：
综上，如果 $n - 1$ 是经过「等值跳」加入队列的话，起所能达到的最小步数必然为发起点 $t$ 的最小步数 $+1$。
也就是说，即使首次等值跳，加入队列后会将其从哈希表中进行移除，正确性也是可以保证的。
基于此，我们可以额外增加一个 trick，就是在构建哈希表的时候，使用「倒序」的形式构建等值下标列表，这样可以确保如果最后位置是通过「等值跳」而来是，能够优先出队。
代码（感谢 @Benhao 和 @🍭可乐可乐吗 同学提供的其他语言版本）：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
39class Solution {
int INF = 0x3f3f3f3f;
public int minJumps(int[] arr) {
int n = arr.length;
Map<Integer, List<Integer>> map = new HashMap<>();
// 倒序插入 list，相当于给 deque 增加一个同层「下标越大，优先出队」的作用
for (int i = n - 1; i >= 0; i--) {
List<Integer> list = map.getOrDefault(arr[i], new ArrayList<>());
list.add(i);
map.put(arr[i], list);
}
int[] dist = new int[n];
Arrays.fill(dist, INF);
Deque<Integer> d = new ArrayDeque<>();
d.addLast(0);
dist[0] = 0;
while (!d.isEmpty()) {
int t = d.pollFirst(), step = dist[t];
if (t == n - 1) return step;
if (t + 1 < n && dist[t + 1] == INF) {
d.addLast(t + 1);
dist[t + 1] = step + 1;
}
if (t - 1 >= 0 && dist[t - 1] == INF) {
d.addLast(t - 1);
dist[t - 1] = step + 1;
}
List<Integer> list = map.getOrDefault(arr[t], new ArrayList<>());
for (int ne : list) {
if (dist[ne] == INF) {
d.addLast(ne);
dist[ne] = step + 1;
}
}
map.remove(arr[t]);
}
return -1; // never
}
}
-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
37class Solution {
public:
int minJumps(vector<int>& arr) {
const int inf = 0x3f3f3f3f;
int n = arr.size();
unordered_map<int, vector<int>> map;
for(int i = n - 1; ~i; i--) {
map[arr[i]].push_back(i);
}
vector<int> dist(n, inf);
queue<int> q;
q.push(0);
dist[0] = 0;
while(q.size()) {
auto t = q.front(), step = dist[t];
q.pop();
if(t == n - 1) return step;
if(t + 1 < n and dist[t + 1] == inf) {
q.push(t + 1);
dist[t + 1] = step + 1;
}
if(t - 1 >= 0 and dist[t - 1] == inf) {
q.push(t - 1);
dist[t - 1] = step + 1;
}
const auto& list = map[arr[t]];
for(auto ne :list) {
if(dist[ne] == inf) {
q.push(ne);
dist[ne] = step + 1;
}
}
map[arr[t]].clear(); //or map.erase(arr[t]);
}
return -1;
}
};
-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
26class Solution:
def minJumps(self, arr: List[int]) -> int:
n = len(arr)
mp = defaultdict(list)
for i, num in enumerate(arr):
mp[num].append(i)
dist = [inf] * n
d = deque([0])
dist[0] = 0
while len(d) > 0:
t = d.popleft()
step = dist[t]
if t == n - 1:
return step
for ne in mp[arr[t]]:
if dist[ne] == inf:
d.append(ne)
dist[ne] = step + 1
mp.pop(arr[t])
if dist[t + 1] == inf:
d.append(t + 1)
dist[t + 1] = step + 1
if t and dist[t - 1] == inf:
d.append(t - 1)
dist[t - 1] = step + 1
return -1
-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
35const INF int = 0x3f3f3f3f
func minJumps(arr []int) int {
n := len(arr)
mp := map[int][]int{}
dist := make([]int, len(arr))
for i := 0; i < n; i++{
list := mp[arr[i]]
list = append(list, i)
mp[arr[i]] = list
dist[i] = INF
}
d := []int{0}
dist[0] = 0
for len(d) > 0{
t := d[0]
step := dist[t]
if t == n - 1{
return step
}
d = d[1:]
list := mp[arr[t]]
delete(mp, arr[t])
list = append(list, t + 1)
if t > 0 {
list = append(list, t - 1)
}
for _, ne := range list {
if dist[ne] == INF {
dist[ne] = step + 1
d = append(d, ne)
}
}
}
return -1
}
- 时间复杂度：预处理出
map的复杂度为 $O(n)$；跑一遍BFS得到答案复杂度为 $O(n)$。整体复杂度为 $O(n)$ - 空间复杂度：$O(n)$
双向 BFS
自然也能够使用「双向 BFS」进行求解。
不了解「双向 BFS」的同学，可以先看前置🧀：【图论搜索专题】如何使用「双向 BFS」解决搜索空间爆炸问题 & 【图论搜索专题】双向 BFS 模板题 。
双向 BFS 能够有效解决搜索空间爆炸问题，本题使用双向 BFS 的话，可以不进行哈希表的 remove 操作。
代码：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
61class Solution {
int[] arr;
int INF = 0x3f3f3f3f;
int n;
Map<Integer, List<Integer>> map = new HashMap<>();
public int minJumps(int[] _arr) {
arr = _arr;
n = arr.length;
if (n == 1) return 0;
for (int i = n - 1; i >= 0; i--) {
List<Integer> list = map.getOrDefault(arr[i], new ArrayList<>());
list.add(i);
map.put(arr[i], list);
}
Deque<Integer> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
int[] dist1 = new int[n], dist2 = new int[n];
Arrays.fill(dist1, INF);
Arrays.fill(dist2, INF);
d1.addLast(0);
dist1[0] = 0;
d2.addLast(n - 1);
dist2[n - 1] = 0;
while (!d1.isEmpty() && !d2.isEmpty()) {
int t = -1;
if (d1.size() < d2.size()) t = update(d1, d2, dist1, dist2);
else t = update(d2, d1, dist2, dist1);
if (t != -1) return t;
}
return -1; // never
}
int update(Deque<Integer> d1, Deque<Integer> d2, int[] dist1, int[] dist2) {
int m = d1.size();
while (m-- > 0) {
int t = d1.pollFirst(), step = dist1[t];
if (t + 1 < n) {
if (dist2[t + 1] != INF) return step + 1 + dist2[t + 1];
if (dist1[t + 1] == INF) {
d1.addLast(t + 1);
dist1[t + 1] = step + 1;
}
}
if (t - 1 >= 0) {
if (dist2[t - 1] != INF) return step + 1 + dist2[t - 1];
if (dist1[t - 1] == INF) {
d1.addLast(t - 1);
dist1[t - 1] = step + 1;
}
}
List<Integer> list = map.getOrDefault(arr[t], new ArrayList<>());
for (int ne : list) {
if (dist2[ne] != INF) return step + 1 + dist2[ne];
if (dist1[ne] == INF) {
d1.addLast(ne);
dist1[ne] = step + 1;
}
}
map.remove(arr[t]);
}
return -1;
}
}
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
其他「图论搜索 / 模拟」内容
题太简单？不如来学习热乎的 简单图论搜索题 🍭🍭🍭
- 常规 BFS（二维转一维）
- 常规 BFS/迭代加深（结合二叉树）
- 多源 BFS
- 双向 BFS
- 双向 BFS Ⅱ
- 双向 BFS Ⅲ（结合并查集）
- 灵活运用多种搜索方式（启发式）
- 灵活运用多种搜索方式 Ⅱ（启发式）
- 灵活运用多种搜索方式 Ⅲ（启发式 结合状态压缩）
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1345 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
