代码随想录算法训练营第36期DAY36

贪心好难，希望能坚持到柳暗花明那天。

DAY36

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

自己的方法，注意越界条件放在最前面就好：

1. class Solution {
2. public:
3.     int largestSumAfterKNegations(vector<int>& nums, int k) {
4.         //自己的方法：
5.         sort(nums.begin(),nums.end());
6.         for(int i=0;i<nums.size()&&nums[i]<0&&k>0;i++){
7.             nums[i]*=-1;
8.             k--;
9.         }
10.         sort(nums.begin(),nums.end());
11.         if(k%2!=0) nums[0]*=-1;
12.         int res=0;
13.         for(int n:nums) res+=n;
14.         return res;
15.         //报错越界，为什么？注意限制条件的先后顺序，把nums.size()放在最前面，因为越界是不能的，所以首先判断。
16.     }
17. };

代码随想录的方法，正好复习一下重载比较符的写法。

记得把自己的重载比较符写进sort里面去。

1. class Solution {
2. public:
3.     static bool mycmp(int a,int b){
4.         return abs(a)>abs(b);
5.     }
6.     int largestSumAfterKNegations(vector<int>& nums, int k) {
7.         sort(nums.begin(),nums.end(),mycmp);
8.         for(int i=0;i<nums.size();i++){
9.             if(nums[i]<0&&k>0) {
10.                 nums[i]*=-1;
11.                 k--;
12.             }
13.         }
14.         if(k%2!=0) nums[nums.size()-1]*=-1;
15.         int res=0;
16.         for(int n:nums)res+=n;
17.         return res;
18.     }
19. };

134加油站

for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while

1. 试试暴力法，既考验思维，又考验语法能力：

还是做不到，加油练习：

修改之后：

代码逻辑：先算油量，根据油量再移动index；（看当下能不能走得动，能不能出发）

1. class Solution {
2. public:
3.     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
4.         for(int i=0;i<gas.size();i++){
5.             //先算油量，根据油量再移动index；（看当下能不能走得动，能不能出发）
6.             int store=0,index=i;
7.             store+=gas[i]-cost[i];
8.             if(store<0) continue;
9.             index=(index+1)%gas.size();
10.             while(store>=0&&index!=i){
11.                 store+=gas[index]-cost[index];
12.                 index=(index+1)%gas.size();
13.             }
14.             if(store>=0&&index==i) return i;
15.         }
16.         return -1;
17.     }
18. };

没问题了，只是会超时。有提升就好。

1. 后退法_全局贪心

知道思想，代码还是写不出来。思想也没对。

1. 全局油量不够
2. 累加过程没有出现负值，可行
3. 出现负值，起点后退。

1. class Solution {
2. public:
3.     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
4.         int mi=INT_MAX;
5.         int cursum=0;
6.         for(int i=0;i<gas.size();i++){
7.             cursum+=gas[i]-cost[i];
8.             if(cursum<mi) mi=cursum;
9.         }
10.         if(cursum<0) return -1;
11.         if(mi<0){
12.             for(int i=gas.size()-1;i>=0;i--){
13.                 mi+=gas[i]-cost[i];
14.                 if(mi>=0) return i;
15.             }
16.         }
17.         else return 0;
18.         return -1;
19.     }
20. };

1. 前进法_局部贪心

[0,i]一旦负数了，就从[i+1开始选起点。（家产败光了的意思——用光了留下当时的剩余，表明自己的都不够用，所以要换到下一个起点）。之后呢？不会了：for遍历的就是起点，找起点就好了。

前进法待二刷：

1. class Solution {
2. public:
3.     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
4.         int cursum=0,totalsum=0,start=0;//标记起点，total判定一圈油量
5.         for(int i=0;i<gas.size();i++){
6.             totalsum+=gas[i]-cost[i];
7.             cursum+=gas[i]-cost[i];
8.             if(cursum<0){
9.                 start=i+1;
10.                 cursum=0;
11.             }
12.         }
13.         if(totalsum<0) return -1;
14.         return start;
15.     }
16. };

135分发糖果，困难

待二刷：

1. class Solution {
2. public:
3.     int candy(vector<int>& ratings) {
4.         vector<int> candy(ratings.size(),1);
5.         if(ratings.size()==1) return 1;
6.         for(int i=1;i<ratings.size();i++){
7.             if(ratings[i]>ratings[i-1]){
8.             candy[i]=candy[i-1]+1;
9.             }
10.         }
11.         for(int i=candy.size()-2;i>=0;i--){
12.             if(ratings[i]>ratings[i+1])
13.             candy[i]=max(candy[i+1]+1,candy[i]);
14.         }
15.         int res=0;
16.         for(int r:candy) res+=r;
17.         return res;
19.     }
20. };