本文主要是介绍代码随想录算法训练营第三十三天|LeetCode1005 k次取反后最大化的数组和、LeetCode134 加油站，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题1：
指路：1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
思路与代码：
题意清晰，需要注意的是需要把k次机会用完。数组中的数分为三种情况：正数，负数，0。要求数组和最大需要我们分两步：第一，在k的范围内遇到负数取反消耗k的总量，第二，在剩余的k的范围内，对非负数中最小的数进行取反。所以在此，我们不能直接排序，需要按照数组中数的绝对值进行排序。最后，负数取反后k的值如果为奇数，则对非负数中最小数取反，否则不变。代码如下：
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);int ans = 0;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;for (auto i : nums)ans += i;return ans;}
};题2：
指路：134. 加油站 - 力扣（LeetCode）
思路与代码：
如果gas和小于cost和一定无法环绕。如果一天内剩下的油量无负数则可环形抵达。如果剩余油量时负数，则需更换出发节点。局部最优解为：不断累加当前油量，在当前油量小于0时，选择下一个站点作为起点。
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int min = INT_MAX; // 从起点出发，油箱里的油量最小值for (int i = 0; i < gas.size(); i++) {int rest = gas[i] - cost[i];curSum += rest;if (curSum < min) {min = curSum;}}if (curSum < 0) return -1; if (min >= 0) return 0; for (int i = gas.size() - 1; i >= 0; i--) {int rest = gas[i] - cost[i];min += rest;if (min >= 0) {return i;}}return -1;}
};
这篇关于代码随想录算法训练营第三十三天|LeetCode1005 k次取反后最大化的数组和、LeetCode134 加油站的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
