一、LeetCode 1005.K次取反后最大化的数组和
题目链接/文章讲解/视频讲解:https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html
状态:已解决
1.思路
还是那个问题,绝对值固定,但要想和最大,根据我们的常识,当然是整个数组都为正数,即都对数组的和有利的情况是最优情况。设负数的个数为m,那么我们就可以根据这个想法分为两种情况:
(1)m = 0:也就是没有负数,那么这种情况我们翻转那个数呢?当然是最小的那个数,这样想,我们总是要翻转一个数的,要使得翻转后相加的和最小,那么我们就应该选择翻转后对我们影响最小的数,对和影响最小的负数,当然是负数中最大的数(这样减的少),也就是翻转前正数中最小的数。
第一个翻转的数很容易就想到了,但是当k>1时,我们还要继续往下翻,此时又应该翻转哪个数了呢?值倒数第二小的正数吗?大漏特漏!!!我们不妨再来看看这个数组,第一次翻转后,数组中就有了一个负数,有负数的情况下,当然是优先翻转负数,才能使得我们的数组之和最大。因此,我们继续翻转第一次翻转得到的负数,实则第二次翻转与第一次翻转的依然是同一个位置的数,且这个位置也很特别,一直都是排序后的数组的第一个元素(最小元素)。
第二次翻转后,数组又变回了原数组,后续如果要继续翻转就重复前两次翻转的过程......
经过前面的讨论,我们可以知道,在没有负数的前提下,每次翻转的实则都是排序后数组的第一个元素,也就是最小的元素,我们只需要重复翻转它,直到翻转次数等于k。
(2)m >0:也就是存在负数的情况。跟我们上面讨论的一样,有负数优先翻转负数,如果存在多个负数,要翻转负数中最小的一个(变正后加的多),另外多个负数时,k>1的情况下也依然优先翻转负数,直到负数全部被翻转,此时数组中没有负数的存在,变成了第一种情况,后续就按照第一种情况持续翻转直到次数等于k。
总结一下:不知道大家有没有发现,无论是情况1还是情况2,我们每次翻转的实则都是数组中最小的元素。因此可以得到暴力思路,每次翻转最小元素后都进行排序,这样我们只需要一直翻转nums[0]即可。
2.代码实现
(1)暴力解法(时间复杂度较高)
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
while(k--){
nums[0]=-nums[0];
sort(nums.begin(),nums.end());
}
int result = 0;
for(int i=0;i<nums.size();i++){
result += nums[i];
}
return result;
}
};
(2)贪心解法:
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
int i=0;
for(;i<nums.size() && nums[i]<0 && k;i++){
nums[i] = -nums[i];
k--;
}//先翻转完所有负数
sort(nums.begin(),nums.end());//翻转完后,要将数组排个序
while(k){
nums[0] = -nums[0];
k--;
}//翻转正数(一直都是第一个元素)
int result = 0;
for(int i=0;i<nums.size();i++){
result += nums[i];
}//计算结果
return result;
}
};
二、134. 加油站
题目链接/文章讲解/视频讲解:https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html
状态:已解决
1.思路
如果能跑完一圈,那么就说明总油量减去总消耗大于等于0,并且到每个加油站时的剩油量也一定是大于等于0的。
到每个加油站的剩油量rest[i]=gas[i]-cost[i]。从0开始累加rest[i],和记为curSum,一旦curSum<0,则说明[0,i]区间都不能作为起始位置,因为这个区间选择任何一个位置作为起点,到i这里都会断油,那么起始位置从i+1算起,再从0计算curSum。
那么为什么一旦[0,i] 区间和为负数,起始位置就可以是i+1呢,i+1后面就不会出现更大的负数吗?如果出现更大的负数,那么依旧更新i,向后遍历,直到不出现为负数的情况,那么起始位置又变成终止时的新的i的i+1了。那有没有可能 在[0,i] 区间中选某某个点作为起点,累加到i这里curSum也大于零呢? 如图:
如果 curSum<0 说明 区间和1 + 区间和2 < 0, 那么 假设从上图中的位置开始计数curSum不会小于0的话,就是 区间和2>0,则区间和1只能 < 0,也满足我们的选择条件,由于数组从左到右遍历,故理论上我们就直接会选择区间1和区间2中间的位置了,根本遍历不到后面去。
那么局部最优:当前累加rest[i]的和curSum一旦小于0,起始位置至少要是i+1,因为从i之前开始一定不行。全局最优:找到可以跑一圈的起始位置。
2.代码实现
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;//整体小于0时无解
return start;
}
};
三、135. 分发糖果
题目链接/文章讲解/视频讲解:https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html
状态:已解决
1.思路
这道题目要求评分相邻大的分得的糖果更多,给出一个分糖策略使得需要的糖数最少。要让总糖数最少,那么我们每次给相邻孩子分糖时,评分高的比评分低的孩子只多分到一颗糖,这样就能让最后的总糖数最少。那么,怎样分糖才能实现题目要求的分糖策略呢?遍历数组,兼顾两侧,使得一个元素左右得分比它高的元素分的糖多一个,评分低的比它少一个吗?不行,这样可能会顾此失彼!例如,得分nums为[3,1,2,5,6],初始大家都分得一颗,从下标为1的元素开始遍历,如果要兼顾两侧,那么nums[0]=2,nums[2]=2,然后遍历下标为2的元素,nums[1]=1,nums[3]=2,这样看也没问题,但是遍历到下标为3的元素时,nums[2]=1,nums[4]=3,这和前面所需要的nums[2]=2矛盾!如果nums[2]=2,那么nums[2]和nums[3]分的糖果一样多了,如果nums[2]=1,那么nums[2]和nums[1]分的糖果也一样多了,由此,若同时注重两边,会导致顾此失彼,产生矛盾!
因此,这道题目一定是要确定一边之后,再确定另一边,例如比较每一个孩子的左边,然后再比较右边。先确定右边评分大于左边的情况(也就是从前向后遍历)此时局部最优:只要右边评分比左边大,右边的孩子就多一个糖果,全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果,局部最优可以推出全局最优。
如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个,所以贪心:candyVec[i] = candyVec[i - 1] + 1。
再确定左孩子大于右孩子的情况(从后向前遍历),为什么不能从前向后遍历呢?因为 rating[5]与rating[4]的比较 要利用上 rating[5]与rating[6]的比较结果,所以 要从后向前遍历。如果从前向后遍历,rating[5]与rating[4]的比较 就不能用上 rating[5]与rating[6]的比较结果了 。如图:
所以确定左孩子大于右孩子的情况一定要从后向前遍历!如果 ratings[i] > ratings[i + 1],此时candyVec[i](第i个小孩的糖果数量)就有两个选择了,一个是candyVec[i + 1] + 1(从右边这个加1得到的糖果数量),一个是candyVec[i](之前比较右孩子大于左孩子得到的糖果数量)。那么又要贪心了,局部最优:取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优:相邻的孩子中,评分高的孩子获得更多的糖果。局部最优可以推出全局最优。所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多,也比右边candyVec[i + 1]的糖果多。
2.代码实现
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> sugar(ratings.size(),1);
for(int i=1;i<ratings.size();i++){
if(ratings[i]>ratings[i-1]){
sugar[i] = sugar[i-1]+1;
}
}
for(int i=ratings.size()-2;i>=0;i--){
if(ratings[i]>ratings[i+1]){
sugar[i] = max(sugar[i],sugar[i+1]+1);
}
}
int result = 0;
for(int i=0;i<sugar.size();i++){
result += sugar[i];
}
return result;
}
};