【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.)

【解析】

題意：給定一個數組，每個元素代表從該位置可以跳過的距離，問從第一個位置跳到最後一個位置至少需要跳多少次。

說明：上一題 Jump Game 要我們求能不能到達最有一個位置，這道題應該隐含一定可以到達最後一個位置，是以不用考慮不能到達最後一個位置的情況。

思路：依舊是貪心，隻不過需要多出一個數組來記錄跳的路徑。

在 【LeetCode】Jump Game 解題報告 基礎上，改進代碼如下：

public class Solution {
    public int jump(int[] A) {
        int[] pre = new int[A.length]; //pre[i] keep the last postion which can jump to i
        int reach = 0;
        for (int i = 0; i < A.length; i++) {
            if (i + A[i] > reach) {
                // reach+1 ... i+A[i] are reached by jumping from i
                for (int j = reach + 1; j <= i + A[i] && j < A.length; j++) {
                    pre[j] = i;
                }
                reach = i + A[i];
            }
        }
        
        int ans = 0;
        int k = A.length - 1;
        while (k > 0) {
            k = pre[k];
            ans++;
        }
        return ans;
    }
}