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）