题目描述
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：
i + 1 需满足：i + 1 < arr.lengthi - 1 需满足：i - 1 >= 0j 需满足：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
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution:
def minJumps(self, arr: List[int]) -> int:
g = defaultdict(list)
for i, x in enumerate(arr):
g[x].append(i)
q = deque([0])
vis = {0}
ans = 0
while 1:
for _ in range(len(q)):
i = q.popleft()
if i == len(arr) - 1:
return ans
for j in (i + 1, i - 1, *g.pop(arr[i], [])):
if 0 <= j < len(arr) and j not in vis:
q.append(j)
vis.add(j)
ans += 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 | class Solution {
public int minJumps(int[] arr) {
Map<Integer, List<Integer>> g = new HashMap<>();
int n = arr.length;
for (int i = 0; i < n; i++) {
g.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
boolean[] vis = new boolean[n];
Deque<Integer> q = new ArrayDeque<>();
q.offer(0);
vis[0] = true;
for (int ans = 0;; ++ans) {
for (int k = q.size(); k > 0; --k) {
int i = q.poll();
if (i == n - 1) {
return ans;
}
for (int j : g.get(arr[i])) {
if (!vis[j]) {
vis[j] = true;
q.offer(j);
}
}
g.get(arr[i]).clear();
for (int j : new int[] {i - 1, i + 1}) {
if (0 <= j && j < n && !vis[j]) {
vis[j] = true;
q.offer(j);
}
}
}
}
}
}
|
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 | class Solution {
public:
int minJumps(vector<int>& arr) {
unordered_map<int, vector<int>> g;
int n = arr.size();
for (int i = 0; i < n; ++i) {
g[arr[i]].push_back(i);
}
vector<bool> vis(n);
queue<int> q{{0}};
vis[0] = true;
for (int ans = 0;; ++ans) {
for (int k = q.size(); k; --k) {
int i = q.front();
q.pop();
if (i == n - 1) {
return ans;
}
for (int j : g[arr[i]]) {
if (!vis[j]) {
vis[j] = true;
q.push(j);
}
}
g[arr[i]].clear();
for (int j : {i - 1, i + 1}) {
if (0 <= j && j < n && !vis[j]) {
vis[j] = true;
q.push(j);
}
}
}
}
}
};
|
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 | func minJumps(arr []int) int {
g := map[int][]int{}
for i, x := range arr {
g[x] = append(g[x], i)
}
n := len(arr)
q := []int{0}
vis := make([]bool, n)
vis[0] = true
for ans := 0; ; ans++ {
for k := len(q); k > 0; k-- {
i := q[0]
q = q[1:]
if i == n-1 {
return ans
}
for _, j := range g[arr[i]] {
if !vis[j] {
vis[j] = true
q = append(q, j)
}
}
g[arr[i]] = nil
for _, j := range []int{i - 1, i + 1} {
if 0 <= j && j < n && !vis[j] {
vis[j] = true
q = append(q, j)
}
}
}
}
}
|
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 | function minJumps(arr: number[]): number {
const g: Map<number, number[]> = new Map();
const n = arr.length;
for (let i = 0; i < n; ++i) {
if (!g.has(arr[i])) {
g.set(arr[i], []);
}
g.get(arr[i])!.push(i);
}
let q: number[] = [0];
const vis: boolean[] = Array(n).fill(false);
vis[0] = true;
for (let ans = 0; ; ++ans) {
const nq: number[] = [];
for (const i of q) {
if (i === n - 1) {
return ans;
}
for (const j of g.get(arr[i])!) {
if (!vis[j]) {
vis[j] = true;
nq.push(j);
}
}
g.get(arr[i])!.length = 0;
for (const j of [i - 1, i + 1]) {
if (j >= 0 && j < n && !vis[j]) {
vis[j] = true;
nq.push(j);
}
}
}
q = nq;
}
}
|