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:

1
2
3

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.

解法

贪心法解题，创建变量reach,记录可以到达的最远值，遍历数组，如果出现了reach不到当前i的情况，则说明终点已经不可能到达了。每次更新reach到的最大值。

具体代码如下：

class  {
    public boolean canJump(int[] nums) {
        int reach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (reach < i || reach >= nums.length - 1) {
                break;
            }
            reach = Math.max(reach, i + nums[i]);
        }
        if (reach >= nums.length - 1) {
            return true;
        }
        return false;
    }
}

leetcode(55) jump game 解法

解法

近期文章

近期评论

标签

热门

文章归档

分类目录

功能