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

分成大于0小于0

class Solution {
public:
    // 只用改负数
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        vector<int> a1; // 大于0
        vector<int> a2; // 小于0
        for (int i = 0; i < nums.size(); i ++)
        {
            if (nums[i] > 0) a1.push_back(nums[i]);
            else a2.push_back(nums[i]);
        }

        sort(a1.begin(), a1.end());
        sort(a2.begin(), a2.end());

        for (int i = 0; i < min(k, (int)a2.size()); i ++)
        {
            a2[i] = -a2[i];
        }

        k -= a2.size();
        bool flag = false;
        // cout << k;
        if (k > 0)
        {
            k %= 2; 
            if (k == 1)
            {
                flag = true;
            }
        }

        int res = 0;
        int minn = 200;
        for (int num : a1) 
        {
            res += num;
            minn = min(minn, num);
        }
        for (int num : a2) 
        {
            res += num;
            minn = min(minn, num);
        }
        if (flag) res -= minn * 2;

        return res;
    }
};

134. 加油站

不合适了就重新计数

class Solution {
public:
    // 如果油量总和大于消耗一定可以
    // 某一点<0表示 它前面都不行, 重新计数
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int totalgas = 0, totalcost = 0, now = 0, pre = 0;
        for (int i = 0; i < n; i ++)
        {
            totalgas += gas[i];
            totalcost += cost[i];
        }
        if (totalcost > totalgas) return -1;

        for (int i = 0; i < n; i ++)
        {
            now += gas[i] - cost[i];
            // 当前点小于0
            if (now < 0)
            {
                now = 0;
                pre = i + 1;
            }
        }

        return pre;
    }
};

135. 分发糖果

前后遍历一遍，没太看懂

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> cnt(n);
        cnt[0] = 1;
        for (int i = 1; i < n; i ++)
        {
            if (ratings[i] > ratings[i-1]) cnt[i] = cnt[i-1] + 1;
            else cnt[i] = 1;
        }

        for (int i = n - 2; i >= 0; i --)
        {
            if (ratings[i] > ratings[i+1]) cnt[i] = max(cnt[i], cnt[i+1] + 1);
        }

        int res = 0;
        for (int i = 0; i < n; i++) res += cnt[i];

        return res;
    }
};