本文共 1828 字，大约阅读时间需要 6 分钟。
Jump Game II
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.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
public class Solution { public int jump(int[] A) { int count = 0, max = 0; for (int i = 0, nextMax = 0; i <= max && i < A.length - 1; i++) { nextMax = Math.max(nextMax, i + A[i]); if (i == max) { max = nextMax; count++; } } // if there is no way to get to the end, return -1 return max >= A.length - 1 ? count : -1;}}上述代码参考leetcode官网的解答Hi All, below is my AC solution:
public int jump(int[] A) { int maxReach = A[0]; int edge = 0; int minstep = 0; for(int i = 1; i < A.length; i++) { if (i > edge) { minstep += 1; edge = maxReach; if(edge > A.length - 1) return minstep; } maxReach = Math.max(maxReach, A[i] + i); if (maxReach == i): return -1; } return minstep;} When iterate the array, I set an edge for the Search phase, which means that if I exceeds the edge, the minstep must add one and the maxReach will be update. And when the last index is within the range of the edge, output the minstep.
[2, 3, 1, 1, 4]
First, the edge is 0; Second, after start iterate the array, it exceeds the edge 0 when reaching the A[0] and update the edge to 2; Third, after it reach the A[2], it exceeds the edge 2 and update the new edge to the maxReach 4. Finally, end of the array is inside the edge, output the minstep.
转载地址：http://jsuni.baihongyu.com/