代码随想录day34

1005.K次取反后最大化的数组和 

本题主要是想到排序的时候要按绝对值大小排序。

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){nums[i]*=-1;k--;}}if(k%2==1) nums[nums.size()-1]*=-1;int res=0;for(int num:nums){res+=num;}return res;}
};

134. 加油站

局部最优就是当前累加和小于0就以下一个站点为起始站点，全局最优就是找到一个站点能走一圈。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int cursum=0;int totalsum=0;int start=0;for(int i=0;i<gas.size();i++){cursum+=(gas[i]-cost[i]);totalsum+=(gas[i]-cost[i]);if(cursum<0){start=i+1;cursum=0;}}if(totalsum<0) return -1;return start;}
};

错因：1、开始加的不是净增量2、没有单独算totalsum

135. 分发糖果

这种需要考虑两边的题目，要先看一边，再考虑另一边，不然容易顾此失彼。

class Solution {
public:int candy(vector<int>& rating) {vector<int> res(rating.size(),1);for(int i=1;i<rating.size();i++){if(rating[i]>rating[i-1]){res[i]=res[i-1]+1;}}for(int i=rating.size()-2;i>=0;i--){if(rating[i]>rating[i+1]){res[i]=max(res[i+1]+1,res[i]);}}int sum=0;for(int num:res){sum+=num;}return sum;}
};