贪心算法总结（2）

一、买卖股票的最佳时机

. - 力扣（LeetCode）

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

解法2：拆分交易

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

 解法3：动态规划

class Solution {
public:int maxProfit(vector<int>& prices){//有两种状态，第i天结束处于买入状态（手上有股票，可卖）     第i天结束后处于交易状态（手上没有股票，可以买int n=prices.size();//创建两个dp表vector<int> 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<int>& nums, int k) {//分类讨论 m表示负数的个数 //当m<=k 把前k大的负数都变成正数即可//m>k 时 先把所有的负数变成正数,然后看看k是奇数还是偶数//如果是偶数，直接返回总和，如果是奇数，还需要挑选最小的那个数进行取反int m=0,n=nums.size();for(auto e:nums) if(e<0) ++m;//开始进行分类讨论int ret=0;if(m>=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<string> sortPeople(vector<string>& names, vector<int>& h) {//解法1 创建一个新的二元数组，将身高和名字绑定，然后按照身高排序，再提取回来int n=names.size();map<int,string,greater<int>> hash;for(int i=0;i<n;++i)  hash[h[i]]=names[i];//然后提取出来vector<string> ret;ret.reserve(n);for(auto kv:hash) ret.emplace_back(kv.second);return ret; }
};

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

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

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

. - 力扣（LeetCode）

class Solution {
public://如果比得过，就比，如果比不过 就干掉最强的那个vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {//对nums1进行升序排序 对nums2进行下标的排序int n=nums1.size();sort(nums1.begin(),nums1.end());vector<int> 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[j];});//然后进行赛马 //用nums2存储最后的结果int left=0,right=n-1;for(auto&x:nums1)if(x>nums2[index[left]]) nums2[index[left++]]=x;   //如果我比你大 我就超越你else nums2[index[right--]]=x;return nums2;//交换论证法 更经常用的原因是  最优解可能是有多个的，所以我们可以把最优解调整成贪心解}
};

六、分发饼干

. - 力扣（LeetCode）

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& 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;}
};