LeetCode 45 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.

Difficulty
Hard

Related Problems
[LeetCode 55] Jump Game M

Analysis

Use greedy algorithm.

Use a variable farMost to record the maximum distance that index i can reach, use variable jumps to record how many jumps we need to get to farMost. use a variable maxAtLastJump to record farMost that last jump can reach. As long as i <= farMost, we don't increase jumps. Once i > farMost, that means we need one jump to get out of the current max reachable distance, and we record the new max reachable distance in maxAtLastJump.

Iterate over the array, and update the farMost to reflect how far we can jump to.

思路一 如果要计算最短的步数，就不能贪心每次都找最远距离了，因为有可能一开始跳的远的路径，后面反而更慢。 所以我们要探索所有的可能性，这里用快慢指针分出一块当前结点能跳的一块区域，然后再对这块区域遍历，找出这块区域中的点所能跳到的下一块区域的上下边界，每块区域都对应一步，直到上界超过终点时为之。

思路二 初始状态：last 位于位置 0，它到达 0 所需的最小步数 ret 是 0。但是，curr 表示原来的势力范围内再走一步所能达到的最远的距离。初始为 curr = A[0]。 每次 i 往前走一步，只要还在原来步数（即 ret）所在的势力范围，都更行 curr 为原来的势力范围加上走这一步所能跳到的最远的位置。 一旦 i 超出 last 位置（原来所能到达的势力范围），就把 last 更新为新的跳到的最远的位置（相当于新的势力范围）。

Solutions

1. 分区间，每块区间对应一步

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = (int) nums.size();
        int high = 0, low = 0, preHigh = 0, step = 0;
        while(high < n - 1){
            step++;
            // 记录下当前区域的上界，以便待会更新下一个区域的上界
            preHigh = high;
            for(int i = low; i <= preHigh; i++){
                //更新下一个区域的上界
                high = max(high, i + nums[i]);
            }
            //更新下一个区域的下界
            low = preHigh + 1;
        }
        return step;
    }
};

1. 势力范围更新法，超出势力范围就更新新势力范围

/*
 * We use "last" to keep track of the maximum distance that can be reached
 * by using the minimum steps "ret", whereas "curr" is the maximum distance
 * that can be reached by using "ret+1" steps. Thus, curr = max(curr, i+A[i]) where 0 <= i <= last.
 */

class Solution {
public:
    int jump(vector<int> & A) {
        int ret = 0;
        int last = 0;
        int curr = 0;
        for (int i = 0; i < n; ++i) {
            if (i > last) {
                last = curr;
                ++ret;
            }
            curr = max(curr, i+A[i]);
        }
        return ret;
    }
};

1. 其他方法 从最后一个开始，找到第一个能到最后的，再往前找第一个能到新的位置的，直到第 0 位。大数据会超时。

class Solution {
public:
    int jump(vector<int>& A) {
        int n = (int) A.size();
        int i = n - 1;
        int step = 0;
        while(i > 0){
            for(int j = 0; j < i; j++){
                if(A[j] + j >= i){
                    step++;
                    i = j;
                    break;
                }
            }
        }
        return step;
    }
};

1. Go solution

func jump(nums []int) int {
    maxLastJump, farMost, jumps := 0, 0, 0

    for i, v := range nums {
        if i > maxLastJump {
            maxLastJump = farMost
            jumps++
        }

        farMost = max(farMost, i+v)
    }

    return jumps
}

func max(a, b int) int {
    return int(math.Max(float64(a), float64(b)))
}

Reference

http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html http://www.cnblogs.com/TenosDoIt/p/3719630.html