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

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

跳躍游戲

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 的延伸，那題是問能不能到達(dá)最后一個(gè)數(shù)字，而此題只讓求到達(dá)最后一個(gè)位置的最少跳躍數(shù)，貌似是默認(rèn)一定能到達(dá)最后位置的? 此題的核心方法是利用貪婪算法 Greedy 的思想來解，想想為什么呢？ 為了較快的跳到末尾，想知道每一步能跳的范圍，這里貪婪并不是要在能跳的范圍中選跳力最遠(yuǎn)的那個(gè)位置，因?yàn)檫@樣選下來不一定是最優(yōu)解，這么一說感覺又有點(diǎn)不像貪婪算法了。其實(shí)這里貪的是一個(gè)能到達(dá)的最遠(yuǎn)范圍，遍歷當(dāng)前跳躍能到的所有位置，然后根據(jù)該位置上的跳力來預(yù)測下一步能跳到的最遠(yuǎn)距離，貪出一個(gè)最遠(yuǎn)的范圍，一旦當(dāng)這個(gè)范圍到達(dá)末尾時(shí)，當(dāng)前所用的步數(shù)一定是最小步數(shù)。需要兩個(gè)變量 cur 和 pre 分別來保存當(dāng)前的能到達(dá)的最遠(yuǎn)位置和之前能到達(dá)的最遠(yuǎn)位置，只要 cur 未達(dá)到最后一個(gè)位置則循環(huán)繼續(xù)，pre 先賦值為 cur 的值，表示上一次循環(huán)后能到達(dá)的最遠(yuǎn)位置，如果當(dāng)前位置i小于等于 pre，說明還是在上一跳能到達(dá)的范圍內(nèi)，根據(jù)當(dāng)前位置加跳力來更新 cur，更新 cur 的方法是比較當(dāng)前的 cur 和 i + A[i] 之中的較大值，如果題目中未說明是否能到達(dá)末尾，還可以判斷此時(shí) pre 和 cur 是否相等，如果相等說明 cur 沒有更新，即無法到達(dá)末尾位置，返回 -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)友 實(shí)驗(yàn)室小紙貼校外版的博客，這里 cur 是當(dāng)前能到達(dá)的最遠(yuǎn)位置，last 是上一步能到達(dá)的最遠(yuǎn)位置，遍歷數(shù)組，首先用 i + nums[i] 更新 cur，這個(gè)在上面解法中講過了，然后判斷如果當(dāng)前位置到達(dá)了 last，即上一步能到達(dá)的最遠(yuǎn)位置，說明需要再跳一次了，將 last 賦值為 cur，并且步數(shù) res 自增1，這里小優(yōu)化一下，判斷如果 cur 到達(dá)末尾了，直接 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++如何解決跳躍游戲問題”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。