Day34| Leetcode 1005. K 次取反后最大化的数组和 Leetcode 134. 加油站 Leetcode 135. 分发糖果

本文介绍: 成立，才能兼顾题目中所说的相邻两个孩子评分更高的孩子会获得更多的糖果，并且需要最少的糖果，如果反过来，取两边高的话，就会不满足最少的糖果的要求，这里也说明了，在判断左孩子比右孩子大的时候，为什么需要后序遍历的原因，如果前序遍历就没法满足。本题一共用到了两个贪心，第一个是我们的数组中有负数时每次就让绝对值最大的负数转变，直到用到 k为零，第二个贪心的地方，如果都为正数，就取最小的一个正数来让其不停的取反，如果k为奇数，反转一次就行，如果k为偶数，即不需要反转。其次，需要满足一个点：我们要让这个等式。

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

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

本题目一开始我认为直接排序，让最小的取反回来就直接结束，我太天真了，一个反例直接猝死，下面上贪心的思路：

本题一共用到了两个贪心，第一个是我们的数组中有负数时每次就让绝对值最大的负数转变，直到用到k为零，第二个贪心的地方，如果都为正数，就取最小的一个正数来让其不停的取反，如果k为奇数，反转一次就行，如果k为偶数，即不需要反转。下面上代码：

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

Leetcode 134. 加油站

题目链接 134 加油站

本题目一开始想的时候这个题目和贪心毫无关系，但是仔细看过卡哥的讲解后，恍然大物，这才是真的算法，并且才感觉到贪心思想。

每个加油站的剩余量rest[i]为ga s[i] – cost[i]。

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算 curSum。

那么局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

下面上代码:

class Solution {
public:
    int canCompleteCircuit(vector<int>&amp; gas, vector<int>&amp; 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;
    }
};

Leetcode 135. 分发糖果

题目链接 135 分发糖果

本题之前看到过，当时比较菜，没有看懂，本题目的一个核心思想：这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。其次，需要满足一个点：我们要让这个等式a[i-1]<a[i]>a[i+1]成立，才能兼顾题目中所说的相邻两个孩子评分更高的孩子会获得更多的糖果，并且需要最少的糖果，如果反过来，取两边高的话，就会不满足最少的糖果的要求，这里也说明了，在判断左孩子比右孩子大的时候，为什么需要后序遍历的原因，如果前序遍历就没法满足a[i-1]<a[i]>a[i+1]。

c and yVec[i]是之前比较右孩子大于左孩子得到的糖果数量。

局部最优：取c and yVec[i + 1] + 1 和 cand yVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

下面上代码：

class Solution {
public:
    int candy(vector<int>&amp; ratings) {
        vector<int> candyVec(ratings.size(),1);//初始化都为1
        for(int i=1;i<ratings.size();i++){
            //从前往后遍历，并且右孩子比左孩子大的情况
            if(ratings[i]>ratings[i-1]){
                candyVec[i] = candyVec[i-1]+1;
            }
        }
    for(int i=ratings.size()-2;i>=0;i--){
        //从后往前遍历，并且是左孩子比右孩子大的情况
        if(ratings[i] > ratings[i+1]){
            candyVec[i] = max(candyVec[i],candyVec[i+1]+1);
        }
    }
    int result = 0;
    for(int i=0;i<candyVec.size();i++){
        result+=candyVec[i];
    }
    return result;
    }
};