跳躍游戲

55. 跳躍游戲 - 力扣（LeetCode）

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

判斷你是否能夠到達最后一個下標，如果可以，返回 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 ， 所以永遠不可能到達最后一個下標。

解

其實不用關心跳幾步，怎么跳，而是要關心最大的跳躍范圍能不能覆蓋到終點

public boolean canJump(int[] nums)
{int coverage = 0;   //覆蓋范圍for (int i = 0; i <= coverage; i++) //覆蓋范圍達不到下一個位置時，退出循環{//每遍歷一個位置，覆蓋范圍要么不變，要么延伸。coverage = Math.max(coverage, i + nums[i]);//如果終點在當前覆蓋范圍內，那一定有辦法跳到終點if (coverage >= nums.length - 1)return true;}return false;
}

跳躍游戲 Ⅱ

45. 跳躍游戲 II - 力扣（LeetCode）

給定一個長度為 n 的 0 索引整數數組 nums。初始位置為 nums[0]。（意思是nums[0]所在的位置，即索引為0處，跟上一題一個意思）

每個元素 nums[i] 表示從索引 i 向前跳轉的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉到任意 nums[i + j] 處:

• 0 <= j <= nums[i]
• i + j < n

返回到達 nums[n - 1] 的最小跳躍次數。生成的測試用例可以到達 nums[n - 1]。

示例 1:

輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是 2。從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達數組的最后一個位置。

示例 2:

輸入: nums = [2,3,0,1,4]
輸出: 2

解

public int jump(int[] nums)
{//起點即終點，不需要跳if (nums.length == 1)return 0;int maxBoundary = 0;int right = 0;int step = 0;//left負責尋找最大覆蓋范圍，right負責跳到覆蓋邊界，step負責記錄right跳躍的步數for (int left = 0; left < nums.length - 1; ++left){maxBoundary = Math.max(maxBoundary, left + nums[left]);//left在[left, right-1]之間遍歷時，maxBoundary可能會更新//所以要求left 追上 right，right再跳到 maxBoundary 處if (left == right){right = maxBoundary;step++;}//能一步跳到終點了if (right >= nums.length - 1)return step;}//跳不到（但此題不會出現這種情況）return -1;
}