day34 K次取反后最大化的数组和 加油站 分发糖果

题目1：1005 K次取反后最大化的数组和

题目链接：1005K次取反后最大化的数组和

题意

将整数数组nums[i]中某个元素替换为nums[i]重复k次，返回可能的最大和

一次贪心（性能差）

每次都对最小值取相反数（最小数是负数时，取相反数增加最大值；最小数是正数时，取相反数数减小最大值的程度最小）,这样才可能得到最大和

代码

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int sum = 0;
        //每次排序,最小值都会在前面，对最小值取相反数,得到的可能的最大和
        while(k!=0){
            sort(nums.begin(),nums.end());//每次都排序一次,这样每次都会得到最小值,对最小值取相反数
            nums[0] *= -1;
            k--;
        }
        for(int i=0;i<nums.size();i++){
            sum += nums[i];
        } 
        return sum;  
    }
};

• 时间复杂度: O(knlogn)
• 空间复杂度: O(1)

两次贪心（性能好）

数组中全部为负数时，优先对绝对值大的负数取反；数组中全部为正数时，取绝对值最小的负数取反，得到的才是可能的最大和

代码

class Solution {
public:
    static bool cmp(int a,int b){
        return abs(a) > abs(b);
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int sum = 0;
        //按照绝对值从大到小排序
        sort(nums.begin(),nums.end(),cmp);
        //将数组中的元素全部转化为正数
        for(int i=0;i<nums.size();i++){
            if(nums[i]<0 && k>0){
                nums[i] *= -1;
                k--;
            }
        }
        if(k%2==1) nums[nums.size()-1] *= -1;
        for(int i=0;i<nums.size();i++) sum += nums[i];
        return sum;
    }
};

• 时间复杂度: O(nlogn)
• 空间复杂度: O(1)

题目2：134 加油站

题目链接：134 加油站

题意

环路上有n个加油站 第i个加油站有汽油gas[i]升

汽车油箱容量无限，从第i个加油站开往第i+1个加油站需消耗cost[i]升汽油，开始油箱为空

若可以顺序绕环路一周，返回出发的加油站编号，否则返回-1，解唯一

贪心策略

统计每个站点的剩余油量，如果剩余油量cursum变为负数，说明该加油点之前（包括该加油点）的每个站点都不能绕一周，所以选择后面的加油点作为起始位置，继续统计剩余油量

代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int cursum = 0;//剩余油量
        int totalsum = 0;//全部油量
        for(int i=0;i<gas.size();i++) totalsum += gas[i] - cost[i];
        if(totalsum<0) return -1;
        int start = 0;
        for(int i=0;i<gas.size();i++){
            cursum += gas[i] - cost[i];//剩余油量
            if(cursum<0){
                start = i+1;
                cursum = 0;//重新统计剩余油量
            }
        }
        return start;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

题目3：135 分发糖果

题目链接：135 分发糖果

题意

每个孩子至少分配一个糖果，相邻两个孩子评分更高的获得更多糖果，至少需要准备糖果的数量

两次贪心策略

先确定一边再确定另一边 先比较左边孩子比右边孩子低的情况，再比较右边孩子比左边孩子低的情况，两次糖果数量取最大值

代码

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candy(ratings.size(),1);
        //从前向后遍历 左孩子比右孩子小
        for(int i=1;i<ratings.size();i++){
            if(ratings[i]>ratings[i-1]) candy[i] = candy[i-1]+1;
        }
        //从后向前遍历 右孩子比左孩子小
        for(int i=ratings.size()-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]) candy[i] = max(candy[i],candy[i+1]+1);
        }
        int result = 0;
        for(int i=0;i<candy.size();i++){
            result += candy[i];
        }
        return result;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)