55. Jump Game (1)

Link

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.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

Solution

從最尾端開始看是否可以到某個確定可以到達的點

設定一個index (lastPosition)指向一定可以到達array最尾端的index，並保持這個index是最靠前的，剩下只要判斷其餘的點是否可以到達這個index，若可以就讓該點取代這個index使他成為下一次的判斷基點。

class Solution {
    public boolean canJump(int[] nums) {
        int lastPosition = nums.length -1;
        for(int i = nums.length -1; i >= 0; i--){
            if(nums[i] >= lastPosition-i){
                lastPosition = i;
            }
        }
        return lastPosition == 0;
    }
}