116. Jump Game

Question

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.

Thinking

读题

1. 无负数

2. 指向0

range = A[i] + i

target = A.length-1;

贪心Greedy：

最大的距离我们可以跳到

在可以跳到的任意位置， 设最大距离是 之前最大距离和我们现在能跳的最大距离 中大的一个

Greedy 在条件

1. 可以达到目前为止

下：获得最大的可以跳的距离

比较最大跳的距离 和 目标 得到结果

public class Solution {

    /*

     * @param A: A list of integers

     * @return: A boolean

     */

    public boolean canJump(int[] A) {

        // write your code here

        int maxReach = 0;

        int target = A.length - 1;

        

        for(int i = 0; i < A.length; i++){

            int range = A[i] + i;

            // check if current maxReach can reach i;

            if(maxReach >= i){

                maxReach = Math.max(range, maxReach);    

            }

            

        }

            

        return maxReach >= target ? true : false;

        

    }

    

}