柚子快報邀請碼778899分享：【算法】貪心算法練習(xí)一
柚子快報邀請碼778899分享：【算法】貪心算法練習(xí)一
個人主頁 ： zxctscl 如有轉(zhuǎn)載請先通知
題目
1. 貪心算法的介紹2. 860. 檸檬水找零2.1 分析2.2 代碼3. 2208. 將數(shù)組和減半的最少操作次數(shù)3.1 分析3.2 代碼4. 179. 最大數(shù)4.1 分析4.2 代碼
1. 貪心算法的介紹
一、貪心策略：解決問題的策略，局部最優(yōu)->全局最優(yōu)
把解決問題的過程分為若干步；解決每一步的時候，都選擇當(dāng)前看起來“最優(yōu)的”解法；希望得到全局最優(yōu)。
二、貪心策略的正確性 因為有可能“貪心策略”是一個錯誤的方法 正確的貪心策略，是需要證明的
常見的證明方法就是在數(shù)學(xué)中見過的所有證明方法。
三、學(xué)習(xí)貪心算法的方向 遇到不會的貪心題，很正常，把心態(tài)放平。
前期學(xué)習(xí)的時候，把重點放在貪心的策略上，把這個策略當(dāng)做經(jīng)驗吸收。如何證明貪心策略是正確的
2. 860. 檸檬水找零
2.1 分析
一、題目解析 題目已經(jīng)提到：一開始你手頭沒有任何零錢，如果第一個顧客給的錢超過了5美元，那么就沒有零錢找，就返回false。 考慮當(dāng)前的顧客時候，是不考慮后面的顧客。
二、算法原理 分情況討論：第一種：當(dāng)顧客給了5美元，就直接收下； 第二種，當(dāng)顧客給了10美元，先判斷一下有沒有5美元，有就收下，沒有就返回false; 第三種：20美元的找零，可以分一張10和一張5；還可以找三種5塊錢，有分歧的時候就得判斷一下哪一個找零更好，是10+5，還是5+5+5，所以對于5塊錢的作用很大的時候，就把5塊錢保留。
2.2 代碼
class Solution {
public:
bool lemonadeChange(vector
int five=0,ten=0;
for(auto x: bills)
{
if(x==5) five++;
else if(x==10)
{
if(five==0) return false;
five--;ten++;
}
else
{
if(ten&&five)
{
ten--;five--;
}
else if(five>=3)
{
five-=3;
}
else return false;
}
}
return true;
}
};
3. 2208. 將數(shù)組和減半的最少操作次數(shù)
3.1 分析
一、題目解析 題目要求返回將 nums 數(shù)組和至少減少一半的最少操作數(shù)，看一下例1： 數(shù)組和是33，一半就是16.5，先選擇19減半就是9.5，此時數(shù)組和沒有小于16.5；然后繼續(xù)選擇9.5減半為4.75，此時數(shù)組和沒有小于16.5；再選擇8減半為4，此時此時數(shù)組和小于16.5，總共就三次減半。
二、算法原理 每次挑選當(dāng)前數(shù)組中，最大的那個數(shù)，然后減半，最大的數(shù)減半，才有可能最快減到數(shù)組和減少到至少一半。 為了選擇最大的數(shù)，遍歷一遍數(shù)組的時間復(fù)雜度太高了，所以就用一個大根堆，每次堆頂?shù)脑鼐褪亲畲蟮臄?shù)。
3.2 代碼
class Solution {
public:
int halveArray(vector
priority_queue
double sum=0;
for(auto x:nums)
{
heap.push(x);
sum+=x;
}
sum/=2.0;
int count=0;
while(sum>0)
{
double t=heap.top()/2;
heap.pop();
sum-=t;
count++;
heap.push(t);
}
return count;
}
};
4. 179. 最大數(shù)
4.1 分析
一、題目解析 題目已經(jīng)提到： 要得到最大的拼接數(shù)，就得先把這些數(shù)先拼接起來，然后比較找到最大的那一個就行。
二、算法原理 這里就得排序，確定元素的先后順序：誰在前，誰在后 給這個數(shù)組排序，比如[a,b]：如果ab>ba,那么a前,b后；如果ab=ba，那么順序無所謂；如果ab 4.2 代碼 class Solution { public: string largestNumber(vector vector for(int x:nums)strs.push_back(to_string(x)); sort(strs.begin(),strs.end(),[](const string& s1,const string& s2) { return s1+s2>s2+s1; }); string ret; for(auto& s:strs) { ret+=s; } if(ret[0]=='0')return "0"; return ret; } }; 有問題請指出，大家一起進步！?。?/p> 柚子快報邀請碼778899分享：【算法】貪心算法練習(xí)一 好文閱讀
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Kogan優(yōu)選坊
