day35贪心算法part03| 1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果

本文主要是介绍day35贪心算法part03| 1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

本题简单一些，估计大家不用想着贪心，用自己直觉也会有思路。
题目讲解 | 题目链接

自己的想法，也通过了

class Solution {
public:int sumMax(vector<int>& nums) {int sum = 0;for (int i = 0; i < nums.size(); i++) {cout << nums[i] << endl;sum += nums[i];}return sum;}int largestSumAfterKNegations(vector<int>& nums, int k) {while (k--){// 每次优先把最小的数取反int min = INT32_MAX, min_idx = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] < min) {min = nums[i];min_idx = i;}}nums[min_idx] *= -1; }return sumMax(nums);}
};

134. 加油站

本题有点难度，不太好想，推荐大家熟悉一下方法二
题目讲解 | 题目链接
这题自己做不出来

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;}
};

135. 分发糖果

本题涉及到一个思想，就是想处理好一边再处理另一边，不要两边想着一起兼顾，后面还会有题目用到这个思路
https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html

class Solution {
public:int candy(vector<int>& ratings) {if (ratings.size() == 1)return 1;vector<int> nums(ratings.size(), 1);// 从前向后，右是否比左大for (int i = 0; i <= ratings.size() - 2; i++) {if (ratings[i + 1] > ratings[i]) {nums[i + 1] = nums[i] + 1;}}// 从后向前，左是否比右大for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i + 1] < ratings[i]) {nums[i] = max(nums[i + 1] + 1, nums[i]);}}int result = 0;for (int i = 0; i < nums.size(); i++) {cout << nums[i] << " ";result += nums[i];}return result;}
};