DAY33 贪心算法Ⅱ

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

想到把整体利润分解为每天的利润，就豁然开朗了。

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

55. 跳跃游戏 - 力扣（LeetCode）

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 - 力扣（LeetCode）

class Solution {
public:int jump(vector<int>& nums) {if(nums.size()==1) return 0;int curDistance=0;int nextDistance=0;int ans=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;}
};

1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

 需要注意的是如何使用sort函数实现绝对值降序排列，需要自定义cmp函数来确定排序规则。

class Solution {static bool cmp(int a,int b){return abs(a) > abs(b);
}
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(),nums.end(),cmp);for(int i=0;i<nums.size();i++){if(nums[i]<0 && k>0){nums[i]*=-1;k--;}}//如果k依旧不为0if(k%2==1) nums[nums.size()-1]*=-1;int result=0;for(int i=0;i<nums.size();i++){result+=nums[i];}return result;}
};