貪心|122.買賣股票的最佳時機II驾胆、55.跳躍游戲、45.跳躍游戲II
122.買賣股票的最佳時機II
思路
局部最優(yōu)：收集每天的正利潤贱呐，全局最優(yōu)：求得最大利潤丧诺。
利潤分解
代碼：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
for(int i = 0; i < prices.size() - 1; i++){
int price = prices[i + 1] - prices[i];
ans += max(price, 0);
}
return ans;
}
};
參考詳解
55.跳躍游戲
思路
貪心算法局部最優(yōu)解：每次取最大跳躍步數(shù)（取最大覆蓋范圍），整體最優(yōu)解：最后得到整體最大覆蓋范圍吼句，看是否能到終點锅必。
代碼：
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover = 0;
if(nums.size() == 1) return true;
for(int i = 0; i <= cover; i++){
cover = max(nums[i] + i, cover);
if (cover >= nums.size() - 1) {
return true;
}
}
return false;
}
};
參考詳解
45.跳躍游戲II
思路
首先 起始位置為0，覆蓋范圍為零惕艳。然后遍歷目前的數(shù)組，因為本題目一定有解驹愚，所以我們記錄在目前的覆蓋范圍內(nèi)最大的可跳躍值（在目前跳躍范圍中我們最遠可以到達的值）這個值是目前遍歷的index加該index所對應的數(shù)組的值
（nums[i] + i）远搪。當遍歷到當前覆蓋范圍的末尾，我們首先發(fā)現(xiàn)覆蓋范圍小于數(shù)組長度逢捺，說明我們需要再跳躍一步谁鳍，而且我們已經(jīng)收集到了目前跳躍范圍內(nèi)，能跳躍到的最大位置。此時given我們需要再跳躍一步倘潜，我們要更新覆蓋范圍绷柒，這個新范圍就是我們之前記錄的最大范圍值。
代碼：
class Solution {
public:
int jump(vector<int>& nums) {
int cover = 0, cnt = 0, next = 0;
if(nums.size() == 1) return cnt;
for(int i = 0; i <= cover; i++) { //在覆蓋范圍內(nèi)判斷
next = max(next, nums[i] + i); //next 記錄的是覆蓋范圍內(nèi)的最大下一跳
if(i == cover) { //已經(jīng)到達覆蓋范圍
if(cover < nums.size() - 1) { //但還未到達終點
cnt++; //跳數(shù)增加
cover = next; //跳到最大下一跳
if(cover >= nums.size() - 1) break; //到達終點結(jié)束
} else break;
}
}
return cnt;
}
};
