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;}
};