DAY34 贪心算法Ⅲ

134. 加油站 - 力扣（LeetCode）

这种环路问题要记一下。

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

135. 分发糖果 - 力扣（LeetCode）

做的第一道hard，要分成左右两部分分别贪心。

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

860. 柠檬水找零 - 力扣（LeetCode）