1005 K 次取反后最大化的数组和
思路：这个题目的思路是先将数组按照元素绝对值从大到小排序，然后从头开始遍历数组，将负数变成正数，同时记录已经变成正数的个数 count，当 count 达到 k 的时候就可以停止遍历了。如果 k 还没有用完，且当前的数是非负数，那么根据贪心策略，将剩余的变成负数，此时 k 用完了。
如果 k 仍然有剩余，那么说明把所有的负数都变成正数仍然不够，此时应该将最小的一个数变成负数。可以通过判断 k % 2 是否等于 1 来判断是否需要将最小的数变成负数。
最后遍历数组求和即可。
1.贪心
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) nums[nums.size() - 1] *= -1;
int result = 0;
for(int num : nums) result += num;
return result;
}
};
134 加油站
思路：算法的思路是模拟行驶整个环路，利用 curSum 和 totalSum 变量分别记录当前行驶过的路程和总路程的花费与收益之差。如果当前的 curSum 变量变成负数，则表示从起点到当前点的路径不可行，起点应该移动到下一个点。如果整个行驶过程中，totalSum 仍然是负数，则表示整个路线是不可行的。如果全部通过，则返回起点的位置。
1.贪心
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 分发糖果
思路：这个问题的解决方法是，先从左向右遍历一遍 ratings，如果当前小朋友的分数比前一个小朋友高，那么就给当前小朋友的糖果数加 1。然后再从右向左遍历一遍 ratings，如果当前小朋友的分数比后一个小朋友高，那么就取当前小朋友的糖果数和后一个小朋友的糖果数加 1 中的最大值作为当前小朋友的糖果数。最后，把每个小朋友的糖果数累加起来即可。
1.贪心
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 c : candyVec) result += c;
return result;
}
};
