122. 買賣股票的最佳時(shí)機(jī) II
題目鏈接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
算法思路：
貪心的思想。只要去考慮每一天的利潤(rùn)，今天的利潤(rùn)是今天的股票價(jià)格-昨天的股票價(jià)格赏参，只取正數(shù)的利潤(rùn)土思。
class Solution {
public:
? ? int maxProfit(vector<int>& prices) {
? ? ? ? int sum = 0;
? ? ? ? for(int i=1;i<prices.size();i++)
? ? ? ? {
? ? ? ? ? ? sum += prices[i]-prices[i-1]>0?prices[i]-prices[i-1]:0;
? ? ? ? }
? ? ? ? return sum;
? ? }
};
55. 跳躍游戲
題目鏈接：https://leetcode.cn/problems/jump-game/
算法思想：
遍歷當(dāng)前走到的步數(shù)能覆蓋的范圍萌壳，然后計(jì)算下一個(gè)覆蓋范圍，當(dāng)覆蓋范圍能覆蓋終點(diǎn)，則可以走到。否則走不到煤搜。
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); //計(jì)算出最大的覆蓋范圍，然后再去遍歷這個(gè)覆蓋范圍
? ? ? ? ? ? if(cover>=nums.size()-1)
? ? ? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? return false;
? ? }
};
https://leetcode.cn/problems/jump-game-ii/
算法思想：
用for循環(huán)模擬走到的地方唧席。
nextdistance記錄當(dāng)前i下一步能走到的最大覆蓋范圍
curdistance記錄當(dāng)前的最大覆蓋范圍
如果i走到當(dāng)前覆蓋范圍的最遠(yuǎn)位置卻還沒到達(dá)終點(diǎn)的時(shí)候擦盾，步數(shù)需要+1，然后更新當(dāng)前覆蓋范圍為下一步的覆蓋范圍淌哟，重新走迹卢。
class Solution {
public:
? ? int jump(vector<int>& nums) {
? ? ? ? //記錄下一步的最遠(yuǎn)距離下標(biāo)
? ? ? ? //判斷當(dāng)前的覆蓋范圍是否已經(jīng)到達(dá)終點(diǎn)了，沒有到達(dá)就記錄步數(shù)+1
? ? ? ? //走到下一步時(shí)更新當(dāng)前覆蓋范圍下標(biāo)
? ? ? ? int nextdistance = 0;
? ? ? ? int curdistance = 0;
? ? ? ? int ans = 0;
? ? ? ? if(nums.size()==1)
? ? ? ? ? ? return 0;
? ? ? ? for(int i=0;i<nums.size();i++)
? ? ? ? {
? ? ? ? ? ? nextdistance = max(nums[i]+i, nextdistance);
? ? ? ? ? ? if(i == curdistance) //如果已經(jīng)走到最遠(yuǎn)的地方了徒仓，還是沒到終點(diǎn)
? ? ? ? ? ? if(i <=nums.size()-1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ans++;
? ? ? ? ? ? ? ? curdistance = nextdistance;
? ? ? ? ? ? ? ? if(curdistance >=nums.size()-1)
? ? ? ? ? ? ? ? ? ? break;? ? ? ? ? ? ? ?
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? return ans;
? ? }
};
