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.

Analysis

  1. 用i从左边开始扫描
  2. 计算每一点可以到达的最远index，update这个index
  3. 注意i的条件，不能out of bound，也不能大于最远index
  4. 最后看i是否能够到达A的边界

Code

public class Solution {
    public boolean canJump(int[] nums) {
        int i=0;
        for(int reach=0; i<nums.length && i<=reach; i++){
            reach = Math.max(reach, i+nums[i]);
            if (reach>=nums.length) {return true;}//如果已经超过边界就可以直接return了
        }
        return i==nums.length;
    }
}

Reference