55.跳躍游戲
55.跳躍游戲
難度：中等
給定一個非負整數陣列 nums ，你最初位于陣列的 第一個下標 ，
陣列中的每個元素代表你在該位置可以跳躍的最大長度，
判斷你是否能夠到達最后一個下標，
** **
示例 1：
輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然后再從下標 1 跳 3 步到達最后一個下標，
示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置，但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最后一個下標，
分析：
用貪心法，遍歷陣列每個元素，記錄從當前下標和對應的元素，確定能夠到達的最大距離，若大于當前最大距離則更新，否則不變，
以題目中的示例一
[2, 3, 1, 1, 4]
為例：
我們一開始在位置 0，可以跳躍的最大長度為 2，因此最遠可以到達的位置被更新為 2；
我們遍歷到位置 1，由于 1≤2，因此位置 1 可達，我們用 1 加上它可以跳躍的最大長度 3，將最遠可以到達的位置更新為 4，由于 4 大于等于最后一個位置 4，因此我們直接回傳 True，
我們再來看看題目中的示例二
[3, 2, 1, 0, 4]
我們一開始在位置 0，可以跳躍的最大長度為 3，因此最遠可以到達的位置被更新為 3；
我們遍歷到位置 1，由于 1≤3，因此位置 1 可達，加上它可以跳躍的最大長度 2 得到 3，沒有超過最遠可以到達的位置；
位置 2、位置 3 同理，最遠可以到達的位置不會被更新；
我們遍歷到位置 4，由于 4>3，因此位置 4 不可達，我們也就不考慮它可以跳躍的最大長度了，
在遍歷完成之后，位置 4 仍然不可達，因此我們回傳 False，
class Solution {
public:
bool canJump(vector<int>& nums) {
int maxlen=0;
int a=0;
for(int i=0;i<nums.size();i++)
{
if(i<=maxlen){
a=nums[i];
maxlen=max(maxlen,a+i);
if(maxlen>=nums.size()-1)
return true;
}
}
return false;
}
};
- 跳躍游戲 II
45. 跳躍游戲 II
給你一個非負整數陣列 nums ，你最初位于陣列的第一個位置，
陣列中的每個元素代表你在該位置可以跳躍的最大長度，
你的目標是使用最少的跳躍次數到達陣列的最后一個位置，
假設你總是可以到達陣列的最后一個位置，
** **
示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是 2，
** 從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達陣列的最后一個位置，**
示例 2:
輸入: nums = [2,3,0,1,4]
輸出: 2
思路
1，如果某一個作為 起跳點 的格子可以跳躍的距離是 3，那么表示后面 3 個格子都可以作為 起跳點，
** 11. 可以對每一個能作為 起跳點 的格子都嘗試跳一次，把 能跳到最遠的距離 不斷更新，**
2，如果從這個 起跳點 起跳叫做第 1 次 跳躍，那么從后面 3 個格子起跳 都 可以叫做第 2 次 跳躍，
3，所以，當一次 跳躍 結束時，從下一個格子開始，到現在 能跳到最遠的距離，都 是下一次 跳躍 的 起跳點，
** 31. 對每一次 跳躍 用 for 回圈來模擬，**
** 32. 跳完一次之后，更新下一次 起跳點 的范圍，**
** 33. 在新的范圍內跳，更新 能跳到最遠的距離，**
記錄 跳躍 次數，如果跳到了終點，就得到了結果，
class Solution {
public:
int jump(vector<int>& nums) {
int res=0;
int end=0; //記錄下一跳能到達的位置
for(int i=0;i<nums.size();i++)
{
if(end>=nums.size()-1)
return res;
int maxlen=0;
for(int j=i;j<=end;j++) //從當前到end之間能到達的最大位置作為下一跳能到達的最大位置
{
maxlen=max(maxlen,j+nums[j]);
}
end=maxlen;
res++;
}
return res;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/460822.html
標籤：其他
下一篇：免費建站