BiruLyu
7/28/2017 - 10:21 PM

45. Jump Game II(#).java

``````class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return 0;

farest = nums[0];
i = 1;
count = 1;
start = 1;
while(farest < len(nums) - 1):
end = farest + 1;
for i in range(start,end):
farest = max(farest, i + nums[i]);
count += 1;
start = end;

return count;``````
``````public class Solution {
public int jump(int[] nums) {
int len = nums.length;
int start = 0, current = 0, last = 0, step = 0;
while(start<len){
if(start>last){
step++;
last = current;
}
current = current>nums[start]+start?current:nums[start]+start;
start++;
}
return step;
}
}``````
``````public class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length < 2) return 0;
int len = nums.length;
int farthest = nums[0];
int end = farthest;
int i = 1;
int cnt = 1;
while (farthest < len - 1) {
while (i <= farthest) {
end = Math.max(end, nums[i] + i);
//if (end >= len - 1) return cnt;
i++;
}
cnt++;
farthest = end;
}
return cnt;

}
}``````