C ++中的Jump Game III

假设我们有一个非负整数arr的数组，我们最初位于数组的起始索引处。当我们出现在索引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-arr [curr]插入q

• 将curr-arr [curr]插入访问

• 将curr + arr [curr]插入q

• 将curr + arr [curr]插入访问

• curr：= q的前元素，从q删除前元素

• 如果array [curr]为0，则返回true

• 如果curr + arr [curr] <n并且curr + arr [curr]不存在于访问集中，则

• 如果curr-arr [curr]> = 0并且curr-arr [curr]在访问集中不存在，则

• 返回假

示例

让我们看下面的实现以更好地理解-

#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