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 is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:
You can assume that you can always reach the last index.

原问题链接：https://leetcode.com/problems/jump-game-ii/

 

问题分析

初步思路

　　因为假定每个步骤都可以走到数组的最后面，于是很容易想到一种思路。就是我们用一个等长的数组来记录到这个位置所走的最小步数。比如上面示例中的数组A = [2, 3, 1, 1 4]。在最开始索引为０的位置，它的长度为2。所以从索引0到索引0 + 2这个位置是它能走的第一步的范围。然后看索引１的值，将它和A[1]的值相加的所有范围的数字尝试比较加一，取其中较小的那个数字。概括起来说，对于任意一个位置i，我们在新建的数组里设置成steps[i + j] = Math.min(steps[i + j], steps[i] + 1)，其中j表示从1到A[i]的范围内的取值。

　　所以根据上述讨论可以得到如下的代码：

 

public class Solution {
    public int jump(int[] nums) {
        if(nums == null || nums.length <= 1) return 0;
        int n = nums.length;
        int[] steps = new int[n];
        for(int i = 1; i < n; i++) steps[i] = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++) {
            for(int j = 1; j < nums[i] && i + j < n; j++) {
                steps[i + j] = Math.min(steps[i] + 1, steps[i + j]);
            }
        }
        return steps[n - 1];
    }
}

 　　上述代码需要额外申请一个同等长度的数组空间，另外，里面的for循环在nums[i]值比较大的时候也会产生严重的性能影响。所以它的时间复杂度会达到O(N^2)。在实际的运行时候会导致超时。

 

思路改进

　　上述的问题解决思路虽然逻辑上是正确的但是执行效率比较低。因此需要想办法去改进它的执行性能。我们来看有没有别的办法。对于上述的问题，当我们从最开始的索引节点开始取步数的时候，我们最多能覆盖的范围就是A[0]的值所定的范围，如下图：

　　假定４是它所能涵盖最远的范围，那么对于1到４这个范围内的值来说，它的最小步数就是１。在没有到达数组的末尾时，我们需要继续考虑步数为２的涵盖范围。在1到4的这个范围内来取，假设中间１所取的数值范围最大，如下图：

　　这个时候，我们要取的第二步的范围是从４到９。 通过这个步骤推演，我们会发现一个规律。就是对于任何一个步数来说，它当前所能涵盖的最大范围即为所用步数最少的范围。比如前面到４只需要１步。而从当前步数涵盖的范围到下一个范围则需要从当前范围里取涵盖最大的一个。这样依次类推。

　　所以每次我们只要在某个步数所能涵盖的最大范围内设置它当前的步数，只有超过这个最大范围的时候才对这个步数加一。求下一个步数的时候则求在当前步数的范围内能涵盖的最大值。在具体的实现中，我们需要记录在每一步中它所能涵盖的最大值，每次到遍历到这个值的时候，我们的步数加一。另外，我们在每次的遍历中都要计算当前位置所能涵盖的最大范围以作为下一个步数所能涵盖的范围。

　　按照这个思路我们能得到如下的代码：

 

public class Solution {
    public int jump(int[] A) {
        int jumps = 0, curEnd = 0, curFarthest = 0;
        for (int i = 0; i < A.length - 1; i++) {
            curFarthest = Math.max(curFarthest, i + A[i]);
            if (i == curEnd) {
                jumps++;
                curEnd = curFarthest;
            }
        }
        return jumps;
    }
}

 　　这种方法的时间复杂度为O(N)，它的性能得到大幅的提升。从本质上来说这是一种贪婪的思路。我们每次都去找当前步数所能涵盖的最大范围。