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

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

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

题目

解法

1. 考虑绝对值

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), [](int a, int b){return abs(a) > abs(b);} ); // 按绝对值大小排序int sum = 0;for (int i = 0; k > 0; i++) {if(nums[i] < 0 && i < nums.size()-1 ) {nums[i] = -nums[i];k--;}if(i == nums.size()-1){nums[i] = k % 2 == 0 ? nums[i] : -nums[i];k=-1;}}for (int num : nums) {sum += num;}return sum;}
};

134. 加油站

题目

解法

1. 暴力解法：超时

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {// 从各个加油站出发int idx ; // 加油站索引int curgas; // 目前的油量for (int i = 0; i < gas.size(); i++) {if(gas[i] < cost[i] ) continue; // 过滤 idx = i;curgas = 0;for (int j = idx; j < gas.size(); j++) {curgas += gas[j];curgas -= cost[j];if (curgas < 0) {break;}  if (idx == 0 && j == gas.size() -1 && curgas >= 0) return idx;if (j == gas.size() -1) {for (int k = 0; k < idx; k++) {curgas += gas[k];curgas -= cost[k];if (curgas < 0) {break;}if (k == idx -1 && curgas >= 0) return idx;}}}   }return -1;// 看是否可以}
};

使用while来模拟环形：

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {for (int i = 0; i < cost.size(); i++) {int rest = gas[i] - cost[i]; // 记录剩余油量int index = (i + 1) % cost.size();while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈（如果有rest==0，那么答案就不唯一了）rest += gas[index] - cost[index];index = (index + 1) % cost.size();}// 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置if (rest >= 0 && index == i) return i;}return -1;}
};

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;  // 情况1 gas的总和小于cost总和if (min >= 0) return 0;     // 情况2 0就是起点// 情况3 min前面已经遍历了， 这里遍历min后面的for (int i = gas.size() - 1; i >= 0; i--) {int rest = gas[i] - cost[i];min += rest;if (min >= 0) {return i;}}return -1;}
};

3.贪心算法：前面的出现剩余出现负数，说明起点一定不在这里的范围内

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. 贪心

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candys(ratings.size(),1);for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i-1]) candys[i] = candys[i-1]+1; //比左边的多一个}for (int i = ratings.size()-2; i >= 0; i--) { //之所以从后往前，是为了保证 从前往后的第一次遍历有效if (ratings[i] > ratings[i+1]) candys[i] = max(candys[i], candys[i+1]+1);}int result = 0;for (int num : candys) result += num;return result;}
};

感悟

贪心有点难想

这篇关于代码随想录算法训练营第三十四天 |1005. K 次取反后最大化的数组和 、134. 加油站、135. 分发糖果的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---