[leetcode] 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 is2. (Jump1step from index 0 to 1, then3steps to the last index.)
https://oj.leetcode.com/problems/jump-game-ii/
構想1:まずDPを考え,後から前へ押すと,現在位置の最小ステップ数はその到達可能な範囲内の最小ステップ数に依存するため,その被覆範囲を遍歴する必要があり,複雑度はやや高く,O(n)のアルゴリズムではなく,目測タイムアウトである.
考え方2:欲張り.いくつかの変数、curReach、nextReachを維持し、curReachが最後まで上書きされるまで、curReachの範囲内でnextReachを更新します.
参照先:
http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html
http://blog.csdn.net/havenoidea/article/details/11853301
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 is2. (Jump1step from index 0 to 1, then3steps to the last index.)
https://oj.leetcode.com/problems/jump-game-ii/
構想1:まずDPを考え,後から前へ押すと,現在位置の最小ステップ数はその到達可能な範囲内の最小ステップ数に依存するため,その被覆範囲を遍歴する必要があり,複雑度はやや高く,O(n)のアルゴリズムではなく,目測タイムアウトである.
考え方2:欲張り.いくつかの変数、curReach、nextReachを維持し、curReachが最後まで上書きされるまで、curReachの範囲内でnextReachを更新します.
public class Solution {
public int jump(int[] A) {
if (A == null || A.length < 2)
return 0;
int n = A.length;
int step = 0;
int curReach = 0;
int nextReach = 0;
int i;
for (i = 0; i < n;) {
if (curReach >= n - 1)
break;
while (i <= curReach) {
nextReach = nextReach > (i + A[i]) ? nextReach : (i + A[i]);
i++;
}
curReach = nextReach;
step++;
}
return step;
}
public static void main(String[] args) {
System.out.println(new Solution()
.jump(new int[] { 2, 3, 1, 1, 1, 2, 3 }));
}
}参照先:
http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html
http://blog.csdn.net/havenoidea/article/details/11853301