1005.K次取反后最大化的数组和
本题简单一些，估计大家不用想着贪心 ，用自己直觉也会有思路。
Tips：
- 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
- 第二步：从前向后遍历，遇到负数将其变为正数，同时K--
- 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
- 第四步：求和
我的题解：
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int sum = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] < 0 && k > 0){
nums[i] = -nums[i];
k--;
}
sum += nums[i];
}
if(k == 0 || k % 2 == 0){
return sum;
}
else{
sort(nums.begin(),nums.end());
sum -= nums[0] * 2;
return sum;
}
}
};134.加油站
本题有点难度，不太好想，推荐大家熟悉一下方法二
https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html
Tips：
首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。
如图： 
那么为什么一旦[i，j] 区间和为负数，起始位置就可以是j+1呢，j+1后面就不会出现更大的负数？
如果出现更大的负数，就是更新j，那么起始位置又变成新的j+1了。
而且j之前出现了多少负数，j后面就会出现多少正数，因为耗油总和是大于零的（前提我们已经确定了一定可以跑完全程）。
那么局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置。
局部最优可以推出全局最优，找不出反例，试试贪心！
我的题解：
暴力法：（会超出时间限制）
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
for(int i = 0; i<gas.size(); i++){
//这里 i 是起点
int tank = gas[i];
int j = i;
while(tank>=cost[j]){
tank -= cost[j];
if(j < gas.size() - 1){
j++;
}
else{
j = 0;
}
if(j == i){
return i;
}
tank += gas[j];
}
}
return -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.分发糖果
本题涉及到一个思想，就是想处理好一边再处理另一边，不要两边想着一起兼顾，后面还会有题目用到这个思路
https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html
Tips：
这在leetcode上是一道困难的题目，其难点就在于贪心的策略，如果在考虑局部的时候想两边兼顾，就会顾此失彼。
那么本题我采用了两次贪心的策略：
- 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
- 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。
我的题解：
class Solution {
public:
int candy(vector<int>& ratings) {
int count = ratings.size();
vector<int> candy = vector<int>(ratings.size(),1);
for(int i = 1; i < ratings.size(); i++){
if(ratings[i] > ratings[i-1] && candy[i] <= candy[i-1]){
count += candy[i-1] + 1 - candy[i];
candy[i] = candy[i-1] + 1;
}
}
for(int i = ratings.size() - 2; i >= 0; i--){
if(ratings[i] > ratings[i+1] && candy[i] <= candy[i+1]){
count += candy[i+1] + 1 - candy[i];
candy[i] = candy[i+1] + 1;
}
}
return count;
}
};