算法训练营第34天|● 1005.K次取反后最大化的数组和 ● 134. 加油站● 135. 分发糖果

文档讲解：代码随想录 (programmercarl.com)

视频讲解：代码随想录的个人空间-代码随想录个人主页-哔哩哔哩视频 (bilibili.com)

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

题目链接：1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

代码如下：

class Solution {
static bool cmp(int a, int b) {
    return abs(a) > abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(), A.end(), cmp);       // 第一步
        for (int i = 0; i < A.size(); i++) { // 第二步
            if (A[i] < 0 && K > 0) {
                A[i] *= -1;
                K--;
            }
        }
        if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步
        int result = 0;
        for (int a : A) result += a;        // 第四步
        return result;
    }
};

LeetCode?134. 加油站

题目链接：134. 加油站 - 力扣（LeetCode）

解题思路：保证总消耗后的剩余油量大于等于0的前提下，寻找令cursum>0恒成立的站点。

解题代码如下：?

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

LeetCode?135. 分发糖果

题目链接：135. 分发糖果 - 力扣（LeetCode）

解题代码如下：

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