文章目錄
- Leetcode45
- 1.問題描述
- 2.解決方案
Leetcode45
1.問題描述
2.解決方案
思路關鍵在于：在當前步覆寫范圍內找一個下一步能走最遠的，作為下一步的選擇！
官方說法：以最小的步數增加最大的覆寫范圍，直到覆寫范圍覆寫到了終點！
代碼實作也思路清晰
1.在i<=curDistance范圍內找到最大的nextDistance
2.在i==curDistance進行判斷要不要再走一步
2.1 不用走了
2.2 再走一步
2.3 剪枝，如果這到終點了直接回傳(這一步不一定會提升效率說實話)
代碼實作有個注意的點，官方的curDistance初始化是為零，我初始化為了nums[0]，其實都可以，初始化為零不過就是第一次回圈后把nums[0]賦給了curDistance，效果一樣的
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.size()==1) return 0;
int ans=1;
int curDistance=nums[0];
int nextDistance=0;
for(int i=1;i<nums.size();i++){
//1.在i<=curDistance范圍內找到最大的nextDistance
nextDistance=max(nextDistance,nums[i]+i);
//2.在i==curDistance進行判斷要不要再走一步
if(i==curDistance){
//2.1 不用走了
if(curDistance==nums.size()-1) return ans;
//2.2 再走一步
curDistance=nextDistance;
ans++;
//2.3 剪枝，如果這到終點了直接回傳(這一步不一定會提升效率說實話)
if(nextDistance>=nums.size()-1) return ans;
}
}
return ans;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/302580.html
標籤：其他
上一篇：Unity筆記-09-玩家控制器