day35贪心算法part03| 1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果

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

本题简单一些，估计大家不用想着贪心 ，用自己直觉也会有思路。
题目讲解 | 题目链接

自己的想法，也通过了

class Solution {
public:
    int sumMax(vector<int>& nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            cout << nums[i] << endl;
            sum += nums[i];
        }
        return sum;
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {

        while (k--)
        {
            // 每次优先把最小的数取反
            int min = INT32_MAX, min_idx = 0;
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] < min) {
                    min = nums[i];
                    min_idx = i;
                }
            }
            nums[min_idx] *= -1; 
        }
        return sumMax(nums);
    }
};

134. 加油站

本题有点难度，不太好想，推荐大家熟悉一下方法二
题目讲解 | 题目链接
这题自己做不出来

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for (int i = 0; i < cost.size(); i++) {
            int rest = gas[i] - cost[i]; // 记录剩余油量
            int index = (i + 1) % cost.size();
            while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈（如果有rest==0，那么答案就不唯一了）
                rest += gas[index] - cost[index];
                index = (index + 1) % cost.size();
            }
            // 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置
            if (rest >= 0 && index == i) return i;
        }
        return -1;
    }
};

135. 分发糖果

本题涉及到一个思想，就是想处理好一边再处理另一边，不要两边想着一起兼顾，后面还会有题目用到这个思路
https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html

class Solution {
public:
    int candy(vector<int>& ratings) {
        if (ratings.size() == 1)
            return 1;
        vector<int> nums(ratings.size(), 1);
        // 从前向后，右是否比左大
        for (int i = 0; i <= ratings.size() - 2; i++) {
            if (ratings[i + 1] > ratings[i]) {
                nums[i + 1] = nums[i] + 1;
            }
        }

        // 从后向前，左是否比右大
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i + 1] < ratings[i]) {
                nums[i] = max(nums[i + 1] + 1, nums[i]);
            }
        }
        int result = 0;
        for (int i = 0; i < nums.size(); i++) {
            cout << nums[i] << " ";
            result += nums[i];
        }
        return result;
    }
};