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]
andi != 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.
Example 1:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404] Output: 3 Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
Example 2:
Input: arr = [7] Output: 0 Explanation: Start index is the last index. You don't need to jump.
Example 3:
Input: arr = [7,6,9,6,9,6,9,7] Output: 1 Explanation: You can jump directly from index 0 to index 7 which is last index of the array.
Example 4:
Input: arr = [6,1,9] Output: 2
Example 5:
Input: arr = [11,22,7,7,7,7,7,7,7,22,13] Output: 3
Constraints:
1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8
Solution: HashTable + BFS
Use a hashtable to store the indices of each unique number.
each index i has neighbors (i-1, i + 1, hashtable[arr[i]])
Use BFS to find the shortest path in this unweighted graph.
Key optimization, clear hashtable[arr[i]] after the first use, since all nodes are already on queue, no longer needed.
Time complexity: O(n)
Space complexity: O(n)
C++
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 |
// Author: Huahua, 124 ms, 30.5 MB class Solution { public: int minJumps(vector<int>& arr) { const int n = arr.size(); unordered_map<int, vector<int>> m; for (int i = 0; i < n; ++i) m[arr[i]].push_back(i); vector<int> seen(n); queue<int> q({0}); seen[0] = 1; int steps = 0; while (!q.empty()) { int size = q.size(); while (size--) { int i = q.front(); q.pop(); if (i == n - 1) return steps; if (i - 1 >= 0 && !seen[i - 1]++) q.push(i - 1); if (i + 1 < n && !seen[i + 1]++) q.push(i + 1); auto it = m.find(arr[i]); if (it == m.end()) continue; for (int nxt : it->second) if (!seen[nxt]++) q.push(nxt); m.erase(it); // no longer needed. } ++steps; } return -1; } }; |
Related Problems
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment