前言
思念折腾人，也锻炼人，更锻造人的性格的沉稳和感情的深沉。思念别人是一种温馨，被人思念是一种幸福
一、K次取反后最大化的数组和
1、暴力思路：
在k还没有用完前，每次选择最小的元素，把它取反，这样就能得到最大的和。
class Solution { public: int largestSumAfterKNegations(vector<int>& nums, int k) { while(k--) //记录K的次数 { int min=1e8; int j=0; for(int i=0;i<nums.size();i++) { if(nums[i]<min) //找出最小值 { min=nums[i]; j=i; } } nums[j]=-nums[j]; //反 } int sum=0; for(int i=0;i<nums.size();i++) //记录和 { printf("%d ",nums[i]); sum+=nums[i]; } return sum; } };
但这是时间复杂度比较大的解法，我们还可以改善一下。
2、贪心思路：
要先和最大。
1、把负数全部变成正数。
2、如果全是正数，把最小的正数变成负数。
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); //按绝对值从大到小排序 int i=0; for(i=0;i<nums.size();i++) { if(nums[i]<0) //负数都反 { nums[i]=-nums[i]; k--; } if(k==0) //用完了就退出了 { break; } } if(k%2==1) //剩余的看单双数，双数等于不变 { nums[nums.size()-1]*=-1; //末尾最小 } int sum=0; for(auto it:nums) { sum+=it; } return sum; } };
二、加油站
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
1、贪心思路1：
在确定了是可以跑一圈的情况下，在中间出现了负值，说明从0到负值位置开始是行不通的，要从后面往前，找到那个可以补缺的点哪里。
class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int min=1e8; int sum=0; for(int i=0;i<gas.size();i++) { sum+=gas[i]-cost[i]; //从0开始跑计算总油量 if(sum<min) { min=sum; //记录最小的负值 } } if(sum<0) //小于0就退出，因为不可能跑一圈了 { return -1; } if(min>=0) //如果从0开始跑可以跑一圈就返回0 { return 0; } for(int i=gas.size()-1;i>=0;i--) //从后往前遍历 { min+=gas[i]-cost[i]; //啥时候可以填补空缺 if(min>=0) return i; } return -1; } };
2、贪心思路2：
如果cursum小于0了，那么【0，i】上面开始都是不行的。
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) { // 当前累加rest[i]和 curSum一旦小于0 start = i + 1; // 起始位置更新为i+1 curSum = 0; // curSum从0开始 } } if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了 return start; } };
三、分发糖果
class Solution { public: int candy(vector<int>& ratings) { vector<int> candys(ratings.size(),1); for(int i=1;i<ratings.size();i++) //右孩子大于左孩子 { if(ratings[i]>ratings[i-1]) { candys[i]=candys[i-1]+1; //比旁边的孩子多一个 } } for(int i=ratings.size()-2;i>=0;i--) //重点，重后往前 { if(ratings[i]>ratings[i+1]) { candys[i]=max(candys[i],candys[i+1]+1); } } int sum=0; for(auto it:candys) sum+=it; return sum; } };
为什么要从后往前呢，从后往前，我们可以用处理过的结果来判断，因为前一个是处理过的，从前往后，就是依据前一个判断后一个，前一个都是没有处理过的。
总结
贪心没有套路，只有一点感觉，继续加油哇。
