1345. Jump Game IV
Given an array of integers arr, you are initially positioned at the first index of the array.
In one step you can jump from index i to index:
- i + 1 where: i + 1 < arr.length.
- i - 1 where: i - 1 >= 0.
- j where: arr[i] == arr[j] and i != j.
Return the minimum number of steps to reach the last index of the array.
Notice that you can not jump outside of the array at any time.
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
| class Solution {
unordered_map<int, vector<int>> jump;
unordered_set<int> jumped;
vector<int> dp;
public:
int minJumps(vector<int>& arr) {
int n = arr.size();
dp = vector<int>(n, -1);
dp[0] = 0;
for(int i = 0; i < n; i++)
jump[arr[i]].push_back(i);
queue<int> q;
q.push(0);
while(!q.empty() and dp.back() == -1) {
auto pos = q.front(); q.pop();
if(!jumped.count(arr[pos])) {
for(auto eq : jump[arr[pos]]) {
if(eq == pos) continue;
if(dp[eq] == -1) {
dp[eq] = dp[pos] + 1;
q.push(eq);
}
}
jumped.insert(arr[pos]);
}
if(pos > 0 and dp[pos - 1] == -1) {
dp[pos - 1] = dp[pos] + 1;
q.push(pos-1);
}
if(dp[pos + 1] == -1) {
dp[pos + 1] = dp[pos] + 1;
q.push(pos+1);
}
}
return dp.back();
}
};
|
