LeetCode Q55 Jump Game

Given an array of non-negative integers nums, 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.

  • First, initialize end is 0, it makes sure that we jump to max position later.
  • Initialize maxPosition = 0, it keep looking for max position
  • Traverse the nums array
  • if we ever found end is smaller than current index, that means nums[end] is 0, we return false
  • Updating maxPostion, find max between maxPosition and current index + current number
  • let end = maxPosition if we reach end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean canJump(int[] nums) { 
int end = 0;
int maxPosition = 0;
for(int i = 0; i < nums.length - 1; i++){
//当前更新超过了边界,那么意味着出现了 0 ,直接返回 false
if(end < i){
return false;
}
//找能跳的最远的
maxPosition = Math.max(maxPosition, nums[i] + i);//现在的数加上现在的index,表示了最远可以到第几步

if( i == end){ //遇到边界,就更新边界,并且步数加一
end = maxPosition;
}
}
//最远的距离是否到答末尾
return maxPosition>=nums.length-1;
}