贪默算法总结（1）
https://img-blog.csdnimg.cn/direct/3ced876e319a476090dbd2f0b50cf8aa.gif一、贪默算法简介
https://img-blog.csdnimg.cn/direct/1c7ee64f003247b19aa4f9fa2f3fad0f.png
常用方法：交换论证法、数学归纳法、反证法、分类讨论
二、柠檬水找零（交换论证法）
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/f38febc081b74a51bb039d1b2ed5b033.png
https://img-blog.csdnimg.cn/direct/ff5677a98e6747d9a42fb8155cac5b8d.png
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five=0,ten=0;
for(auto&e:bills)
if(e==5) ++five;
else if(e==10)
{
if(five==0) return false;
--five,++ten;
}
else //贪心策略
{
if(five&&ten) --five,--ten;
else if(five>=3) five-=3;
else return false;
}
return true;
}
//交换论证法、数学归纳法和反证法常用的策略
}; 三、将数组减半的最小操纵次数（交换论证法）
. - 力扣（LeetCode）https://img-blog.csdnimg.cn/direct/3ef89fe3f5cc46ffa286212d3e85e37f.png
https://img-blog.csdnimg.cn/direct/e32557d1a02b46788a2252c58aaae2be.png
class Solution {
public:
int halveArray(vector<int>& nums) {
priority_queue<double> q(nums.begin(),nums.end());
double sum=accumulate(nums.begin(),nums.end(),0.0);
int ret=0;
sum/=2.0;
while(sum>0)
{
double t=q.top()/2.0;
q.pop();
sum-=t;
q.push(t);
++ret;
}
return ret;
}
}; 四、最大数（排序规则明白+全序性证明）
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/358aa4462ea846d8ba5094ec75e00786.png
https://img-blog.csdnimg.cn/direct/e1ed2fdac911489ab5acd0c7e620b67c.pnghttps://img-blog.csdnimg.cn/direct/298390abb6314edaac57fa5f1b009323.png
class Solution {
public:
string largestNumber(vector<int>& nums) {
//贪心策略 先转化成字符串 然后利用字典序排序
vector<string> strs;
strs.reserve(nums.size());//提前扩容 小优化
for(auto&e:nums) strs.emplace_back(to_string(e));
sort(strs.begin(),strs.end(),[](const string&s1,const string&s2)
{
return s1+s2>s2+s1;//大的在前面
});
//按顺序加入到ret中返回
string ret;
for(auto&s:strs) ret+=s;
//细节处理:前导0 除非都是0才会出现前导0所以我们只需要当出现前导0的时候，返回"0"即可
if(ret=='0') return "0";
return ret;
}
//全序关系一个集合中任意选出两个元素 如果在你定义的比较规则下能够满足全序关系
//我们就说这个集合是可以排序的
//1、完全性 可以推测出他的大小关系（a>=b a<=b）
//2、反对称性 a>=b&&b>=a——>a==b a前和b前无所谓(唯一性)
//3、传递性 a>=bb>=c a>=c
}; 五、摆动序列（反证法）
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/3d40cc53112e40a7b667fdeb0ff00179.png
https://img-blog.csdnimg.cn/direct/d9f78ae571e34cbe9fb250c0b6fd389c.png
class Solution {
public:
int wiggleMaxLength(vector<int>& nums)
{
int n=nums.size();
if(n<2) return n;
//总是选择当前的最优策略
int left=0,ret=0; //left表示左边的状态
for(int i=0;i<n-1;++i)
{
int right=nums-nums;
if(right==0) continue;//跳过相等的情况
if(right*left<=0) ++ret;
left=right;
}
return ret+1; //算上最后一个
}
}; 六、最长递增子序列（交换论证）
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/d921a555916d451a8c9a7546473daa82.png
https://img-blog.csdnimg.cn/direct/ed88cb11319b4e9e8534dbba4d0259c6.png
贪心+二分
class Solution {
public:
int lengthOfLIS(vector<int>& nums)
{
//贪心+二分
int n=nums.size();
vector<int> ret;
ret.emplace_back(nums);
for(int i=1;i<n;++i)
//如果比最后一个数大 就直接尾插即可
if(nums>ret.back()) ret.emplace_back(nums);
//否则就用二分
else
{
int left=0,right=ret.size()-1;
while(left<right)
{
int mid=(left+right)>>1;
if(ret<nums) left=mid+1;
else right=mid;
}
ret=nums;
}
return ret.size();
}
}; 七、递增的三元子序列
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/e192bd8c4cb04c13b3dbab763dee9426.png
https://img-blog.csdnimg.cn/direct/63c8abb98bc94b3f9b71ad8fc135a547.png贪心：
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
//贪心策略
int n=nums.size();
if(n<3) return false;
int first=nums;
int second=INT_MAX;
for(int i=1;i<n;++i)
if(nums>second) return true;
else if(nums>first) second=nums;
else first=nums;//否则我肯定比较小 就得更新first
return false;
}
}; 八、最长连续递增子序列
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/b629037604114b00ae3adbc20e8244f9.png
https://img-blog.csdnimg.cn/direct/46976a56f83b45f79f4146f6eb0c82ad.png
贪心+滑动窗口：
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
//贪心+双指针
int ret=0;
int n=nums.size();
for(int i=0;i<n;)
{
int j=i+1;
while(j<n&&nums>nums) ++j;
ret=max(j-i,ret);
i=j;
}
return ret;
}
}; https://img-blog.csdnimg.cn/direct/54b3c6790ac34d9fa4496ca5ca1b01d2.jpeg
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]