LeetCode 45. Jump Game II [Hard] [C++] 解題筆記

這題是 LeetCode 55. Jump Game 的進階題，沒做過 55. 題的朋友可以先去做做看喔。

題目給定一個array，每個位置表示在這個位置上可以走得最大範圍，需要求出最少需要多少步(Jump)才可以到達最後一個位置。

注意！這題題目保證一定可以到達最後一個位置。

EX:

    [2,3,1,1,4]

Ans: 2 ，從 index 0 跳 1 個位置到 index 1，在從 index 1 跳 3 個位置到達 index 4 (最後一個位置)

想法:

        這裡和 LeetCode 55. Jump Game 一樣，採用Greedy alogrithm，比較不一樣的是因為要知道最小跳躍次數，因此每次超出當前跳躍次數可以到達的地方時就要更新當前跳躍次數(跳躍次數+1,表示當前跳躍次數可到達的範圍都搜索完了)，然後同時更新新的跳躍次數可以到達的地方。

舉個例子，[2,3,1,1,4] 在 index 0 時進行第一次跳躍，第一次跳躍可到達的範圍為 index 0~2 ，因此在遍歷到 index 3 時至少得進行2次跳躍，而在 index 3 的時候跳躍可以到達的範圍為 index 1~4，因此跳躍2次就可以到達最後一個位置。

完整程式碼:

class Solution {
public:
    int jump(vector<int>& nums) {
        // 跳躍次數
        int steps = 0;
        // 當前跳躍次數最遠可以到達的位置, n步之遙(從頭跳n次最遠可以到的位置)
        int cur_steps_can_reach = 0;
        // n+1次跳躍最遠可以到達的位置, n+1步之遙
        int next_steps_can_reach = 0;
       
        for (int i = 0; i < nums.size(); i++) {
            // 超出n步之遙
            if (i > cur_steps_can_reach) {
                steps++;
                cur_steps_can_reach = next_steps_can_reach;
            }
            next_steps_can_reach = max(next_steps_can_reach, i + nums[i]);
        }
       
        return steps;
    }
};