• 今日学习的文章链接，或者视频链接

第八章 贪心算法 part03

• 自己看到题目的第一想法

• 看完代码随想录之后的想法

1005:

class Solution {
public:static bool cmp(int a, int b) {return abs(a) > abs(b);}int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(),nums.end(),cmp);for(auto i = 0;i<nums.size();i++){if(nums[i]<0&&k>0){nums[i]*=-1;k--;}}if(k%2==1){nums[nums.size()-1]*=-1;}int result =0;for(auto num:nums){result+=num;}return result;}
};

134

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int totalSum = 0;int start = 0;for(auto 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

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

• 自己实现过程中遇到哪些困难

• 今日收获，记录一下自己的学习时长