给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
public int jump(int[] A) {int count = 0;int maxPos = 0;int lastMaxPos = -1;for (int i = 0; i < A.length && maxPos < A.length; i++) {if (i + A[i] >= A.length-1){count++;if (i < maxPos)count++;break;}if (i == lastMaxPos){count+=2;}if (maxPos <= i+A[i]){lastMaxPos = maxPos;maxPos = i+A[i];}}return count;}
自己的解法非常丑陋并且可读性极差
dalao解法：
public int jump2(int[] A) {// write your code hereif (A == null || A.length == 0) {return -1;}int start = 0, end = 0, jumps = 0;while (end < A.length - 1) {jumps++;int farthest = end;for (int i = start; i <= end; i++) {farthest = Math.max(farthest, A[i] + i);}start = end + 1;end = farthest;}return jumps;
}
summary:在jump1的基础上，每个阶段的开始总是在前一阶段的结尾的基础上进行