資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 實現跳躍遊戲 IV
假設我們有一個名為 arr 的整數陣列。我們最初位於索引 0。一步內，我們可以從索引 i 跳到 i + x，其中：i + x < n。i - x，其中：i - x >= 0。j，其中：arr[i] 和 arr[j] 相同，並且 i 和 j 不相同。這裡 n 是陣列的大小。我們必須找到到達陣列最後一個索引的最小步數。
因此，如果輸入類似於：
則輸出將為 3，我們需要從索引 0 跳到 4，再到 3，最後到 9，共三步。
為了解決這個問題，我們將遵循以下步驟：
定義一個對映 m
n := arr 的大小
初始化 i := 0，當 i < n 時，更新（i 增加 1），執行：
將 i 插入到 m[arr[i]] 的末尾
將 i 插入到 m[arr[i]] 的末尾
將 0 插入到 visited 中
定義一個佇列 q
初始化 lvl := 0，當 q 不為空時，更新（lvl 增加 1），執行：
sz := q 的大小
當 sz 不為零時，每次迭代 sz 減 1，執行：
curr := q 的第一個元素
從 q 中刪除元素
如果 curr 與 n - 1 相同，則
返回 lvl
i := curr
如果 i - 1 >= 0 且 i - 1 不在 visited 中，則：
將 i - 1 插入到 q 中
將 i - 1 插入到 visited 中
如果 i + 1 < n 且 i + 1 不在 visited 中，則：
將 i + 1 插入到 q 中
將 i + 1 插入到 visited 中
初始化 j := 0，當 j < m[arr[curr]] 的大小時，更新（j 增加 1），執行：
如果 (m[arr[curr], j]) 不在 visited 中，則：
將 m[arr[curr], j] 插入到 q 中
將 m[arr[curr], j] 插入到 visited 中
如果 arr[curr] 不在 m 中，則：
從 m 中刪除 arr[curr]
返回 -1
讓我們看看以下實現以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minJumps(vector<int>& arr) {
map<int, vector<int> > m;
int n = arr.size();
for (int i = 0; i < n; i++) {
m[arr[i]].push_back(i);
}
set<int> visited;
visited.insert(0);
queue<int> q;
q.push(0);
for (int lvl = 0; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
int curr = q.front();
q.pop();
if (curr == n - 1)
return lvl;
int i = curr;
if (i - 1 >= 0 && !visited.count(i - 1)) {
q.push(i - 1);
visited.insert(i - 1);
}
if (i + 1 < n && !visited.count(i + 1)) {
q.push(i + 1);
visited.insert(i + 1);
}
for (int j = 0; j < m[arr[curr]].size(); j++) {
if (!visited.count(m[arr[curr]][j])) {
q.push(m[arr[curr]][j]);
visited.insert(m[arr[curr]][j]);
}
}
if (m.count(arr[curr])) {
m.erase(arr[curr]);
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<int> v = {20,-5,-5,25,20,5,5,5,1,25};
cout << (ob.minJumps(v));
}輸入
{20,-5,-5,25,20,5,5,5,1,25}輸出
3
266 次瀏覽
