【代码随想录算法训练Day35】LeetCode 1005. K 次取反后最大化的数组和、LeetCode 134.加油站、LeetCode 135.分发糖果

Day35 贪心第三天

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

两步贪心，解决问题：
1.优先取反绝对值最大的负数
2.如果所有的数都非负了，就用绝对值最小的整数消耗掉剩余的k。

class Solution {
public:
    static bool cmp(int a,int b){
        return abs(a)>abs(b);
    }
    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--;
            }
        }
        if(k%2==1) nums[nums.size()-1]*=-1;
        int res=0;
        for(int a:nums) res+=a;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

LeetCode 134.加油站

贪心思路比较简单，我们从头开始向后走，如果当前的油为负数，说明从头到现在的点都不能作为起点，就从下一个点开始，这样循环一圈就行了。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int cur=0,total=0,start=0;
        for(int i=0;i<gas.size();i++){
            cur+=gas[i]-cost[i];
            total+=gas[i]-cost[i];
            if(cur<0){
                start=i+1;
                cur=0;
            }
        }
        if(total<0) return -1;
        return start;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode 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 res=0;
        for(int i=0;i<candy.size();i++)
            res+=candy[i];
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

贪心主要在于积累思路，加油！