贪心算法总结（2）

一、买卖股票的最佳时机

. - 力扣（LeetCode）

class Solution {public: int maxProfit(vector& prices) { int mini=INT_MAX; int ret=0; for(int&price:prices){ //遍历的时候，我们随时去更新最小的值，然后让每一位数都来-最小值 更新利润，这里不能直接用最大值 //因为最大值可能在最小值的左边 ret=max(ret,price-mini); mini=min(price,mini); } return ret; }};

二、买卖股票的最佳时机II 

. - 力扣（LeetCode）

解法1：双指针（重点掌握）

class Solution {public: int maxProfit(vector& p) { //只要是正收益 就交易 //双指针+贪心 int ret=0,n=p.size(); for(int i=0,j=0;i<n;){ while(j+1p[j]) ++j; ret+=p[j]-p[i]; ++j,i=j; } return ret; }};

解法2：拆分交易

class Solution {public: int maxProfit(vector& p) { //拆分交易 int ret=0,n=p.size(); for(int i=1;ip[i-1]) ret+=p[i]-p[i-1]; return ret; }};

 解法3：动态规划

class Solution {public: int maxProfit(vector& prices) { //有两种状态，第i天结束处于买入状态（手上有股票，可卖） 第i天结束后处于交易状态（手上没有股票，可以买 int n=prices.size(); //创建两个dp表 vector f(n);//第i天结束后处于买入状态 //情况1，前一天处于买入状态，啥也没干，还是处于买入状态f[i]=f[i-1] //情况2，前一天卖过，然后今天刚买 f[i]=g[i-1]-prices[i] auto g=f;//第i天结束后处于交易状态 //情况1，前一天还是可交易状态，啥也没干 g[i]=g[i-1] //情况2.前一天处于买入状态，今天刚卖出一只股票，外加手续费 g[i]=f[i-1]+prices[i]-fee //初始化， f[0]=-prices[0]; for(int i=1;i<n;++i){ f[i]=max(f[i-1],g[i-1]-prices[i]); g[i]=max(g[i-1],f[i-1]+prices[i]); } return g[n-1]; }};

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

. - 力扣（LeetCode）

class Solution {public: int largestSumAfterKNegations(vector& nums, int k) { //分类讨论 m表示负数的个数 //当mk 时 先把所有的负数变成正数,然后看看k是奇数还是偶数 //如果是偶数，直接返回总和，如果是奇数，还需要挑选最小的那个数进行取反 int m=0,n=nums.size(); for(auto e:nums) if(e=k) { sort(nums.begin(),nums.end()); for(int i=0;i<k;++i) ret+=-nums[i]; for(int i=k;i<n;++i) ret+=nums[i]; } else{ int mini=INT_MAX; for(auto e:nums) { ret+=abs(e); mini=min(mini,abs(e)); } if((k-m)%2) ret-=2*mini; } return ret; }};

四、按身高排序（下标数组排序）

. - 力扣（LeetCode）

解法2：哈希存下标映射

class Solution {public: vector sortPeople(vector& names, vector& h) { //解法1 创建一个新的二元数组，将身高和名字绑定，然后按照身高排序，再提取回来 int n=names.size(); map<int,string,greater> hash; for(int i=0;i<n;++i) hash[h[i]]=names[i]; //然后提取出来 vector ret; ret.reserve(n); for(auto kv:hash) ret.emplace_back(kv.second); return ret; }};

解法3：对下标排序（重要技巧）

class Solution {public: vector sortPeople(vector& names, vector& h) { //解法2 创建一个下标数组 对下标数组进行排序 然后找到原数组的信息 int n=names.size(); vector index(n); for(int i=0;ih[j]; }); vector ret(n); for(int i=0;i<n;++i) ret[i]=names[index[i]]; return ret; }};

五、优势洗牌（田忌赛马策略）

. - 力扣（LeetCode）

class Solution {public: //如果比得过，就比，如果比不过 就干掉最强的那个 vector advantageCount(vector& nums1, vector& nums2) { //对nums1进行升序排序 对nums2进行下标的排序 int n=nums1.size(); sort(nums1.begin(),nums1.end()); vector index(n); iota(index.begin(), index.end(),0); //用val的连续++初始化 sort(index.begin(),index.end(),[&nums2](const int&i,const int&j){  return nums2[i]nums2[index[left]]) nums2[index[left++]]=x; //如果我比你大 我就超越你 else nums2[index[right--]]=x; return nums2; //交换论证法 更经常用的原因是 最优解可能是有多个的，所以我们可以把最优解调整成贪心解 }};

六、分发饼干

. - 力扣（LeetCode）

class Solution {public: int findContentChildren(vector& g, vector& s) { //先排序 满足的直接喂 不满足的就看看下一个孩子 sort(g.begin(),g.end()); sort(s.begin(),s.end()); //双指针 int ret=0,n1=g.size(),n2=s.size(); for(int i=0,j=0;i<n1&&j<n2;++i,++j){ //找饼干 while(j<n2&&s[j]<g[i]) ++j; if(j<n2) ++ret; } return ret; }};