[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 的延伸，那題是問(wèn)能不能到達(dá)最后一個(gè)數(shù)字，而此題只讓求到達(dá)最后一個(gè)位置的最少跳躍數(shù)，貌似是默認(rèn)一定能到達(dá)最后位置的? 此題的核心方法是利用貪婪算法 Greedy 的思想來(lái)解，想想為什么呢？ 為了較快的跳到末尾，想知道每一步能跳的范圍，這里貪婪并不是要在能跳的范圍中選跳力最遠(yuǎn)的那個(gè)位置，因?yàn)檫@樣選下來(lái)不一定是最優(yōu)解，這么一說(shuō)感覺(jué)又有點(diǎn)不像貪婪算法了。其實(shí)這里貪的是一個(gè)能到達(dá)的最遠(yuǎn)范圍，遍歷當(dāng)前跳躍能到的所有位置，然后根據(jù)該位置上的跳力來(lái)預(yù)測(cè)下一步能跳到的最遠(yuǎn)距離，貪出一個(gè)最遠(yuǎn)的范圍，一旦當(dāng)這個(gè)范圍到達(dá)末尾時(shí)，當(dāng)前所用的步數(shù)一定是最小步數(shù)。需要兩個(gè)變量 cur 和 pre 分別來(lái)保存當(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，說(shuō)明還是在上一跳能到達(dá)的范圍內(nèi)，根據(jù)當(dāng)前位置加跳力來(lái)更新 cur，更新 cur 的方法是比較當(dāng)前的 cur 和 i + A[i] 之中的較大值，如果題目中未說(shuō)明是否能到達(dá)末尾，還可以判斷此時(shí) pre 和 cur 是否相等，如果相等說(shuō)明 cur 沒(méi)有更新，即無(wú)法到達(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;
    }
};

還有一種寫(xiě)法，跟上面那解法略有不同，但是本質(zhì)的思想還是一樣的，這里 cur 是當(dāng)前能到達(dá)的最遠(yuǎn)位置，last 是上一步能到達(dá)的最遠(yuǎn)位置，遍歷數(shù)組，首先用 i + nums[i] 更新 cur，這個(gè)在上面解法中講過(guò)了，然后判斷如果當(dāng)前位置到達(dá)了 last，即上一步能到達(dá)的最遠(yuǎn)位置，說(shuō)明需要再跳一次了，將 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;
    }
};

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

最新評(píng)論