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

链接：代码随想录

 

自己做过一遍，又重新做了一遍

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {//把负的换成正的，尽可能地变，而且负的要从小到大变//如果全变成正的后还有剩余，看剩余的值是奇数还是偶数，偶数不变，奇数则把最小的数变成负的int n=nums.size();int sum=0;sort(nums.begin(),nums.end());for(int i=0;i<n;i++){if(nums[i]<0 &&k){nums[i]=-nums[i];k--;}sum+=nums[i];}if(k==0|| k%2==0){return sum;}else{sort(nums.begin(),nums.end());return sum-2*nums[0];}}
};

 答案是用绝对值进行排序。

class Solution {
static bool cmp(int a, int b) {return abs(a) > abs(b);
}
public:int largestSumAfterKNegations(vector<int>& A, int K) {sort(A.begin(), A.end(), cmp);       // 第一步for (int i = 0; i < A.size(); i++) { // 第二步if (A[i] < 0 && K > 0) {A[i] *= -1;K--;}}if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步int result = 0;for (int a : A) result += a;        // 第四步return result;}
};

134. 加油站

本题有点难度，不太好想，推荐大家熟悉一下方法二

链接：代码随想录

 

 

 这个题好像做过一遍！

不会，贪心贪得是什么呢，如果只是找到第一个差值为正的，那么要一个个验证吗？

比如

2、-3、6、-2这种情况，不应该从2开始，而是从6开始。

例一的差值是-2，-2，-2，3，3.

则如果sum<0.i++,sum=0

自己的做法，挣扎了半天还是错的。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n=gas.size();vector<int>v(n,0);for(int i=0;i<n;i++){v[i]=gas[i]-cost[i];}int index=0;//设最终要找到的索引是indexint sum=0;//for(int i=0;i<n;i++){sum+=v[i];if(sum<0){sum=0;index=i;continue;}}//最后获得的index是可能的结果，对其进行检查if(sum<0){return -1;}cout<<index<<" "<<sum<<endl;sum=0;for(int j=0;j<n;j++){sum+=v[(index+1+j)%n];cout<<sum<<endl;if(sum<0){return -1;}}return index+1;}
};

 

 真正的做法并没有像我一样，每一步都检验 是否为负。而是只看了total值最后相加是否为负，感觉需要背。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n=gas.size();vector<int>v(n,0);for(int i=0;i<n;i++){v[i]=gas[i]-cost[i];}int sum=0;int total=0;//主要用来检验所有的油量消耗完毕后是否大于等于0，如果小于零，那么怎么走都是完蛋int index=0;//要找到的indexfor(int i=0;i<n;i++){sum+=v[i];total+=v[i];if(sum<0){sum=0;index=i+1;//index立刻往前推}}if(total<0){return -1;}return index;}
};

135. 分发糖果

链接：代码随想录

本题涉及到一个思想，就是想处理好一边再处理另一边，不要两边想着一起兼顾，后面还会有题目用到这个思路。

 提示：根本就是自己的思考还很不足，又看到是困难题，直接看了答案。

class Solution {
public:int candy(vector<int>& ratings) {int n=ratings.size();/*自己的思考：既然是最少糖果数目，那么最小评分的孩子只有1个糖果，然后是它两边的，多一个，感觉像是波峰波谷问题，如果处于波谷那么就是1，然后波峰就慢慢往上爬。n个波谷n-1个波峰，波峰最高点取相邻两边最大值。觉得自己的思考没错，但是这道题是困难题，应该有很多需要完善的细节。不如直接看答案答案太精彩了。相比起我两边同时进行思考，又要波峰，又要波谷，答案先考虑从左往右的，右边孩子大于左边孩子。再考虑从右往左的，同时在已经计算的右边孩子的最大值，与从左计算的进行比较，相当于波峰最高点取相邻两边最大值。*/vector<int>candy(n,1);//默认所有人糖果为1for(int i=1;i<n;i++)//右孩子大于左孩子,i是右孩子{if(ratings[i]>ratings[i-1]){candy[i]=candy[i-1]+1;}}for(int i=n-2;i>=0;i--)//左孩子大于右孩子，i是左孩子{if(ratings[i]>ratings[i+1]){candy[i]=max(candy[i+1]+1,candy[i]);}}int result=0;for(int i=0;i<n;i++){result+=candy[i];}return result;}
};