貪心的第一道題目,快看看你夠不夠貪心
455.分發(fā)餅干
力扣題目鏈接:https://leetcode-cn.com/problems/assign-cookies
假設(shè)你是一位很棒的家長,想要給你的孩子們一些小餅干。但是,每個(gè)孩子最多只能給一塊餅干。
對每個(gè)孩子 i,都有一個(gè)胃口值 g[i],這是能讓孩子們滿足胃口的餅干的最小尺寸;并且每塊餅干 j,都有一個(gè)尺寸 s[j]。如果 s[j]>= g[i],我們可以將這個(gè)餅干 j 分配給孩子 i ,這個(gè)孩子會得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子,并輸出這個(gè)最大數(shù)值。
示例1:
- 輸入: g = [1,2,3], s = [1,1]
- 輸出: 1 解釋:你有三個(gè)孩子和兩塊小餅干,3個(gè)孩子的胃口值分別是:1,2,3。雖然你有兩塊小餅干,由于他們的尺寸都是1,你只能讓胃口值是1的孩子滿足。所以你應(yīng)該輸出1。
示例2:
- 輸入: g = [1,2], s = [1,2,3]
- 輸出: 2
- 解釋:你有兩個(gè)孩子和三塊小餅干,2個(gè)孩子的胃口值分別是1,2。你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。所以你應(yīng)該輸出2.
提示:
- 1 <= g.length <= 3 * 10^4
- 0 <= s.length <= 3 * 10^4
- 1 <= g[i], s[j] <=?2^31 - 1
思路
為了了滿足更多的小孩,就不要造成餅干尺寸的浪費(fèi)。
大尺寸的餅干既可以滿足胃口大的孩子也可以滿足胃口小的孩子,那么就應(yīng)該優(yōu)先滿足胃口大的。
這里的局部最優(yōu)就是大餅干喂給胃口大的,充分利用餅干尺寸喂飽一個(gè),全局最優(yōu)就是喂飽盡可能多的小孩。
可以嘗試使用貪心策略,先將餅干數(shù)組和小孩數(shù)組排序。
然后從后向前遍歷小孩數(shù)組,用大餅干優(yōu)先滿足胃口大的,并統(tǒng)計(jì)滿足小孩數(shù)量。
如圖:
455.分發(fā)餅干這個(gè)例子可以看出餅干9只有喂給胃口為7的小孩,這樣才是整體最優(yōu)解,并想不出反例,那么就可以擼代碼了。
C++代碼整體如下:
//時(shí)間復(fù)雜度:O(nlogn)
//空間復(fù)雜度:O(1)
classSolution{
public:
intfindContentChildren(vector<int>&g,vector<int>&s){
sort(g.begin(),g.end());
sort(s.begin(),s.end());
intindex=s.size()-1;//餅干數(shù)組的下表
intresult=0;
for(inti=g.size()-1;i>=0;i--){
if(index>=0&&s[index]>=g[i]){
result++;
index--;
}
}
returnresult;
}
};
從代碼中可以看出我用了一個(gè)index來控制餅干數(shù)組的遍歷,遍歷餅干并沒有再起一個(gè)for循環(huán),而是采用自減的方式,這也是常用的技巧。
有的同學(xué)看到要遍歷兩個(gè)數(shù)組,就想到用兩個(gè)for循環(huán),那樣邏輯其實(shí)就復(fù)雜了。
也可以換一個(gè)思路,小餅干先喂飽小胃口
代碼如下:
classSolution{
public:
intfindContentChildren(vector<int>&g,vector<int>&s){
sort(g.begin(),g.end());
sort(s.begin(),s.end());
intindex=0;
for(inti=0;iif(indexreturnindex;
}
};
總結(jié)
這道題是貪心很好的一道入門題目,思路還是比較容易想到的。
文中詳細(xì)介紹了思考的過程,想清楚局部最優(yōu),想清楚全局最優(yōu),感覺局部最優(yōu)是可以推出全局最優(yōu),并想不出反例,那么就試一試貪心。
其他語言版本
Java
classSolution{
//思路1:優(yōu)先考慮餅干,小餅干先喂飽小胃口
publicintfindContentChildren(int[]g,int[]s){
Arrays.sort(g);
Arrays.sort(s);
intstart=0;
intcount=0;
for(inti=0;iif(s[i]>=g[start]){
start++;
count++;
}
}
returncount;
}
}
classSolution{
//思路2:優(yōu)先考慮胃口,先喂飽大胃口
publicintfindContentChildren(int[]g,int[]s){
Arrays.sort(g);
Arrays.sort(s);
intcount=0;
intstart=s.length-1;
//遍歷胃口
for(intindex=g.length-1;index>=0;index--){
if(start>=0&&g[index]<=?s[start])?{
????????????????start--;
????????????????count++;
????????????}
????????}
????????returncount;
}
}
Python
class Solution:
# 思路1:優(yōu)先考慮胃餅干
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
res = 0
for i in range(len(s)):
if res = g[res]: #小餅干先喂飽小胃口
res += 1
return res
classSolution:
#思路2:優(yōu)先考慮胃口
deffindContentChildren(self,g:List[int],s:List[int])->int:
g.sort()
s.sort()
start,count=len(s)-1,0
forindexinrange(len(g)-1,-1,-1):#先喂飽大胃口
ifstart>=0andg[index]<=?s[start]:
????????????????start?-=?1
count+=1
returncount
Go
//排序后,局部最優(yōu)
funcfindContentChildren(g[]int,s[]int)int{
sort.Ints(g)
sort.Ints(s)
//從小到大
child:=0
forsIdx:=0;childlen(g)&&sIdxlen(s);sIdx++{
ifs[sIdx]>=g[child]{//如果餅干的大小大于或等于孩子的為空則給與,否則不給予,繼續(xù)尋找選一個(gè)餅干是否符合
child++
}
}
returnchild
}
審核編輯 :李倩
-
算法
+關(guān)注
關(guān)注
23文章
4552瀏覽量
92019 -
數(shù)組
+關(guān)注
關(guān)注
1文章
411瀏覽量
25821
原文標(biāo)題:分發(fā)餅干,也要貪心
文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論