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

• 用两次贪心，第一次先把负数都转过来，第二次如果k还有剩的为奇数再把最小的正数转过来。
• 注意负数转过来后可能会产生更小的正数，所以一开始排序要不然按绝对值排序，要不然转过来之后再排序一次。
• 注意一点，选当前点前面的起始点相当于多了油量，二刷借此想法看看第一种全局的方法：1.走一圈剩余油和<0不可能完成2.从0开始走一圈大于0输出，小于0则往前倒退看谁能补齐差的油。

//C++ 两次从小到大排序
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
        }
        sort(nums.begin(), nums.end());
        if (k % 2 == 1) nums[0] *= -1;
        int result = 0;
        for (int a : nums) {
            result += a;
        }
        return result;
    }

};
// C++ 按绝对值排序
class Solution {
public:
    static bool cmp(int a, int b) {
        return abs(a) > abs(b);
    }
    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 == 1) nums[nums.size() - 1] *= -1;
        int result = 0;
        for (int a : nums) {
            result += a;
        }
        return result;
    }

};

//C#绝对值排序，Sort的不同用法
public class Solution {
    public static int CustomComparison(int x, int y) {
    // 自定义的排序逻辑
        return Math.Abs(y).CompareTo(Math.Abs(x)) ;
    }
    public int LargestSumAfterKNegations(int[] nums, int k) {
        Array.Sort(nums, CustomComparison);
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
        }
        if (k % 2 == 1) {
            nums[nums.Length - 1] *= -1;
        }
        int res = 0;
        foreach(int item in nums) res += item;
        return res;
    }
}

134. 加油站

暴力，注意for用于模拟从头到尾的遍历，而while适用于模拟环形遍历，比如这题for遍历每个起点的情况，while用于模拟车的环形移动，但可惜的是时间复杂度是O（n^2）会超时。

//C++ 暴力
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for (int i = 0; i < cost.size(); i++) {
            int res = gas[i] - cost[i];
            int index = (i + 1) % cost.size();
            while (res > 0 && index != i) {
                res += gas[i] - cost[i];
                index = (i + 1) % cost.size();   
            }
            if (res >= 0 && index == i) return i;
        }
        return -1;
    }
};

贪心，如果总油量减去总消耗大于等于零那么一定可以跑完一圈，剩余油量和>=0。局部最优是累加剩余油量和，一旦小于0说明不能在之前的区间选择起点，因为任意一个起点到这都会没油。这时在i+1选起点就可以，找一圈因为有唯一解，则起点确定，此时判断如果油量和 < 0 ,则有解。具体实现curSum记录每个可选择起点区间的和，totalSum记录全局的和用于判断整体能否跑完一圈。

局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

//C++ 贪心
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;
        int res = 0;
        for (int i = 0; i < cost.size(); i++) {
            totalSum += gas[i] - cost[i];
            curSum += gas[i] - cost[i];
            if (curSum < 0) {
                res = i + 1;
                curSum = 0; 
            }
        }
        if (totalSum >= 0) return res;
        return -1;
    }
};

135. 分发糖果

两次贪心的策略： 一次是从左到右遍历，只比较右边孩子评分比左边大的情况，大就多一个。 一次是从右到左遍历，只比较左边孩子评分比右边大的情况，这样才能用到之前的比较结果，大就多一个，并考虑与从左到右时的最大值，同时满足两种情况。

//C++
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candy(ratings.size(), 1);
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) {
                candy[i] = candy[i - 1]+ 1;
            }
        }
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candy[i] = max(candy[i], candy[i + 1] + 1);
            }
        }
        int res = 0;
        for (int i = 0; i < candy.size(); i++) res += candy[i];
        return res;
    }
};