跳跃游戏

跳跃游戏 I、跳跃游戏 II、跳跃游戏 III

55.跳跃游戏 I

class Solution {
public:
    bool canJump(vector<int>& nums) {
        //思路：贪心
        //最远能跳多远，如果能越过最后一格，返回 true，否则返回 false
        int n=nums.size();
        int farthest = 0;
        for(int i=0;i<n-1;i++){
            // 更新能跳到的最远距离
            farthest = max(farthest, i+nums[i]);
            // 可能碰到了 0，卡住跳不动了
            if(farthest<=i) return false;
        }
        return farthest >= n-1;
    }
};

45.跳跃游戏 II

class Solution {
public:
    int jump(vector<int>& nums) {
        //贪心
        int n=nums.size();
        int end=0; //标记可以选择的跳跃步数的最后一个
        int farthest=0; //所有可选择跳跃步数[i...end]中能够跳到的最远距离
        int res=0;  //记录跳跃次数
        for(int i=0;i<n-1;i++){
            // 更新能跳到的最远距离
            farthest = max(farthest, i+nums[i]);
            if(end==i){ 
                res++;
                end = farthest;
            }
        }
        return res;
    }
};

1306.跳跃游戏 III

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        //BFS
        if(arr[start]==0){
            return true;
        }
        int n=arr.size();
        vector<bool> isVisited(n);
        queue<int> q;
        q.push(start);
        isVisited[start] = true;

        while(!q.empty()){
            int cur = q.front();
            q.pop();
            //可以达到位置 cur+arr[cur]，并且没有被搜索过
            if(cur+arr[cur]<n && !isVisited[cur+arr[cur]]){
                if(arr[cur+arr[cur]] == 0){
                    return true;
                }
                q.push(cur+arr[cur]);
                isVisited[cur+arr[cur]] = true;
            }
            //可以达到位置 cur-arr[cur]，并且没有被搜索过
            if(cur-arr[cur]>=0 && !isVisited[cur-arr[cur]]){
                if(arr[cur-arr[cur]] == 0){
                    return true;
                }
                q.push(cur-arr[cur]);
                isVisited[cur-arr[cur]] = true;
            }
        }
        return false;
    }
};