122.買賣股票的最佳時機II

講解鏈接：https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html

簡單思路：逐個計算連續兩天的股票差值，sum初始為零，只有出售股票賺錢（為正值）時，計入sum中

class Solution {
public:int maxProfit(vector<int>& prices) {vector<int> Diff(prices.size()-1,0);int sum = 0;for(int i=0;i<prices.size()-1;i++) {Diff[i] = prices[i+1]-prices[i];if(Diff[i]<=0)continue;elsesum+=Diff[i];}return sum;}
};

55. 跳躍游戲

講解鏈接：https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html

不用一步一步推過程，
局部最優，計算
cover記錄最大到達的下標位置
更新cover： i+nums[i] 和 當前最大到達下標

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(i+nums[i],cover);if(cover >= nums.size()-1)return true;}return false;}
};

45.跳躍游戲II

講解鏈接：https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html

計算下一步的最大到達距離
若當前最遠距離下標未到終點，ans(記錄步數)加一
然后更新為當前最大覆蓋距離

class Solution {
public:int jump(vector<int>& nums) {if(nums.size()==1)return 0;//記錄最遠距離下標int curDistance = 0;//記錄走的步數int ans = 0;int nextDistance = 0;for(int i=0;i<nums.size();i++) {//更新下一步覆蓋的最遠距離下標nextDistance = max(nums[i]+i,nextDistance);//遇到走的最遠距離的時候還沒有到結尾if(i==curDistance) {//需要再走一步ans ++;//更新覆蓋最遠距離下標curDistance = nextDistance;//最遠距離到集合終點，結束if(nextDistance >= nums.size() -1)break;}}return ans;}
};