代码随想录算法训练营第33天| Leetcode1005.K次取反后最大化的数组和、134. 加油站、135. 分发糖果

本文主要是介绍代码随想录算法训练营第33天| Leetcode1005.K次取反后最大化的数组和、134. 加油站、135. 分发糖果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

Leetcode 1005.K次取反后最大化的数组和
Leetcode 134. 加油站
Leetcode 135. 分发糖果

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

题目链接：Leetcode 1005.K次取反后最大化的数组和
题目描述： 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。重复这个过程恰好 k 次。可以多次选择同一个下标i 。以这种方式修改数组后，返回数组可能的最大和。
思路： 由于要对数组元素取相反值，并且想要得到数组总和最大，很容易想到思路：先对数组绝对值较大的负数取相反值，如果所有负数都变成了正数但是k还有剩余，则不断操作绝对值最小的那个数字。
解题步骤：

将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
从前向后遍历，遇到负数将其变为正数，同时k--
如果k还大于0，那么反复转变数值最小的元素，将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) {k--;nums[i] *= -1;}}if (k % 2 == 1)nums[nums.size() - 1] *= -1;int result = 0;for (int i = 0; i < nums.size(); i++) {result += nums[i];}return result;}
};

时间复杂度 $O (n l o g n)$
空间复杂度 $O (1)$

Leetcode 134. 加油站

题目链接：Leetcode 134. 加油站
题目描述： 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。
思路： 本题的暴力思路是两层循环，遍历每个加油站作为起点，如果跑了一圈，中途没有断油，而且最后油量大于等于0,说明该起点合理，不过时间复杂度为 $O(n^2)$ ，会超时。
因此我们需要换一个方法。根据题意我们发现：如果总油量减去总消耗大于等于零那么一定可以跑完一圈。进而推理出：各个站点的加油站剩油量rest[i]相加一定是大于等于零的。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

代码如下：(从局部推全局)

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int cur = 0;   //从某点出发后的差值之和int total = 0; //两个数组的所有数字对应差值之和int start = 0; //记录结果for (int i = 0; i < gas.size(); i++) {cur += gas[i] - cost[i];total += gas[i] - cost[i];if (cur < 0) {start = i + 1; //记录起始位置cur = 0;       //重新计算}}return (total < 0) ? -1 : start;}
};

时间复杂度： $O (n)$
空间复杂度： $O (1)$

除了从局部贪心，还可以从全局来考虑，不过这种方法不太容易想到。

情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。（相当于转化为情况二）

代码如下：(从全局考虑)

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int cur = 0;int min = INT_MAX; //从起点出发，记录油量最小值for (int i = 0; i < gas.size(); i++) {cur += gas[i] - cost[i];if (cur < min) {min = cur;}}if (cur < 0)return -1; //情况一if (min >= 0)return 0; //情况二for (int i = gas.size() - 1; i >= 0; i--) {min += gas[i] - cost[i];if (min >= 0) { //相当于转化成了情况二return i;}}return -1;}
};

时间复杂度： $O (n)$
空间复杂度： $O (1)$

Leetcode 135. 分发糖果

题目链接：Leetcode 135. 分发糖果
题目描述： n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

思路： 本题可以遍历所有孩子，分别让其与左、右孩子的评分进行比较，如果评分高，则糖果数量 $+ 1$ 。我们发现两种比较所需要的遍历方式不同：

比较右边孩子比左边孩子大的情况，需要从前向后遍历
比较左边孩子比右边孩子大的情况，需要从后向前遍历

为什么呢？由于比较之后，要在确定好的糖果数量上 $+ 1$ ，举个例子：
注：该图片来源于《代码随想录》
注：上述图片来源于《代码随想录》
rating[5]与rating[4]的比较需要利用上 rating[5]与rating[6]的比较结果，因此只能从后向前遍历。
代码如下：

class Solution {
public:int candy(vector<int>& ratings) {vector<int> vec(ratings.size(), 1);//先比较右边孩子比左边孩子大的情况for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1])vec[i] = vec[i - 1] + 1;}//再比较左边孩子比右边孩子大的情况for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1])vec[i] = max(vec[i + 1] + 1, vec[i]); //和上面计算的vec[i]取最大值}//统计结果int result = 0;for (int i = 0; i < vec.size(); i++) {result += vec[i];}return result;}
};

时间复杂度: $O (n)$
空间复杂度: $O (n)$