柚子快報(bào)邀請(qǐng)碼778899分享：c++ 貪心算法總結(jié)（1）

http://yzkb.51969.com/

一、貪心算法簡(jiǎn)介

常用方法：交換論證法、數(shù)學(xué)歸納法、反證法、分類(lèi)討論?

?二、檸檬水找零（交換論證法）

. - 力扣（LeetCode）

class Solution {

public:

bool lemonadeChange(vector& 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;

}

//交換論證法、數(shù)學(xué)歸納法和反證法常用的策略

};

三、將數(shù)組減半的最小操作次數(shù)（交換論證法）

. - 力扣（LeetCode）

class Solution {

public:

int halveArray(vector& nums) {

priority_queue 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;

}

};

四、最大數(shù)（排序規(guī)則理解+全序性證明）

. - 力扣（LeetCode）

class Solution {

public:

string largestNumber(vector& nums) {

//貪心策略 先轉(zhuǎn)化成字符串 然后利用字典序排序

vector strs;

strs.reserve(nums.size());//提前擴(kuò)容 小優(yōu)化

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;

//細(xì)節(jié)處理:前導(dǎo)0 除非都是0才會(huì)出現(xiàn)前導(dǎo)0 所以我們只需要當(dāng)出現(xiàn)前導(dǎo)0的時(shí)候，返回"0"即可

if(ret[0]=='0') return "0";

return ret;

}

//全序關(guān)系 一個(gè)集合中任意選出兩個(gè)元素 如果在你定義的比較規(guī)則下能夠滿足全序關(guān)系

//我們就說(shuō)這個(gè)集合是可以排序的

//1、完全性 可以推測(cè)出他的大小關(guān)系（a>=b a<=b）

//2、反對(duì)稱性 a>=b&&b>=a ——>a==b a前和b前無(wú)所謂(唯一性)

//3、傳遞性 a>=b b>=c a>=c

};

五、擺動(dòng)序列（反證法）

. - 力扣（LeetCode）

class Solution {

public:

int wiggleMaxLength(vector& nums)

{

int n=nums.size();

if(n<2) return n;

//總是選擇當(dāng)前的最優(yōu)策略

int left=0,ret=0; //left表示左邊的狀態(tài)

for(int i=0;i

{

int right=nums[i+1]-nums[i];

if(right==0) continue;//跳過(guò)相等的情況

if(right*left<=0) ++ret;

left=right;

}

return ret+1; //算上最后一個(gè)

}

};

?六、最長(zhǎng)遞增子序列（交換論證）

. - 力扣（LeetCode）

貪心+二分

class Solution {

public:

int lengthOfLIS(vector& nums)

{

//貪心+二分

int n=nums.size();

vector ret;

ret.emplace_back(nums[0]);

for(int i=1;i

//如果比最后一個(gè)數(shù)大 就直接尾插即可

if(nums[i]>ret.back()) ret.emplace_back(nums[i]);

//否則就用二分

else

{

int left=0,right=ret.size()-1;

while(left

{

int mid=(left+right)>>1;

if(ret[mid]

else right=mid;

}

ret[left]=nums[i];

}

return ret.size();

}

};

?七、遞增的三元子序列

. - 力扣（LeetCode）

貪心：?

class Solution {

public:

bool increasingTriplet(vector& nums) {

//貪心策略

int n=nums.size();

if(n<3) return false;

int first=nums[0];

int second=INT_MAX;

for(int i=1;i

if(nums[i]>second) return true;

else if(nums[i]>first) second=nums[i];

else first=nums[i];//否則我肯定比較小 就得更新first

return false;

}

};

八、最長(zhǎng)連續(xù)遞增子序列

. - 力扣（LeetCode）

貪心+滑動(dòng)窗口：?

class Solution {

public:

int findLengthOfLCIS(vector& nums) {

//貪心+雙指針

int ret=0;

int n=nums.size();

for(int i=0;i

{

int j=i+1;

while(jnums[j-1]) ++j;

ret=max(j-i,ret);

i=j;

}

return ret;

}

};

?

柚子快報(bào)邀請(qǐng)碼778899分享：c++ 貪心算法總結(jié)（1）

http://yzkb.51969.com/

推薦文章