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 ， 所以永遠不可能到達最后一個下標。
提示：
1 <= nums.length <= 1040 <= nums[i] <= 105
題解
題目描述給定了一個非負整數數組nums，其中數組中的每個元素表示再該位置的最大跳躍長度，目的是判斷是否能從第一個下標到達最后一個下標。
貪心算法非常適合這個問題，這道題的方法是遍歷數組，并在每一步中根據當前位置和當前位置的跳躍長度更新最大可到達的下標。在任何一步遍歷中，如果最大可達的下標超過或等于最后一個下標，則答案為true。如果迭代結束沒有到達最后一個下標，則答案為false。
class Solution {
public:bool canJump(vector<int>& nums) {int maxReach = 0; // 最遠能到達的位置for(int i = 0; i < nums.szie(); ++i){if(i > maxReach) return false; // 如果當前位置已經超過了最遠能到達的位置，就返回false}// 更新最遠能到達的位置maxReach = max(maxReach, nums[i] + i);if(maxReach >= nums.size() - 1) return true; // 如果最遠能到達的位置已經超過了數組的長度，就返回true}
};
45. 跳躍游戲 II - 力扣（LeetCode）
給定一個長度為 n 的 0 索引整數數組 nums。初始位置為 nums[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
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000- 題目保證可以到達
nums[n-1]
題解
這個題是上一個題的進階版，它指在上題的基礎上要求你找從第一個下標到最后一個下標所需跳躍的最小次數。
同樣使用貪心的方法來解決，思路是記錄每一次迭代可到達的范圍，直到到達數組的最后一個下標。
同時引入兩個變量：
currentEnd：記錄每一次跳躍前下標的跳躍邊界farthest：記錄跳躍的最遠距離
每一次遍歷，我們都更新farthest為自身和當前下標i+nums[i]的最大值。這表示從當前位置可以到達的最大下標。
如果i達到currentEnd，則表明我們已經到達當前跳躍的邊界，因為我們增加跳躍次數(+1)并將currentEnd設置為farthest。這是我們在下一次跳躍中可以到達的位置范圍。
更新currentEnd后，如果currentEnd大于等于末尾，我們就不需要繼續遍歷了
class Solution {
public:int jump(vector<int>& nums) {int jumps = 0; // 跳躍次數int currentEnd = 0; // 當前跳躍的邊界int farthest = 0; // 最遠能跳到的位置if(nums.size() == 1) return 0; // 如果數組長度為1，就不用跳了，直接返回0for(int i = 0; i < nums.size() - 1; ++i){farthest = max(nums[i] + i, farthest); // 更新最遠能跳到的位置if(i == currentEnd){ // 遇到邊界，就更新邊界，并且步數加一currentEnd = farthest;++jumps;if(currentEnd >= nums.size() - 1) return jumps; // 如果當前邊界已經超過了數組的長度，就不用再繼續計算了}}return jumps;}
};
