首页 > 代码库 > leetcode_Jump Game

leetcode_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.

思路:

和求Max Subarray类似,维护一个当前元素能够跳至的最大值,每循环一次更新reach=Math.max(nums[i]+1,reach),当i>reach或i>=nums.length的时候循环终止,最后看循环是否到达了最后。到达最后则返回true,否则,返回false.

代码:

public boolean canJump(int[] nums) {
        int i=0;
        for(int reach=0;i<nums.length&&i<=reach;i++)
        {
        	reach=Math.max(nums[i]+i,reach);
        }
        return i==nums.length;
    }

leetcode_Jump Game