平台网站建设方案,网站建设电脑维修数据恢复,企业建网站有这个必要吗,鄂州网站制作哪家好文章目录 前置知识1005.K次取反后最大化的数组和题目描述分情况讨论贪心算法 134. 加油站题目描述暴力解法贪心算法 135. 分发糖果题目描述暴力解法贪心算法 总结 前置知识
参考前文 参考文章#xff1a; LeetCode刷题笔记【23】#xff1a;贪心算法专题-1#xff08;分发饼… 文章目录 前置知识1005.K次取反后最大化的数组和题目描述分情况讨论贪心算法 134. 加油站题目描述暴力解法贪心算法 135. 分发糖果题目描述暴力解法贪心算法 总结 前置知识
参考前文 参考文章 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 ① nk, 将所有负数转为正数 ② nk, 从小到大地处理k个负数, 然后结束 ③ nk, 将所有负数转为正数后, 再sort数组, 对sort后的数组最小数处理(k-n)次
class Solution {
public:int largestSumAfterKNegations(vectorint nums, int k) {sort(nums.begin(), nums.end());int n0;for(int num : nums){if(num0)n;elsebreak;}if(nk){for(int i0; ik; i){nums[i] -nums[i];}}else{for(int i0; in; i){nums[i] -nums[i];}sort(nums.begin(), nums.end());int key k-n;if(key%2 ! 0)nums[0] -nums[0];}int ans0;for(int num : nums){ans num;}return ans;}
};贪心算法
换一种实现方法: 先按照绝对值进行从大到小排序, 然后遍历加和 在k没用完的时候遇到负数就加上其绝对值, k-- k用完了就加上其本身值, 遍历到最后如果k还有剩余, 且剩余k为奇数, 就加上最后一个数的负数
class Solution {
public:int largestSumAfterKNegations(vectorint nums, int k) {sort(nums.begin(), nums.end(), [](int a, int b){return abs(a)abs(b);});int ans0;for(int i0; inums.size(); i){if(nums[i]0 k0){nums[i] -nums[i];k--;}}if(k%21)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, vectorint diff){int sumdiff[index], curindex1;if(curdiff.size())cur0;while(cur ! index){if(sum0){return false;}else{sum diff[cur];cur ;if(curdiff.size())cur0;}}if(sum0)return false;return true;}int canCompleteCircuit(vectorint gas, vectorint cost) {int ngas.size();vectorint diff(n);for(int i0; in; i){diff[i] gas[i] - cost[i];}for(int i0; in; i){if(check(i, diff))return i;}return -1;}
};贪心算法
很遗憾, 暴力解法超出时间限制了 ② 贪心算法, 过程中维护curSum和totalSum; 当curSum0时整个计数从i1开始(curSum置为0)(将ans置为i1) totalSum记录所有的sum, 如果最后totalSum0, 那么返回-1
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int ans0;int curSum0;int totalSum0;for(int i0; igas.size(); i){totalSum gas[i]-cost[i];curSum gas[i]-cost[i];if(curSum0){ans i1;curSum 0;}}if(totalSum0)return -1;return ans;}
};135. 分发糖果
题目描述 LeetCode链接https://leetcode.cn/problems/candy/description/ 暴力解法
暴力解法: 创建vectorint candy(ratings.size(), 1), 记录给每个孩子分的糖, 初始每个孩子都有一颗糖 多次遍历, 发现一个孩子比相邻的孩子ratings高, 但是candy没有更多, 就candy, 同时ans 循环遍历, 直到没有发现以上情况
class Solution {
public:bool check(int i, vectorint ratings, vectorint candy){if(i0){if(ratings[i]ratings[i1] candy[i]candy[i1])return true;elsereturn false;}else if(iratings.size()-1){if(ratings[i]ratings[i-1] candy[i]candy[i-1])return true;elsereturn false;}else{if((ratings[i]ratings[i1] candy[i]candy[i1]) || (ratings[i]ratings[i-1] candy[i]candy[i-1]))return true;elsereturn false;}return false;}int candy(vectorint ratings) {vectorint candy(ratings.size(), 1);int ansratings.size();if(ans1)return ans;bool changedtrue;while(changedtrue){changed false;for(int i0; iratings.size(); i){if(check(i, ratings, candy)){candy[i] ;changed true;ans ;}}}return ans;}
};
贪心算法
很遗憾, 通过样例, 但是超出时间范围 参考代, 使用贪心算法, 具体操作如下 进行两次遍历, 一次从前往后, 一次从后往前 从前往后遍历过程中: 如果发现ratings[i1]ratings[i], 则candy[i1] max(candy[i1], candy[i]1); 从后往前遍历过程中: 如果发现ratings[i-1]ratings[i], 则candy[i-1] max(candy[i-1], candy[i]1);
class Solution {
public:int candy(vectorint ratings) {vectorint candy(ratings.size(), 1);for(int i0; iratings.size()-1; i){if(ratings[i1]ratings[i])candy[i1] max(candy[i1], candy[i]1);}for(int iratings.size()-1; i0; --i){if(ratings[i-1]ratings[i])candy[i-1] max(candy[i-1], candy[i]1);}int ans0;for(int c : candy)ans c;return ans;}
};总结
贪心, 讲真就是只有思想, 没有固定的套路. 现在做(被折磨)多了, 下意识的, 逐渐有一种看看了解了解的想法了.
如果笔试的时候真遇到类似的题目, 如果可以想到贪心, 那么最好; 如果一时半会儿没有想到很巧妙的方法, 最好先用暴力解法, 通过一部分测试用例, 分到手最好.
归根到底还是要代码实现能力过硬, 可不要感觉暴力解法是那么简单哦~ 很多时候想的很清楚, 写出来就是很奇怪;
并且写的是一会儿, 往往在代码层面可以有优化很多的写法. 当然, 这样的功夫, 也只能在不断的练习过程中慢慢培养了. 本文参考 K次取反后最大化的数组和 加油站 分发糖果
