JumpGame

Posted on Edited on In

problem

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:

1
2
3
4
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.

key

本题有两个易理解错的地方

  • 达到最后一个index或者超过最后一个index是可以的
  • 【2,5,0,0】第一个2可以跳两步，然后我们在5的基础上跳五步

本题采用贪心算法，算出局部最优解就可以了，当然也可以考虑dp，但本题没有这个必要

solution

1
2
3
4
5
6
public boolean canJump(int[] nums) {
		int reach = nums[0];
        for(int i = 1; i < nums.length && reach >= i; i++)
            if(i + nums[i] > reach) reach = i + nums[i];
        return reach >= (nums.length-1) ? true : false;
	}

perfect

1
I'm the perfect