[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.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: 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.

這題是之前那道 Jump Game 的延伸，那題是問能不能到達最后一個數字，而此題只讓求到達最后一個位置的最少跳躍數，貌似是默認一定能到達最后位置的? 此題的核心方法是利用貪婪算法 Greedy 的思想來解，想想為什么呢？ 為了較快的跳到末尾，想知道每一步能跳的范圍，這里貪婪并不是要在能跳的范圍中選跳力最遠的那個位置，因為這樣選下來不一定是最優(yōu)解，這么一說感覺又有點不像貪婪算法了。其實這里貪的是一個能到達的最遠范圍，遍歷當前跳躍能到的所有位置，然后根據該位置上的跳力來預測下一步能跳到的最遠距離，貪出一個最遠的范圍，一旦當這個范圍到達末尾時，當前所用的步數一定是最小步數。需要兩個變量 cur 和 pre 分別來保存當前的能到達的最遠位置和之前能到達的最遠位置，只要 cur 未達到最后一個位置則循環(huán)繼續(xù)，pre 先賦值為 cur 的值，表示上一次循環(huán)后能到達的最遠位置，如果當前位置i小于等于 pre，說明還是在上一跳能到達的范圍內，根據當前位置加跳力來更新 cur，更新 cur 的方法是比較當前的 cur 和 i + A[i] 之中的較大值，如果題目中未說明是否能到達末尾，還可以判斷此時 pre 和 cur 是否相等，如果相等說明 cur 沒有更新，即無法到達末尾位置，返回 -1，代碼如下：

解法一：

class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0, n = nums.size(), i = 0, cur = 0;
        while (cur < n - 1) {
            ++res;
            int pre = cur;
            for (; i <= pre; ++i) {
                cur = max(cur, i + nums[i]);
            }
            if (pre == cur) return -1; // May not need this
        }
        return res;
    }
};

還有一種寫法，跟上面那解法略有不同，但是本質的思想還是一樣的，這里 cur 是當前能到達的最遠位置，last 是上一步能到達的最遠位置，遍歷數組，首先用 i + nums[i] 更新 cur，這個在上面解法中講過了，然后判斷如果當前位置到達了 last，即上一步能到達的最遠位置，說明需要再跳一次了，將 last 賦值為 cur，并且步數 res 自增1，這里小優(yōu)化一下，判斷如果 cur 到達末尾了，直接 break 掉即可，代碼如下：

解法二：

class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0, n = nums.size(), last = 0, cur = 0;
        for (int i = 0; i < n - 1; ++i) {
            cur = max(cur, i + nums[i]);
            if (i == last) {
                last = cur;
                ++res;
                if (cur >= n - 1) break;
            }
        }
        return res;
    }
};

到此這篇關于C++實現LeetCode(45.跳躍游戲之二)的文章就介紹到這了,更多相關C++實現跳躍游戲之二內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論