首页 > 代码库 > LeetCode: Jump Game II 解题报告
LeetCode: Jump Game II 解题报告
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.)
SOLUTION 1:
参考：http://blog.csdn.net/fightforyourdream/article/details/14517453
我们可以使用贪心法来解决这个问题。
从后往前思考问题。以 des = len - 1反向思考。思考能到达它的最远的距离是多少。
例子：
2 3 1 1 4
i = 1
上例子中index i = 2是达到4的最远的距离。这时index i = 1 到4是最后一步的最优解，因为其它的解，如果跳到index = 2, 3 到达4为最后一步，那么倒数第二步既然可以到达 index = 2, 3 也可以到达index = 1，所以跳到index = 1步数会是一样的。所以其它的解最好的情况也就是与从index = 2跳过去一样而已。
而前面的点因为距离限制 ，有可能只能跳到index = 1,而不可以跳到index = 2, 3.所以 将倒数第二步设置在index = 1可以得到最多的解。
1 package Algorithms.greedy; 2 3 public class Jump { 4 public static void main(String[] strs) { 5 int[] A = {2, 3, 1, 1, 4}; 6 System.out.println(jump(A)); 7 } 8 9 public static int jump(int[] A) {10 if (A == null || A.length == 0) {11 return 0;12 }13 14 int len = A.length;15 16 int sum = 0;17 18 int des = len - 1;19 while (des > 0) { // destination index20 for (int i = 0; i < des; i++) { // 不断向前移动dest21 if (A[i] + i >= des) { // 说明从i位置能1步到达dest的位置22 sum++;23 des = i; // 更新dest位置，下一步就是计算要几步能调到当前i的位置24 //break; // 没必要再继续找，因为越早找到的i肯定越靠前，说明这一跳的距离越远25 // 这一行可以去掉， des = i，不符合for的条件，会自动break.26 System.out.println("sum:" + sum);27 System.out.println("des:" + des);28 }29 }30 }31 32 return sum;33 }34 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/greedy/Jump.java
LeetCode: Jump Game II 解题报告