数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
