leetcode-45：跳躍游戲 II
- 題目
- 解題
- 方法一：回溯
題目
題目鏈接
給你一個非負整數陣列 nums ，你最初位于陣列的第一個位置，
陣列中的每個元素代表你在該位置可以跳躍的最大長度，
你的目標是使用最少的跳躍次數到達陣列的最后一個位置，
假設你總是可以到達陣列的最后一個位置，
示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是 2，
從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達陣列的最后一個位置，
示例 2:
輸入: nums = [2,3,0,1,4]
輸出: 2
解題
方法一：回溯
更加推薦第一種寫法,思路比較清晰，
本題的思路就是獲取每一步的范圍
上圖例子中，在i=0時，走第一步,res=1
i=2時,第一步走完，準備走第二步, res=2
i=4時，第二步走完，并步打算走第三步(對于終點要特殊情況考慮)if(i!=nums.size()-1) ,否則的話res=3就不符合題意了
class Solution {
public:
int jump(vector<int>& nums) {
int curDistance=0;
int nextDistance=0;
int res=0;
for(int i=0;i<nums.size();i++){
nextDistance=max(nextDistance,i+nums[i]);
if(curDistance==i){
if(i!=nums.size()-1){// 如果當前覆寫最遠距離下標不是終點
curDistance=nextDistance;
res++;
}
}
}
return res;
}
};
這里是為了上面的 對于終點的情況，要特殊考慮，進行了簡化，
索引i只需要走到nums.size()-2就行了
- 如果移動下標等于當前覆寫最大距離下標， 需要再走一步
- 如果移動下標不等于當前覆寫最大距離下標，說明當前覆寫最遠距離就可以直接達到終點了，不需要再走一步
class Solution {
public:
int jump(vector<int>& nums) {
int CurDistance=0;
int NextDistance=0;
int res=0;
for(int i=0;i<nums.size()-1;i++){ //nums.size()-1是關鍵
NextDistance=max(i+nums[i],NextDistance);
if(i==CurDistance){
CurDistance=NextDistance;
res++;
}
}
return res;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/338200.html
標籤：其他