本文主要是介绍代码随想录训练营Day25:贪心算法：加油站、分发糖果和K次取反的最大数组和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.1005K次取反后最大化的数组和
贪心策略：先按照绝对值的大小进行排序，绝对值大的排在前面，然后按照顺序，如果存在负值就翻转直到用完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--;}}int flags = 1;if(k%2==1){flags = -1;}nums[nums.size()-1] *= flags;int result = 0;for(auto num:nums) result += num;return result; }
};2.134加油站
贪心策略：直接从i开始双重for循环遍历，当消耗的油量大于获得的油量就继续遍历，如果找到了一个循环，返回即可。
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();int i = 0;while (i < n) {int sumOfGas = 0, sumOfCost = 0;int cnt = 0;while (cnt < n) {int j = (i + cnt) % n;sumOfGas += gas[j];sumOfCost += cost[j];if (sumOfCost > sumOfGas) {break;}cnt++;}if (cnt == n) {return i;} else {i = i + cnt + 1;}}return -1;}
};3.135分发糖果
贪心策略：这里用到了两次贪心，分别是从左往右和从右往左两次。
对第一次贪心：从左往右进行遍历，如果大于前一个则在前面那个数字+1
对第二次贪心：这次的贪心需要在前面的基础上进行操作。还是按照第一次贪心的类似的思路，从右往左，比较当前值和右边值的大小，如果大则+1，此时重点在：需要比较candyVec[i] = max(candyVec[i],candyVec[i+1]+1);因为我们需要同时满足两边的条件，所以需要取最大值。
最后累加求得结果即可。
class Solution {
public://两次贪心：第一次是从左往右，第二次是从右往左，这样能够保证两边都进行了比较int candy(vector<int>& ratings) {int n = ratings.size();vector<int> candyVec(n,1);//从左往右遍历，确定大于的地方for(int i =1;i<n;i++){if(ratings[i]>ratings[i-1]){candyVec[i] = candyVec[i-1]+1;}}//从右往左遍历，确定大于的地方for(int i = n-2;i>=0;i--){if(ratings[i]>ratings[i+1]){//这个地方是核心所在，两种选择，要同时满足的贪心，所以要取最大值candyVec[i] = max(candyVec[i],candyVec[i+1]+1);}}int result = 0;for(int i =0;i<n;i++){result += candyVec[i];}return result;}
};这篇关于代码随想录训练营Day25:贪心算法：加油站、分发糖果和K次取反的最大数组和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
