[LeetCode] 55. Jump Game 跳躍游戲

這道題說的是有一個非負整數(shù)的數(shù)組，每個數(shù)字表示在當前位置的最大跳力（這里的跳力指的是在當前位置為基礎(chǔ)上能到達的最遠位置），求判斷能不能到達最后一個位置，開始博主以為是必須剛好到達最后一個位置，超過了不算，其實是理解題意有誤，因為每個位置上的數(shù)字表示的是最大的跳力而不是像玩大富翁一樣搖骰子搖出幾一定要走幾。這里可以用動態(tài)規(guī)劃 Dynamic Programming 來解，維護一個一維數(shù)組 dp，其中 dp[i] 表示達到i位置時剩余的跳力，若到達某個位置時跳力為負了，說明無法到達該位置。接下來難點就是推導(dǎo)狀態(tài)轉(zhuǎn)移方程啦，想想啊，到達當前位置的剩余跳力跟什么有關(guān)呢，其實是跟上一個位置的剩余跳力（dp 值）和上一個位置新的跳力（nums 數(shù)組中的值）有關(guān)，這里新的跳力就是原數(shù)組中每個位置的數(shù)字，因為其代表了以當前位置為起點能到達的最遠位置。所以當前位置的剩余跳力（dp 值）和當前位置新的跳力中的較大那個數(shù)決定了當前能到的最遠距離，而下一個位置的剩余跳力（dp 值）就等于當前的這個較大值減去1，因為需要花一個跳力到達下一個位置，所以就有狀態(tài)轉(zhuǎn)移方程了：dp[i] = max(dp[i - 1], nums[i - 1]) - 1，如果當某一個時刻 dp 數(shù)組的值為負了，說明無法抵達當前位置，則直接返回 false，最后循環(huán)結(jié)束后直接返回 true  即可，參見代碼如下：

解法一：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        for (int i = 1; i < nums.size(); ++i) {
            dp[i] = max(dp[i - 1], nums[i - 1]) - 1;
            if (dp[i] < 0) return false;
        }
        return true;
    }
};

其實這題最好的解法不是 DP，而是貪婪算法 Greedy Algorithm，因為這里并不是很關(guān)心每一個位置上的剩余步數(shù)，而只希望知道能否到達末尾，也就是說我們只對最遠能到達的位置感興趣，所以維護一個變量 reach，表示最遠能到達的位置，初始化為0。遍歷數(shù)組中每一個數(shù)字，如果當前坐標大于 reach 或者 reach 已經(jīng)抵達最后一個位置則跳出循環(huán)，否則就更新 reach 的值為其和 i + nums[i] 中的較大值，其中 i + nums[i] 表示當前位置能到達的最大位置，參見代碼如下：

解法二：

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

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

最新評論