-
Notifications
You must be signed in to change notification settings - Fork 2
/
1345.跳跃游戏 IV.js
39 lines (35 loc) · 897 Bytes
/
1345.跳跃游戏 IV.js
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
/**
* @param {number[]} arr
* @return {number}
*/
var minJumps = function(arr) {
const dp = [];
dp[arr.length - 1] = 0;
const map = {};
for (let i = 0; i < arr.length; i++) {
map[arr[i]] = map[arr[i]] || [];
map[arr[i]].push(i);
}
const queue = [arr.length - 1];
while (queue.length) {
const i = queue.shift();
if (i === 0) {
return dp[0];
}
if (i + 1 < arr.length && dp[i + 1] === undefined) {
dp[i + 1] = dp[i] + 1;
queue.push(i + 1);
}
if (i - 1 >= 0 && dp[i - 1] === undefined) {
dp[i - 1] = dp[i] + 1;
queue.push(i - 1);
}
for (const n of map[arr[i]]) {
if (n !== i && dp[n] === undefined) {
dp[n] = dp[i] + 1;
queue.push(n);
}
}
}
return 0;
};