[LeetCode 55] Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

For example:

A = [2, 3, 1, 1, 4], return true.

A = [3, 2, 1, 0, 4], return false.

Difficulty
Medium

Related Problems
[LeetCode 45] Jump Game II H

Analysis

Greedy

Use a variable maxIndex to record the max distance that index i can reach. When we are stepping up i, we keep updating maxIndex with max(maxIndex, i + A[i]), the condition that we can reach n - 1 is that maxIndex >= n - 1.

由于只需判断能否跳到终点，我们只要在遍历数组的过程中，更新每个点能跳到最远的范围就行了，如果最后这个范围大于等于终点，就是可以跳到。

Solutions

1. Cpp solution

class Solution {
public:
    bool canJump(vector<int>& A) {
        int n = A.size();
        int maxIndex = 0;
        for(int i = 0; i <= maxIndex && i < n; i++){
            maxIndex = max(maxIndex, i + A[i]);
            if(maxIndex >= n-1) return true;
        }
        return false;
    }
};

1. Go solution ```go func canJump(nums []int) bool { maxDist := 0 for i := 0; i < len(nums) && i <= maxDist; i++ {

    maxDist = max(maxDist, i+nums[i])
    if maxDist >= len(nums)-1 {
        return true
    }
   

   } return false }

func max(a, b int) int { return int(math.Max(float64(a), float64(b))) } ```

Reference