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

第34天

目录

前言

一、K次取反后最大化的数组和

1、暴力思路：

但这是时间复杂度比较大的解法，我们还可以改善一下。

2、贪心思路：

二、加油站

1、贪心思路1：

2、贪心思路2：

三、分发糖果

总结

---

前言

思念折腾人，也锻炼人，更锻造人的性格的沉稳和感情的深沉。思念别人是一种温馨，被人思念是一种幸福

---

一、K次取反后最大化的数组和

力扣

1、暴力思路：

在k还没有用完前，每次选择最小的元素，把它取反，这样就能得到最大的和。

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
		while(k--)                    //记录K的次数
        {
            int min=1e8;            
            int j=0;
            for(int i=0;isize();i++)
            {
				if(nums[i]//找出最小值
                {
					min=nums[i];
                    j=i;
                }
            }
            nums[j]=-nums[j];        //反
        }
        int sum=0;
        for(int i=0;isize();i++)        //记录和
        {
            printf("%d ",nums[i]);
			sum+=nums[i];
        }
        return sum;
    }
};

但这是时间复杂度比较大的解法，我们还可以改善一下。

2、贪心思路：

要先和最大。

1、把负数全部变成正数。

2、如果全是正数，把最小的正数变成负数。

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);        //按绝对值从大到小排序
        int i=0;
        for(i=0;isize();i++)            
        {
            if(nums[i]<0)                    //负数都反
            {
                nums[i]=-nums[i];
                k--;
            }
            if(k==0)                //用完了就退出了
            {
                break;
            }
        }
        if(k%2==1)                    //剩余的看单双数，双数等于不变
        {
            nums[nums.size()-1]*=-1;        //末尾最小
        }
        int sum=0;
        for(auto it:nums)
        {
            sum+=it;
        }
        return sum;
    }
};

二、加油站

力扣

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

1、贪心思路1：

在确定了是可以跑一圈的情况下，在中间出现了负值，说明从0到负值位置开始是行不通的，要从后面往前，找到那个可以补缺的点哪里。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int min=1e8;
        int sum=0;
		for(int i=0;isize();i++)
        {
            sum+=gas[i]-cost[i];            //从0开始跑计算总油量
			if(sum
            {
                min=sum;            //记录最小的负值
            }
        }
    
        if(sum<0)        //小于0就退出，因为不可能跑一圈了
        {
            return -1;
        }
            if(min>=0)        //如果从0开始跑可以跑一圈就返回0
        {
    	    return 0;
        }
        for(int i=gas.size()-1;i>=0;i--)    //从后往前遍历
        {
            min+=gas[i]-cost[i];        //啥时候可以填补空缺
            if(min>=0)
            return i;
        }
        return -1;
    }
};

2、贪心思路2：

如果cursum小于0了，那么【0，i】上面开始都是不行的。

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) {   // 当前累加rest[i]和 curSum一旦小于0
                start = i + 1;  // 起始位置更新为i+1
                curSum = 0;     // curSum从0开始
            }
        }
        if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return start;
    }
};

三、分发糖果

力扣

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candys(ratings.size(),1);
        for(int i=1;isize();i++)        //右孩子大于左孩子
        {
            if(ratings[i]>ratings[i-1])
            {
                candys[i]=candys[i-1]+1;        //比旁边的孩子多一个
            }
        }
        for(int i=ratings.size()-2;i>=0;i--)        //重点，重后往前
        {
            if(ratings[i]>ratings[i+1])
            {
                candys[i]=max(candys[i],candys[i+1]+1);
            }
        }
        int sum=0;
        for(auto it:candys)
        sum+=it;
        return sum;
    }
};

为什么要从后往前呢，从后往前，我们可以用处理过的结果来判断，因为前一个是处理过的，从前往后，就是依据前一个判断后一个，前一个都是没有处理过的。

---

总结

贪心没有套路，只有一点感觉，继续加油哇。