代码随想录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;
    }
};