本文主要是介绍20240325-算法复习打卡day34||● 1005.K次取反后最大化的数组和 ● 134. 加油站● 135. 分发糖果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1005.K次取反后最大化的数组和
首先根据nums[i]的绝对值大小，从大到小进行排序（贪心的点在于先把绝对值大的负值反转为正数），到最后k如果>0，偶数情况不作下一步处理（原地反转偶数次），奇数情况把最后数反转（因为k>0，所以整个数组都是正数，选取最后一个最小数进行反转）
class Solution {
static bool cmp(int a, int b) {return abs(a) > abs(b);
}
public: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 result = 0;for (int a : nums) result += a;return result;}
}; 134. 加油站
当总的gas和 - cost和 < 0 说明无论如何跑不完一圈；
当从某一个点a出发，中途汽油在b处 < 0说明这个点a到b之间的出发点都不可行
假设可以走完一圈的前提下，出发点一定是在后面的点里选；
for循环结束，判断totalsum < 0 那么无法走一圈； >0 那么start即为所求
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. 分发糖果
关键点在于本题需要考虑左右rating（同时考虑很麻烦）；
采用了先从左到右，然后在右到左的判断方法；非常巧妙
class Solution {
public:int candy(vector<int>& ratings) {vector<int> candyVec(ratings.size(), 1);for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;}for (int i = ratings.size() - 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 < ratings.size(); i++) result += candyVec[i];return result;}
};这篇关于20240325-算法复习打卡day34||● 1005.K次取反后最大化的数组和 ● 134. 加油站● 135. 分发糖果的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
