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

题目链接

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); // 按绝对值大小排序
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) { // 将所有的负数全部变成正数
            if (nums[i] < 0 & k > 0) {
                nums[i] = 0 - nums[i];
                k--;
            }
        }
        if (k % 2 == 1) nums[nums.size() - 1] *= -1; // 反复取最小的数让它修改
        for (auto a : nums) sum += a; // 求和
        return sum;
    }
};

一定要按照绝对值来排序，形成一个伪降序的序列，负数全部取完以后，再考虑取末尾取反，当我剩下的K为偶数的时候，那么不需要再取反了，因为我们对同一个最小的数取两次了，只有剩下k为奇数的时候，才考虑取一次。因为我们返回的是数组最大可能元素和。

134. 加油站

题目链接

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int cur_sum = 0;
        int total_sum = 0;
        int start = 0;
        
        for (int i = 0; i < gas.size(); i++) {
            cur_sum += (gas[i] - cost[i]);
            total_sum += (gas[i] - cost[i]);
            if (cur_sum < 0) {
                start = i+1;
                cur_sum = 0;
            }
        }
        if (total_sum < 0) return -1;
        return start;
    }
};

本题十分巧妙，具体思路可以看题解或者视频讲解，贪心用到极致。

135. 分发糖果

题目链接

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 result = 0;
        for (auto a : candy) result += a;
        return result;
    }
};

注意比较的是排队的左右，要比较同一个位置的左右实现。这里实现很巧妙，如果下次回顾不熟悉可以看网站。思路要先明确了