C++實現(xiàn)跳躍游戲的方法

這篇文章主要講解了“C++實現(xiàn)跳躍游戲的方法”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“C++實現(xiàn)跳躍游戲的方法”吧！

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 的延伸，那題是問能不能到達最后一個數(shù)字，而此題只讓求到達最后一個位置的最少跳躍數(shù)，貌似是默認(rèn)一定能到達最后位置的? 此題的核心方法是利用貪婪算法 Greedy 的思想來解，想想為什么呢？ 為了較快的跳到末尾，想知道每一步能跳的范圍，這里貪婪并不是要在能跳的范圍中選跳力最遠(yuǎn)的那個位置，因為這樣選下來不一定是最優(yōu)解，這么一說感覺又有點不像貪婪算法了。其實這里貪的是一個能到達的最遠(yuǎn)范圍，遍歷當(dāng)前跳躍能到的所有位置，然后根據(jù)該位置上的跳力來預(yù)測下一步能跳到的最遠(yuǎn)距離，貪出一個最遠(yuǎn)的范圍，一旦當(dāng)這個范圍到達末尾時，當(dāng)前所用的步數(shù)一定是最小步數(shù)。需要兩個變量 cur 和 pre 分別來保存當(dāng)前的能到達的最遠(yuǎn)位置和之前能到達的最遠(yuǎn)位置，只要 cur 未達到最后一個位置則循環(huán)繼續(xù)，pre 先賦值為 cur 的值，表示上一次循環(huán)后能到達的最遠(yuǎn)位置，如果當(dāng)前位置i小于等于 pre，說明還是在上一跳能到達的范圍內(nèi)，根據(jù)當(dāng)前位置加跳力來更新 cur，更新 cur 的方法是比較當(dāng)前的 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;
    }
};

還有一種寫法，跟上面那解法略有不同，但是本質(zhì)的思想還是一樣的，關(guān)于此解法的詳細(xì)分析可參見網(wǎng)友 實驗室小紙貼校外版的博客，這里 cur 是當(dāng)前能到達的最遠(yuǎn)位置，last 是上一步能到達的最遠(yuǎn)位置，遍歷數(shù)組，首先用 i + nums[i] 更新 cur，這個在上面解法中講過了，然后判斷如果當(dāng)前位置到達了 last，即上一步能到達的最遠(yuǎn)位置，說明需要再跳一次了，將 last 賦值為 cur，并且步數(shù) 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++實現(xiàn)跳躍游戲的方法”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對C++實現(xiàn)跳躍游戲的方法這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！