大家好，我是怒碼少年小碼。

本篇是貪心思想的跳躍問題專題，跳躍問題出現(xiàn)的頻率很高。

跳躍游戲

LeetCode 55：給你一個非負整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個下標。數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最后一個下標，如果可以，返回 true ；否則，返回 false 。

示例 1：

• 輸入：nums = [2,3,1,1,4]
• 輸出：true
• 解釋：可以先跳 1 步，從下標 0 到達下標 1, 然后再從下標 1 跳 3 步到達最后一個下標。

示例 2：

• 輸入：nums = [3,2,1,0,4]
• 輸出：false
• 解釋：無論怎樣，總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最后一個下標。

分析：這題的關(guān)鍵是要搞清楚題目的意思。如果當(dāng)前位置的元素是3，那么你走1/2/3步，最后如果走到的數(shù)組中的最后一個位置就算你成功！

注意： 這里很容易就陷入到底具體是跳到哪一步、走多少步的思考漩渦中。這里的關(guān)鍵是能否走到終點。所以我們要盡可能的跳躍到最遠的位置，看當(dāng)前位置最多能覆蓋到哪里，如果能覆蓋到終點我們就贏了！

如下圖：

第一個例子中，3能覆蓋{2，1，0}，2能覆蓋{1，0}，1能覆蓋{0}，而0不能覆蓋到4，所以無法達到終點。

可見，第二個例子中有2種跳法{2，1，1，4}，{2，3，1，1，4}。

定義一個變量cover表示當(dāng)前位置可以覆蓋的范圍，遍歷指針只能在cover中的范圍變化，每次i變化都要引起cover的變化（cover會得到當(dāng)前位置i的元素的補充）,我們需要找到最遠可以到達的位置，也就是需要在cover當(dāng)前本身的值和補充之后的值之間，取一個最大值。

當(dāng)cover >= nums.length - 1時，說明可以成功。

public boolean canJump(int[] nums) {if(nums.length == 1){return true;}int cover = 0 ;for(int i = 0 ; i<=cover;i++){cover = Math.max(cover , i+nums[i]);if(cover >= nums.length - 1){return true;}}return false;
}

最短跳躍問題

從上題可以看出一個數(shù)組有多種跳躍方式可以到達終點，那么最少需要幾步能跳到終點呢？這就是LeetCode 45。

這題我們可以采用：貪心+雙指針 的方法解決🤔。

• left用于遍歷數(shù)組
• steps表示一共跳了多少步
• right表示當(dāng)前位置能夠覆蓋的最大范圍

maxPosition = Math.max(maxPosition,left + nums[left]);這個還是最遠能跳到哪里。當(dāng)left == right說明當(dāng)前區(qū)間最大覆蓋區(qū)間已經(jīng)尋找完畢。

例如上面的第一個例子：

public int jump(int[] nums) {int right = 0 ;int steps = 0 ;int maxPosition = 0;for(int left = 0 ; left < nums.length - 1; left++){//最遠能跳到哪里maxPosition = Math.max(maxPosition,left + nums[left]);if(left == right){ //left遍歷到了邊界，就更新邊界并且步數(shù)加一right = maxPosition;steps++;}//right指針到了數(shù)組的最后if(right >= nums.length - 1){return steps;}}return steps;
}

END

今天這篇都是力扣上的中等難度，在面試的時候也挺常見的，多練練動手敲😎。