力扣-K次取反后最大化的数组和 & 加油站

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

class Solution {
public:
    static bool cmp(int a, int b)
    {
        return abs(a) > abs(b);
    }
    //使用两次贪心 局部最优推出全局最优
    //第一次：将绝对值最大的负数取反
    //第二次：如果k有剩余（要么没负数了，要么数组遍历完了），那么就反复取反最小的数字
    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) 
            {
                nums[i] *= -1;
                k--;//使用一次k
            }
            //k用完了就不继续遍历了嗷
            if(k == 0) break;
        }
        //如果k没用完，而且还是奇数
        if( k % 2 == 1) nums[nums.size() - 1] *= -1;
        //求和
        int sum = 0;
        for(auto &each : nums)
        {
            sum += each;
        }
        return sum;

    }
};

    最开始我自己写的时候直接按大小排序，结果呢，后面还要分情况考虑，但如果是按绝对值大小排序的话，就没有那么多弯路去走了。

    注意，sort（）的cmp函数需要时static静态的，不然报错。

134. 加油站

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int totalGas = 0;//记录跑完一圈后剩余油量
        int curGas = 0;//记录当前油量
        int start = 0;//记录出发车站
        int len = gas.size();
        //使用贪心算法：局部最优推出全局最优，选出出发点
        for(int i = 0; i < len; i++)
        {
            int rest = gas[i] - cost[i];
            totalGas += rest;//时刻更新剩余油量
            curGas += rest;
            if(curGas < 0)//如果当前油量小于0，那么从start到i这个位置都不能作为出发点
            {
                start = i + 1;
                curGas = 0;
            }
        }
        //如果总的剩余油量小于0 说明走不完一圈
        if(totalGas < 0) return -1;
        return start;
    }
};

    这道题很遗憾啊，我的想法和代码随想录有相似的地方，但是start这个没有处理好，一旦当前油量小于0那么从下标0到这个下标i位置都不能做初始点。这一点是举不出反例的，就可以直接贪心了

    没想到，贪心还挺难的。