Jump Game III（C++跳跃游戏 III）

朱雀 2022-10-22 13:51 157阅读 0赞

解题思路：

（1）超时递归解法

class Solution {
    public:
        bool helper(vector<int>& arr, vector<int> vis,int start) {
            bool leftb=false,rightb=false;
            int left=start-arr[start];
            int right=start+arr[start];
            if(left>=0 && vis[left]==0) {
                vis[left]=1;
                start=left;
                if(arr[start]==0) return true;
                else leftb=helper(arr,vis,start);
            } 
    
            if(right<arr.size() && vis[right]==0) {
                vis[right]=1;
                start=right;
                if(arr[start]==0) return true;
                else rightb=helper(arr,vis,start);
            }
            return leftb||rightb;
        }
        
        bool canReach(vector<int>& arr, int start) {
            vector<int> vis(arr.size(),0);
            return helper(arr,vis,start);
        }
    };

（2）队列解法，依次寻找，访问所有未访问结点而不可达返回false

class Solution {
    public:
        bool helper(vector<int>& arr,vector<int>& v,queue<int> &q,int start) {
            q.push(start);
            while(!q.empty()) {
                start = q.front();
                v[start]=1;
                q.pop();
                if(arr[start]==0) return true;
                int left=start-arr[start];
                int right=start+arr[start];
                if(left>=0 && v[left]==0) q.push(left);
                if(right<arr.size() && v[right]==0) q.push(right);
            } 
            return false;
        }
        
        bool canReach(vector<int>& arr, int start) {
            queue<int> q;
            vector<int> v(arr.size(),0);
            return helper(arr,v,q,start);
        }
    };