第C++算法精講之貪心算法目錄選擇排序平衡字符串買股票的最佳時(shí)機(jī)跳躍游戲錢幣找零多機(jī)調(diào)度問(wèn)題活動(dòng)選擇無(wú)重疊區(qū)間

選擇排序

我們熟知的選擇排序，其采用的就是貪心策略。它所采用的貪心策略即為每次從未排序的數(shù)據(jù)中選取最小值，并把最小值放在未排序數(shù)據(jù)的起始位置，直到未排序的數(shù)據(jù)為0，則結(jié)束排序。

voidswap(int*arr,inti,intj)

inttmp=arr[i];

arr[i]=arr[j];

arr[j]=tmp;

voidselectSort(int*arr,intn)

//降序

for(inti=0;ii++)

intmaxIndex=i;

for(intj=i+1;jj++)

if(arr[j]=arr[maxIndex])

maxIndex=j;

swap(arr,i,maxIndex);

}

平衡字符串

問(wèn)題描述：

在一個(gè)平衡字符串中，‘L'和‘R'字符的數(shù)量是相同的。

給你一個(gè)平衡字符串s，請(qǐng)你將它分割成盡可能多的平衡字符串。

注意：分割得到的每個(gè)字符串都必須是平衡字符串，且分割得到的平衡字符串是原平衡字符串的連續(xù)子串。

返回可以通過(guò)分割得到的平衡字符串的最大數(shù)量。

貪心策略：從左往右掃描，只要達(dá)到平衡，就立即分割，不要有嵌套的平衡。

故可以定義一個(gè)變量balance，在遇到不同的字符時(shí)，向不同的方向變化，當(dāng)balance為0時(shí)達(dá)到平衡，分割數(shù)更新。

比如：從左往右掃描字符串s，遇到L，balance-1，遇到R，balance+1.當(dāng)balance為0時(shí)，更新cnt++如果最終cnt==0，說(shuō)明s只需要保持原樣，返回1

代碼實(shí)現(xiàn)：

classSolution{

public:

intbalancedStringSplit(strings){

if(s.size()==1)

return0;

intcnt=0;

intbalance=0;

for(inti=0;is.size();i++)

if(s[i]=='R')

--balance;

else

++balance;

if(balance==0)

cnt++;

if(cnt==0)

return1;

returncnt;

};

買股票的最佳時(shí)機(jī)

問(wèn)題描述：

給定一個(gè)數(shù)組prices，其中prices[i]是一支給定股票第i天的價(jià)格。

設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。

貪心策略：

連續(xù)上漲交易日：第一天買最后一天賣收益最大，等價(jià)于每天都買賣。

連續(xù)下降交易日：不買賣收益最大，即不會(huì)虧錢。

故可以遍歷整個(gè)股票交易日價(jià)格列表，在所有上漲交易日都買賣（賺到所有利潤(rùn)），所有下降交易日都不買賣（永不虧錢）

例如從10到50是連續(xù)上漲的5天，可以第一天買入，最后一天賣出，利潤(rùn)為40，等價(jià)于第一天買入第二天賣出，第二天再買入。。。以此類推

代碼實(shí)現(xiàn)：

classSolution{

public:

intmaxProfit(vectorintprices){

intprofit=0;

for(inti=0;iprices.size()-1;i++)

if(prices[i]=prices[i+1])

profit+=prices[i+1]-prices[i];

returnprofit;

};

跳躍游戲

問(wèn)題描述：

給定一個(gè)非負(fù)整數(shù)數(shù)組nums，你最初位于數(shù)組的第一個(gè)下標(biāo)。

數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。

判斷你是否能夠到達(dá)最后一個(gè)下標(biāo)。

貪心策略：

根據(jù)題目描述，對(duì)于數(shù)組中的任意一個(gè)位置y，只要存在一個(gè)位置x，它本身可以到達(dá)，并且它跳躍的最大長(zhǎng)度為x+nums[x]，這個(gè)值大于等于y，即x+nums[x]=y，那么位置y也可以到達(dá)。即對(duì)于每一個(gè)可以到達(dá)的位置x，它使得x+1，x+2，…，x+nums[x]=y，那么位置y也可以到達(dá)。一次遍歷數(shù)組中的每一個(gè)位置，并實(shí)時(shí)更新最遠(yuǎn)可以到達(dá)的位置。對(duì)于當(dāng)前遍歷到的位置x，如果它在最遠(yuǎn)可以到達(dá)的位置范圍內(nèi)，那么我們就可以從起點(diǎn)通過(guò)若干次跳躍達(dá)到該位置，因此我們可以用x+nums[x]更新最遠(yuǎn)可以到達(dá)的位置。

在遍歷的過(guò)程中，如果最遠(yuǎn)可以到達(dá)的位置大于等于數(shù)組中的最后一個(gè)位置，那就說(shuō)明最后一個(gè)位置可到達(dá)，直接返回true。遍歷結(jié)束后，最后一個(gè)位置仍不可達(dá)，返回false。

例如：[2,3,1,1,4]

一開(kāi)始在位置0，可跳躍的最大長(zhǎng)度為2，因此最遠(yuǎn)可以到達(dá)的位置倍更新為2；繼續(xù)遍歷到位置1，由于1=2，因此位置1可達(dá)。用1加上它最大可跳躍的長(zhǎng)度3，將最遠(yuǎn)可以到達(dá)的位置更新為4，4大于最后一個(gè)位置4，返回true

代碼實(shí)現(xiàn)：

classSolution{

public:

boolcanJump(vectorintnums){

intmaxLen=nums[0];

for(inti=0;inums.size();i++)

if(i=maxLen)

maxLen=max(i+nums[i],maxLen);

if(maxLen=nums.size()-1)

returntrue;

returnfalse;

};

錢幣找零

問(wèn)題描述：

假設(shè)1元、2元、5元、10元、20元、50元、100元的紙幣分別有c0,c1,c2,c3,c4,c5,c6張?，F(xiàn)在要用這些錢來(lái)支付K元，至少要用多少?gòu)埣垘牛?/p>

貪心策略：顯然，每一步盡可能用面值大的紙幣即可。在日常生活中我們也是這么做的。

代碼實(shí)現(xiàn)：

//按面值降序

structcmp{

booloperator()(vectorinta1,vectorinta2){

returna1[0]a2[0];

intsolve(vectorvectorintmoneyCount,intmoney)

intnum=0;

sort(moneyCount.begin(),moneyCount.end(),cmp());

//首先選擇最大面值的紙幣

for(inti=0;imoneyCount.size()-1;i++)

//選擇需要的當(dāng)前面值和該面值有的數(shù)量中的較小值

intc=min(money/moneyCount[i][0],moneyCount[i][1]);

money-=c*moneyCount[i][0];

num+=c;

if(money0)

num=-1;

returnnum;

}

多機(jī)調(diào)度問(wèn)題

問(wèn)題描述：

某工廠有n個(gè)獨(dú)立的作業(yè)，由m臺(tái)相同的機(jī)器進(jìn)行加工處理。作業(yè)i所需的加工時(shí)間為ti，任何作業(yè)在被處理時(shí)不能中斷，也不能進(jìn)行拆分處理?，F(xiàn)廠長(zhǎng)請(qǐng)你給他寫(xiě)一個(gè)程序：算出n個(gè)作業(yè)由m臺(tái)機(jī)器加工處理的最短時(shí)間。

輸入：第一行T（1T100)表示有T組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)的第一行分別是整數(shù)n，m（1=n=10000，1=m=100），接下來(lái)的一行是n個(gè)整數(shù)ti（1=t=100)。

輸出：所需的最短時(shí)間

貪心策略：

這個(gè)問(wèn)題還沒(méi)有最優(yōu)解，但是用貪心選擇策略可設(shè)計(jì)出較好的近似算法（求次優(yōu)解）當(dāng)n=m時(shí)，只要將作業(yè)分給每一個(gè)機(jī)器即可；當(dāng)nm時(shí)，首先將n個(gè)作業(yè)時(shí)間從大到小排序，然后依此順序?qū)⒆鳂I(yè)分配給下一個(gè)作業(yè)馬上結(jié)束的處理機(jī)。也就是說(shuō)從剩下的作業(yè)中選擇需要處理時(shí)間最長(zhǎng)的，然后依次選擇處理時(shí)間次長(zhǎng)的，直到所有作業(yè)全部處理完畢，或者機(jī)器不能再處理其他作業(yè)為止。如果我們每次是將需要處理時(shí)間最短的作業(yè)分配給空閑的機(jī)器，那么可能就會(huì)儲(chǔ)秀安其它所有作業(yè)都處理完了只剩下所需時(shí)間最長(zhǎng)的作業(yè)在處理的情況，這樣勢(shì)必效率較低。

代碼實(shí)現(xiàn)：

structcmp{

booloperator()(constintx,constinty){

returnx

intfindMax(vectorintmachines)

intret=0;

for(inti=0;imachines.size();i++)

if(machines[i]machines[ret])

ret=i;

returnmachines[ret];

intgreedStrategy(vectorintworks,vectorintmachines)

//降序

sort(works.begin(),works.end(),cmp());

intn=works.size();

intm=machines.size();

for(inti=0;ii++)

intfinish=0;

intmachineTime=machines[finish];

for(intj=1;jj++)

if(machines[j]machines[finish])

finish=j;

machines[finish]+=works[i];

returnfindMax(machines);

}

活動(dòng)選擇

問(wèn)題描述：

有n個(gè)需要在同一天使用同一個(gè)教室的活動(dòng)a1,a2,…,an，教室同一時(shí)刻只能由一個(gè)活動(dòng)使用。每個(gè)活動(dòng)a[i]都有一個(gè)開(kāi)始時(shí)間s[i]和結(jié)束時(shí)間f[i]。一旦被選擇后，活動(dòng)a[i]就占據(jù)半開(kāi)時(shí)間區(qū)間[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重疊，a[i]和a[j]兩個(gè)活動(dòng)就可以被安排在這一天。求使得盡量多的活動(dòng)能不沖突的舉行的最大數(shù)量。

貪心策略：

1.每次都選擇開(kāi)始時(shí)間最早的活動(dòng)，不能得到最優(yōu)解。

2.每次都選擇持續(xù)時(shí)間最短的活動(dòng)，不能得到最優(yōu)解。

3.每次選取結(jié)束時(shí)間最早的活動(dòng)（結(jié)束時(shí)間最早意味著開(kāi)始時(shí)間也早），可以得到最優(yōu)解。按這種方法選擇，可以為未安排的活動(dòng)留下盡可能多的時(shí)間。如下圖的活動(dòng)集合S，其中各項(xiàng)活動(dòng)按照結(jié)束時(shí)間單調(diào)遞增排序。

代碼實(shí)現(xiàn)：

structcmp{

booloperator()(vectorints1,vectorints2){

returns1[1]s2[1];

intgetMaxNum(vectorvectorintevents)

sort(events.begin(),events.end(),cmp());

intnum=1;

inti=0;

for(intj=1;jevents.size();j++)

if(events[j][0]=events[i][1])

++num;

i=j;

returnnum;

}

無(wú)重疊區(qū)間

問(wèn)題描述：

給定一個(gè)區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。

注意:

可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)。

區(qū)間[1,2]和[2,3]的邊界相互“接觸”，但沒(méi)有相互重疊。

貪心策略：

法一：與上題活動(dòng)選擇類似，用總區(qū)間數(shù)減去最大可同時(shí)進(jìn)行的區(qū)間數(shù)即為結(jié)果。

法二：當(dāng)按照起點(diǎn)先后順序考慮區(qū)間時(shí)，利用一個(gè)prev指針追蹤剛剛添加到最終列表中的區(qū)間。遍歷時(shí)，可能遇到三種情況：

情況1：當(dāng)前考慮的兩個(gè)區(qū)間不重疊。這種情況下不移除任何區(qū)間，將prev賦值為后面的區(qū)間，移除區(qū)間數(shù)量不變。

情況2：兩個(gè)區(qū)間重疊，后一個(gè)區(qū)間的終點(diǎn)在前一個(gè)區(qū)間的終點(diǎn)之前。由于后一個(gè)區(qū)間的長(zhǎng)度更小，可以留下更多空間，容納更多區(qū)間，將prev更新為當(dāng)前區(qū)間，移除區(qū)間的數(shù)量+1

情況3：兩個(gè)區(qū)間重疊，后一個(gè)區(qū)間的終點(diǎn)在前一個(gè)區(qū)間的終點(diǎn)之后。直接移除后一個(gè)區(qū)間，留下更多空間。因此，prev不變，移除區(qū)間的數(shù)量+1

代碼實(shí)現(xiàn)：法一：

structcmp{

booloperator()(vectorints1,vectorints2){

returns1[1]s2[1];

classSolution{

public:

interaseOverlapIntervals(vectorvectorintintervals){

sort(intervals.begin(),intervals.end(),cmp());

intnum=1;

inti=0;

for(int