跳跃游戏4Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：
- i + 1 需满足：i + 1 < arr.length
- i - 1 需满足：i - 1 >= 0
- j 需满足：arr[i] == arr[j] 且 i != j 请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意：任何时候你都不能跳到数组外面。
示例 1：
输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。
示例 2：
输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。
示例 3：
输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
提示：
- 1 <= arr.length <= 5 * 104
- -108 <= arr[i] <= 108
# 思路
BFS
# 解法
class Solution {
public int minJumps(int[] arr) {
Deque<Integer> queue = new ArrayDeque<>();
Map<Integer, Set<Integer>> map = new HashMap<>();
boolean[] visited = new boolean[arr.length];
for (int i = 0; i < arr.length; i++) {
Set<Integer> neighbors = map.getOrDefault(arr[i], new HashSet<>());
neighbors.add(i);
map.put(arr[i], neighbors);
}
queue.offer(0);
visited[0] = true;
int ans = 0;
while (!queue.isEmpty()) {
int levelSize = queue.size();
while (levelSize-- > 0) {
int peek = queue.poll();
if (peek == arr.length - 1) return ans;
if (peek + 1 < arr.length && !visited[peek + 1]) {
queue.offer(peek + 1);
visited[peek + 1] = true;
}
if (peek - 1 >= 0 && !visited[peek - 1]) {
queue.offer(peek - 1);
visited[peek - 1] = true;
}
Set<Integer> neighbors = map.get(arr[peek]);
if (neighbors != null) {
for (Integer neighbor : neighbors) {
if (!visited[neighbor]) {
queue.offer(neighbor);
visited[neighbor] = true;
}
}
}
map.remove(arr[peek]);
}
ans++;
}
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
35
36
37
38
39
40
41
42
43
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
# 总结
- 分析出几种情况，然后分别对各个情况实现
