数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究用 C++ 编写跳跃游戏 III
假设我们有一个非负整数数组 arr，我们最初位于数组的 start 索引处。当我们出现在索引 i 处时，我们可以跳到 i + arr[i] 或 i - arr[i]，检查我们是否可以到达值为 0 的任何索引。我们必须记住，我们不得在任何时候跳出数组。因此，如果输入如下：arr = [4,2,3,0,3,1,2]，并且从 5 开始，则输出将为 true，因为移动 5 → 4 → 1 → 3，或 5 → 6 → 4 → 1 → 3。
为了解决这个问题，我们将遵循以下步骤 −
- n := arr 的大小
- 定义一个队列 q，将 start 插入 q 中，定义一个名为 visited 的集合，并将 start 插入集合 visited 中
- 当队列不为空时，
- curr := q 的首个元素，从 q 中删除首个元素
- 如果 array[curr] 为 0，则返回 true
- 如果 curr + arr[curr] < n 且 curr + arr[curr] 不存在于 visited 集合中，则
- 将 curr + arr[curr] 插入 q 中
- 将 curr + arr[curr] 插入 visited 中
- 如果 curr - arr[curr] >= 0 且 curr - arr[curr] 不存在于 visited 集合中，则
- 将 curr - arr[curr] 插入到 q 中
- 将 curr - arr[curr] 插入到 visited 中
- 返回 false
示例
让我们看看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canReach(vector<int>& arr, int start) {
int n = arr.size();
queue <int> q;
q.push(start);
set <int> visited;
visited.insert(start);
while(!q.empty()){
int curr = q.front();
q.pop();
if(arr[curr] == 0)return true;
if(curr + arr[curr] < n && !visited.count(curr + arr[curr])){
q.push(curr + arr[curr]);
visited.insert(curr + arr[curr]);
}
if(curr - arr[curr] >= 0 && !visited.count(curr - arr[curr])){
q.push(curr - arr[curr]);
visited.insert(curr - arr[curr]);
}
}
return false;
}
};
main(){
vector<int> v = {4,2,3,0,3,1,2};
Solution ob;
cout << (ob.canReach(v, 5));
}输入
[4,2,3,0,3,1,2] 5
输出
1
更新于： 30-04-2020
338 浏览
广告