贪默算法总结（1）

一、贪默算法简介

常用方法：交换论证法、数学归纳法、反证法、分类讨论 
 二、柠檬水找零（交换论证法）

. - 力扣（LeetCode）

1. class Solution {
2. public:
3.     bool lemonadeChange(vector<int>& bills) {
4.          int five=0,ten=0;
5.          for(auto&e:bills)
6.             if(e==5) ++five;
7.             else if(e==10)
8.             {
9.                 if(five==0) return false;
10.                 --five,++ten;
11.             }
12.             else //贪心策略
13.             {
14.                 if(five&&ten) --five,--ten;
15.                 else if(five>=3) five-=3;
16.                 else return false;
17.             }
18.          return true;
19.     }
20.     //交换论证法、数学归纳法和反证法常用的策略
21. };

复制代码

三、将数组减半的最小操纵次数（交换论证法）

. - 力扣（LeetCode）

1. class Solution {
2. public:
3.     int halveArray(vector<int>& nums) {
4.         priority_queue<double> q(nums.begin(),nums.end());
5.         double sum=accumulate(nums.begin(),nums.end(),0.0);
6.         int ret=0;
7.         sum/=2.0;
8.         while(sum>0)
9.         {
10.             double t=q.top()/2.0;
11.             q.pop();
12.             sum-=t;
13.             q.push(t);
14.             ++ret;
15.         }
16.         return ret;
17.     }
18. };

复制代码

四、最大数（排序规则明白+全序性证明）

. - 力扣（LeetCode）

1. class Solution {
2. public:
3.     string largestNumber(vector<int>& nums) {
4.        //贪心策略 先转化成字符串 然后利用字典序排序
5.        vector<string> strs;
6.        strs.reserve(nums.size());//提前扩容 小优化
7.        for(auto&e:nums) strs.emplace_back(to_string(e));
8.        sort(strs.begin(),strs.end(),[](const string&s1,const string&s2)
9.        {
10.                return s1+s2>s2+s1;//大的在前面
11.        });
12.        //按顺序加入到ret中返回
13.        string ret;
14.        for(auto&s:strs) ret+=s;
15.        //细节处理:前导0 除非都是0才会出现前导0  所以我们只需要当出现前导0的时候，返回"0"即可
16.        if(ret[0]=='0') return "0";
17.        return ret;
18.     }
19.     //全序关系  一个集合中任意选出两个元素 如果在你定义的比较规则下能够满足全序关系
20.                 //我们就说这个集合是可以排序的
21.         //1、完全性 可以推测出他的大小关系（a>=b a<=b）
22.         //2、反对称性 a>=b&&b>=a  ——>a==b   a前和b前无所谓(唯一性)
23.         //3、传递性 a>=b  b>=c a>=c
24. };

复制代码

五、摆动序列（反证法）

. - 力扣（LeetCode）

1. class Solution {
2. public:
3.     int wiggleMaxLength(vector<int>& nums)
4.     {
5.         int n=nums.size();
6.         if(n<2) return n;
7.       //总是选择当前的最优策略
8.        int left=0,ret=0; //left表示左边的状态
9.        for(int i=0;i<n-1;++i)
10.        {
11.         int right=nums[i+1]-nums[i];
12.         if(right==0) continue;//跳过相等的情况
13.         if(right*left<=0) ++ret;
14.         left=right;
15.        }
16.       return ret+1; //算上最后一个
17.     }
18. };

复制代码

 六、最长递增子序列（交换论证）

. - 力扣（LeetCode）

贪心+二分

1. class Solution {
2. public:
3.     int lengthOfLIS(vector<int>& nums)
4.     {
5.        //贪心+二分
6.        int n=nums.size();
7.        vector<int> ret;
8.        ret.emplace_back(nums[0]);
9.        for(int i=1;i<n;++i)
10.          //如果比最后一个数大 就直接尾插即可
11.          if(nums[i]>ret.back()) ret.emplace_back(nums[i]);
12.          //否则就用二分
13.          else
14.          {
15.             int left=0,right=ret.size()-1;
16.             while(left<right)
17.             {
18.                 int mid=(left+right)>>1;
19.                 if(ret[mid]<nums[i]) left=mid+1;
20.                 else right=mid;
21.             }
22.             ret[left]=nums[i];
23.          }
24.         return ret.size();
25.     }
26. };

复制代码

 七、递增的三元子序列

. - 力扣（LeetCode）

贪心： 

1. class Solution {
2. public:
3.     bool increasingTriplet(vector<int>& nums) {
4.      //贪心策略
5.      int n=nums.size();
6.      if(n<3) return false;
7.      int first=nums[0];
8.      int second=INT_MAX;
9.      for(int i=1;i<n;++i)
10.         if(nums[i]>second) return true;
11.         else if(nums[i]>first) second=nums[i];
12.         else first=nums[i];//否则我肯定比较小 就得更新first
13.      return false;
14.     }
15. };

复制代码

八、最长连续递增子序列

. - 力扣（LeetCode）

贪心+滑动窗口： 

1. class Solution {
2. public:
3.     int findLengthOfLCIS(vector<int>& nums) {
4.      //贪心+双指针
5.      int ret=0;
6.      int n=nums.size();
7.      for(int i=0;i<n;)
8.      {
9.        int j=i+1;
10.        while(j<n&&nums[j]>nums[j-1]) ++j;
11.        ret=max(j-i,ret);
12.        i=j;
13.      }
14.      return ret;
15.     }
16. };

复制代码

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。