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;
}
};
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;
}
};
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;
}
};
贪心主要在于积累思路,加油!