一、題目455. 分發(fā)餅干
LeetCode地址:https://leetcode-cn.com/problems/assign-cookies/
難度:簡單
假設你是一位很棒的家長,想要給你的孩子們一些小餅干周伦。但是绪妹,每個孩子最多只能給一塊餅干利凑。
對每個孩子 i
励七,都有一個胃口值 g[i]
拇舀,這是能讓孩子們滿足胃口的餅干的最小尺寸;并且每塊餅干 j
匕坯,都有一個尺寸 s[j]
束昵。如果 s[j] >= g[i]
,我們可以將這個餅干 j
分配給孩子 i
葛峻,這個孩子會得到滿足锹雏。你的目標是盡可能滿足越多數(shù)量的孩子,并輸出這個最大數(shù)值术奖。
示例 1:
輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋:
你有三個孩子和兩塊小餅干礁遵,3個孩子的胃口值分別是:1,2,3。
雖然你有兩塊小餅干采记,由于他們的尺寸都是1佣耐,你只能讓胃口值是1的孩子滿足。
所以你應該輸出1唧龄。
二兼砖、解題思路
因為饑餓度最小的孩子最容易吃飽,所以我們先考慮這個孩子既棺。為了盡量使得剩下的餅干可
以滿足饑餓度更大的孩子讽挟,所以我們應該把能夠剛好滿足這個孩子的餅干(大于等于這個孩子饑餓度的、且大小最性啤)給他戏挡。滿足了這個孩子之后,我們采取同樣的策略晨仑,考慮剩下孩子里饑餓度最小的孩子褐墅,直到?jīng)]有滿足條件的餅干存在。
簡而言之洪己,再盡可能滿足孩子的情況下分配餅干妥凳。這個就是貪心算法的策略,保證每次操作都是局部最優(yōu)的答捕,從而使最后得到的結果是全局最優(yōu)的逝钥。
我這里給出了兩種編程語言的實現(xiàn)過程
c++實現(xiàn)
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int child = 0, cookie = 0;
while (child < g.size() && cookie < s.size()) {
if (g[child] <= s[cookie]) ++child;
++cookie;
}
return child;
}
};
PHP實現(xiàn)
class Solution {
/**
* @param Integer[] $g
* @param Integer[] $s
* @return Integer
*/
function findContentChildren($g, $s) {
sort($g);
sort($s);
$child = $cookie = 0;
while($child < count($g) && $cookie < count($s) ){
if($g[$child] <= $s[$cookie]){
++$child;
}
++$cookie;
}
return $child;
}
}
三、小結
貪心算法沒有什么固定的框架拱镐,只要實現(xiàn)局部最優(yōu)的艘款,進而使最后得到的結果是全局最優(yōu)的。貪心算法的全局最優(yōu)是有條件的沃琅,是建立在局部最優(yōu)的操作對下一步操作沒有影響的基礎上的哗咆。
貪心算法與動態(tài)規(guī)劃算法相比,貪心算法算法復雜度較低益眉。貪心算法可以得到全局最優(yōu)的近似解在一定程度上可以代替最優(yōu)解晌柬。