本文主要是介绍代码随想录算法训练营第三十三天|LeetCode1005 K次取反后最大化的数组和 、LeetCode134 加油站、LeetCode135 分发糖果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1005.K次取反后最大化的数组和
思路：先将数组排序，然后将数组从最小值开始向后取反，直至数组都为正。如果K小于数组中负数的个数，取反后直接求和。如果大于数组中负数的个数，将取反后全为正的数组再次排序，然后对最小的元素取反剩余次数，再对数组求和。
class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(),nums.end());int i =0;while(k){if(i<nums.size()&&nums[i]<0){nums[i] = -nums[i];i++;k--;}else{break;}}sort(nums.begin(),nums.end());int sum = 0;if(k%2==0){for(int i = 0;i<nums.size();i++){sum+= nums[i];}}else{nums[0] = -nums[0];for(int i = 0;i<nums.size();i++){sum+= nums[i];}}return sum;}
};134.加油站
思路：计算每个加油站处获取油量与向下一站去消耗油量的差，建立cursum和totalsum，从第一个加油站开始将油量差加入两个sum中，如果cursum为负，说明从前面i个节点开始，油都不够用，起点设置为i+1,cursum清零。继续循环，如果循环结束后，totalsum>=0，说明一定存在满足条件的加油站，return start，如果totalsum<0，说明没有满足条件的加油站，return -1。
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;}return start;}
};135.分发糖果
思路：先判断右边比左边好的孩子，右边孩子的糖果数目为左边数目+1，再判断左边比右边好的孩子，左边孩子的糖果数目为max(右边孩子数目+1,当前数目)。这样就都能满足题目要求。判断右边比左边好时，从前往后循环遍历孩子，判断左边比右边好时，从后往前循环遍历孩子。
class Solution {
public:int candy(vector<int>& ratings) {vector<int> cset(ratings.size(),1);//右边比左边大for(int i = 1;i<ratings.size();i++){if(ratings[i-1]<ratings[i]){cset[i] = cset[i-1]+1;}}for(int i=ratings.size()-2;i>=0;i--){if(ratings[i]>ratings[i+1]){cset[i] = max(cset[i],cset[i+1]+1);}}int sum=0;for(int i = 0;i<cset.size();i++){sum+=cset[i];}return sum;}
};这篇关于代码随想录算法训练营第三十三天|LeetCode1005 K次取反后最大化的数组和 、LeetCode134 加油站、LeetCode135 分发糖果的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
