跳跃游戏

跳跃游戏 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;
    }
};

func canJump(nums []int) bool {
    //思路：贪心
    //最远能跳多远，如果能越过最后一格，返回 true，否则返回 false
    n := len(nums)
    farthest := 0
    for i := 0; i < n-1; i++ {
        // 更新能跳到的最远距离
        if i+nums[i] > farthest {
            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;
    }
};

func jump(nums []int) int {
    //贪心
    n := len(nums)
    end := 0 //标记可以选择的跳跃步数的最后一个
    farthest := 0 //所有可选择跳跃步数[i...end]中能够跳到的最远距离
    res := 0  //记录跳跃次数
    for i := 0; i < n-1; i++ {
        // 更新能跳到的最远距离
        if i+nums[i] > farthest {
            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;
    }
};

func canReach(arr []int, start int) bool {
    //BFS
    if arr[start] == 0 {
        return true
    }
    n := len(arr)
    isVisited := make([]bool, n)
    queue := []int{}
    queue = append(queue, start)
    isVisited[start] = true

    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        //可以达到位置 cur+arr[cur]，并且没有被搜索过
        if cur+arr[cur] < n && !isVisited[cur+arr[cur]] {
            if arr[cur+arr[cur]] == 0 {
                return true
            }
            queue = append(queue, 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
            }
            queue = append(queue, cur-arr[cur])
            isVisited[cur-arr[cur]] = true
        }
    }
    return false
}