中等跳跃游戏 II
33% 通过给出一个非负整数数组,你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
您在真实的面试中是否遇到过这个题? Yes 样例
给出数组A =[2,3,1,1,4],最少到达数组最后一个位置的跳跃次数是2(从数组下标0跳一步到数组下标1,然后跳3步到数组的最后一个位置,一共跳跃2次)
public class Solution {public int jump(int[] nums) {if(nums == null || nums.length == 0){return -1;}int start = 0, end = 0, jump = 0;while(end < nums.length -1){jump++;int farthest = end;for(int i = start; i <= end; i++){farthest = Math.max(farthest,nums[i]+i);if(farthest >= nums.length -1){return jump;}}//跳完这一步,下次开始的地方,保证所有的都被遍历到start = end + 1;end = farthest;}return 0;}}/*** nums: [2,3,1,1,4] nums.length = 5;* start = 0, end = 0, jump = 0;* while(end < nums.length -1){* * jump = 1;* farthest = end = 0;* i = 0*farthest = max(0,2) = 2;* start = end + 1 = 1;* end = farthest = 2;* * jump = 2;* farthest = end = 2;* i = 1*farthest = max(2,4) = 4;* return jump;*/