LeetCode如何實現(xiàn)跳躍游戲

這篇文章給大家介紹LeetCode如何實現(xiàn)跳躍游戲，內(nèi)容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

題目

給定一個非負整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個下標 。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最后一個下標。

示例 1：輸入：nums = [2,3,1,1,4] 輸出：true

解釋：可以先跳 1 步，從下標 0 到達下標 1, 然后再從下標 1 跳 3 步到達最后一個下標。

示例 2：輸入：nums = [3,2,1,0,4] 輸出：false

解釋：無論怎樣，總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最后一個下標。

分析

簡單分析一下，由題目得出，要想到達最后一個下標，得滿足兩個條件：

• 1、假設(shè)每個位置都能跳到，那么我們只需要遍歷數(shù)組，看看有沒有位置能直接通過這個位置上的數(shù)字跳到結(jié)尾。

比如[2,3,2,1,4]，我們遍歷數(shù)字，看看哪個位置可以跳到最后，可以發(fā)現(xiàn)第三個位置的數(shù)字是2，所以可以通過第三個位置跳到最后的下標，數(shù)組成立。

• 2、上述假設(shè)成立的還有個條件就是 每個位置是否都能跳到。

比如[2,0,2,1,4]，按照上面的邏輯，第三個位置是可以跳到最后下標。但是，第三個位置是否能到達呢?如果第三個位置都到不了，那又何談最后的位置呢?在這個例子中，第一個位置為2，是可以跳到第三個位置的。

如果改成[1,0,2,1,4]，第三個位置就到不了了。

結(jié)合上述分析，我們可以得出以下解法：

public boolean canJump(int[] nums) {         //能到達的最大位置k         int k =0;         //遍歷數(shù)組         for(int i=0;i<nums.length;i++){             //如果達不到i位置，就直接返回false             if(k<i) return false;             k=Math.max(k,i+nums[i]);         }         return true;     }

也可以在每次獲取k之后再判斷一次，如果滿足條件就直接返回，減少循環(huán)次數(shù)：

public boolean canJump(int[] nums) {         //能到達的最大位置k         int k =0;         //獲取數(shù)組長度         int l = nums.length;         //遍歷數(shù)組         for(int i=0;i<l;i++){             if(k<i) return false;             k=Math.max(k,i+nums[i]);             if (k >= l-1) {              return true;             }         }         return false;     }

這種在到了某個位置，作出當前最好的選擇 的算法一般稱為貪心算法。

貪心算法的思路就是把問題分為若干個子問題，然后針對每個子問題進行局部求解，最終得到整個問題的解。

貪心算法主要有兩個特點：

• 總是作出在當前看來最好的選擇。

• 從局部的最優(yōu)選擇到整體最優(yōu)解。

所以“貪心”的意思大概就是目光短淺，只看到到眼前的最好，而不會從整體的角度思考。

雖然不能保證最后的解法是最優(yōu)的，但是這種辦法確實是能夠解決問題的，將大問題化解成小問題，小問題好好解決。

那有什么時候會有更好的解呢?這就引出 動態(tài)規(guī)劃了。

動態(tài)規(guī)劃的思想同樣是解決子問題，但是每一步的選擇都會依賴于相關(guān)的子問題解，所以有時候的復雜問題選擇動態(tài)規(guī)劃能有更好的解法，因為他對于子問題間的相關(guān)性更強。

關(guān)于LeetCode如何實現(xiàn)跳躍游戲就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。