C++如何解決跳躍游戲問題

本文小編為大家詳細介紹“C++如何解決跳躍游戲問題”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C++如何解決跳躍游戲問題”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

跳躍游戲

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 的思想來解，想想為什么呢？ 為了較快的跳到末尾，想知道每一步能跳的范圍，這里貪婪并不是要在能跳的范圍中選跳力最遠的那個位置，因為這樣選下來不一定是最優解，這么一說感覺又有點不像貪婪算法了。其實這里貪的是一個能到達的最遠范圍，遍歷當前跳躍能到的所有位置，然后根據該位置上的跳力來預測下一步能跳到的最遠距離，貪出一個最遠的范圍，一旦當這個范圍到達末尾時，當前所用的步數一定是最小步數。需要兩個變量 cur 和 pre 分別來保存當前的能到達的最遠位置和之前能到達的最遠位置，只要 cur 未達到最后一個位置則循環繼續，pre 先賦值為 cur 的值，表示上一次循環后能到達的最遠位置，如果當前位置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，這里小優化一下，判斷如果 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++如何解決跳躍游戲問題”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。