LeetCode刷题笔记【25】：贪心算法专题-3（K次取反后最大化的数组和、加油站、分发糖果）

前置知识

参考前文

参考文章：
LeetCode刷题笔记【23】：贪心算法专题-1（分发饼干、摆动序列、最大子序和）
LeetCode刷题笔记【24】：贪心算法专题-2（买卖股票的最佳时机II、跳跃游戏、跳跃游戏II）

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

题目描述

LeetCode链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/

分情况讨论

首先sort nums, 然后统计其中的负数的数量为n
① n=k, 将所有负数转为正数
② n>k, 从小到大地处理k个负数, 然后结束
③ n<k, 将所有负数转为正数后, 再sort数组, 对sort后的数组最小数处理(k-n)次

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end());int n=0;for(int num : nums){if(num<0)n++;elsebreak;}if(n>=k){for(int i=0; i<k; i++){nums[i] = -nums[i];}}else{for(int i=0; i<n; i++){nums[i] = -nums[i];}sort(nums.begin(), nums.end());int key = k-n;if(key%2 != 0)nums[0] = -nums[0];}int ans=0;for(int num : nums){ans += num;}return ans;}
};

贪心算法

换一种实现方法: 先按照绝对值进行从大到小排序, 然后遍历加和
在k没用完的时候遇到负数就加上其绝对值, k--
k用完了就加上其本身值, 遍历到最后如果k还有剩余, 且剩余k为奇数, 就加上最后一个数的负数

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), [](int a, int b){return abs(a)>abs(b);});int ans=0;for(int i=0; i<nums.size(); ++i){if(nums[i]<0 && k>0){nums[i] = -nums[i];k--;}}if(k%2==1)nums.back() = -nums.back();for(int num : nums)ans += num;return ans;}
};

134. 加油站

题目描述

LeetCode链接：https://leetcode.cn/problems/gas-station/description/

暴力解法

① 暴力解法, 把每个点都尝试跑一遍

class Solution {
public:bool check(int index, vector<int>& diff){int sum=diff[index], cur=index+1;if(cur>=diff.size())cur=0;while(cur != index){if(sum<0){return false;}else{sum += diff[cur];cur ++;if(cur>=diff.size())cur=0;}}if(sum<0)return false;return true;}int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n=gas.size();vector<int> diff(n);for(int i=0; i<n; ++i){diff[i] = gas[i] - cost[i];}for(int i=0; i<n; ++i){if(check(i, diff))return i;}return -1;}
};

贪心算法

很遗憾, 暴力解法超出时间限制了
② 贪心算法, 过程中维护curSum和totalSum;
当curSum<0时整个计数从i+1开始(curSum置为0)(将ans置为i+1)
totalSum记录所有的sum, 如果最后totalSum<0, 那么返回-1

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int ans=0;int curSum=0;int totalSum=0;for(int i=0; i<gas.size(); ++i){totalSum += gas[i]-cost[i];curSum += gas[i]-cost[i];if(curSum<0){ans = i+1;curSum = 0;}}if(totalSum<0)return -1;return ans;}
};

135. 分发糖果

题目描述

LeetCode链接：https://leetcode.cn/problems/candy/description/

暴力解法

暴力解法: 创建vector<int> candy(ratings.size(), 1), 记录给每个孩子分的糖, 初始每个孩子都有一颗糖
多次遍历, 发现一个孩子比相邻的孩子ratings高, 但是candy没有更多, 就candy++, 同时ans++
循环遍历, 直到没有发现以上情况

class Solution {
public:bool check(int i, vector<int>& ratings, vector<int>& candy){if(i==0){if(ratings[i]>ratings[i+1] && candy[i]<=candy[i+1])return true;elsereturn false;}else if(i==ratings.size()-1){if(ratings[i]>ratings[i-1] && candy[i]<=candy[i-1])return true;elsereturn false;}else{if((ratings[i]>ratings[i+1] && candy[i]<=candy[i+1]) || (ratings[i]>ratings[i-1] && candy[i]<=candy[i-1]))return true;elsereturn false;}return false;}int candy(vector<int>& ratings) {vector<int> candy(ratings.size(), 1);int ans=ratings.size();if(ans<=1)return ans;bool changed=true;while(changed==true){changed = false;for(int i=0; i<ratings.size(); ++i){if(check(i, ratings, candy)){candy[i] ++;changed = true;ans ++;}}}return ans;}
};

贪心算法

很遗憾, 通过样例, 但是超出时间范围
参考<代>, 使用贪心算法, 具体操作如下
进行两次遍历, 一次从前往后, 一次从后往前
从前往后遍历过程中: 如果发现ratings[i+1]>ratings[i], 则candy[i+1] = max(candy[i+1], candy[i]+1);
从后往前遍历过程中: 如果发现ratings[i-1]>ratings[i], 则candy[i-1] = max(candy[i-1], candy[i]+1);

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candy(ratings.size(), 1);for(int i=0; i<ratings.size()-1; ++i){if(ratings[i+1]>ratings[i])candy[i+1] = max(candy[i+1], candy[i]+1);}for(int i=ratings.size()-1; i>0; --i){if(ratings[i-1]>ratings[i])candy[i-1] = max(candy[i-1], candy[i]+1);}int ans=0;for(int c : candy)ans += c;return ans;}
};

总结

贪心, 讲真就是只有思想, 没有固定的套路.
现在做(被折磨)多了, 下意识的, 逐渐有一种"看看了解了解"的想法了.

如果笔试的时候真遇到类似的题目, 如果可以想到贪心, 那么最好;
如果一时半会儿没有想到很巧妙的方法, 最好先用暴力解法, 通过一部分测试用例, 分到手最好.

归根到底还是要代码实现能力过硬, 可不要感觉暴力解法是那么简单哦~
很多时候想的很清楚, 写出来就是很奇怪;

并且写的是一会儿, 往往在代码层面可以有优化很多的写法.
当然, 这样的功夫, 也只能在不断的练习过程中慢慢培养了.

本文参考：
K次取反后最大化的数组和
加油站
分发糖果