一起學算法-455.分發(fā)餅干

一、題目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)解晌柬。

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末姥份,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子年碘,更是在濱河造成了極大的恐慌澈歉,老刑警劉巖,帶你破解...
    沈念sama閱讀 210,914評論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件屿衅,死亡現(xiàn)場離奇詭異埃难,居然都是意外死亡,警方通過查閱死者的電腦和手機傲诵,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 89,935評論 2 383
  • 文/潘曉璐 我一進店門凯砍,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人拴竹,你說我怎么就攤上這事悟衩。” “怎么了栓拜?”我有些...
    開封第一講書人閱讀 156,531評論 0 345
  • 文/不壞的土叔 我叫張陵座泳,是天一觀的道長。 經(jīng)常有香客問我幕与,道長挑势,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,309評論 1 282
  • 正文 為了忘掉前任啦鸣,我火速辦了婚禮潮饱,結果婚禮上,老公的妹妹穿的比我還像新娘诫给。我一直安慰自己香拉,他們只是感情好,可當我...
    茶點故事閱讀 65,381評論 5 384
  • 文/花漫 我一把揭開白布中狂。 她就那樣靜靜地躺著凫碌,像睡著了一般。 火紅的嫁衣襯著肌膚如雪胃榕。 梳的紋絲不亂的頭發(fā)上盛险,一...
    開封第一講書人閱讀 49,730評論 1 289
  • 那天,我揣著相機與錄音勋又,去河邊找鬼苦掘。 笑死,一個胖子當著我的面吹牛楔壤,可吹牛的內容都是我干的鹤啡。 我是一名探鬼主播,決...
    沈念sama閱讀 38,882評論 3 404
  • 文/蒼蘭香墨 我猛地睜開眼挺邀,長吁一口氣:“原來是場噩夢啊……” “哼揉忘!你這毒婦竟也來了?” 一聲冷哼從身側響起端铛,我...
    開封第一講書人閱讀 37,643評論 0 266
  • 序言:老撾萬榮一對情侶失蹤泣矛,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后禾蚕,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體您朽,經(jīng)...
    沈念sama閱讀 44,095評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 36,448評論 2 325
  • 正文 我和宋清朗相戀三年换淆,在試婚紗的時候發(fā)現(xiàn)自己被綠了哗总。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,566評論 1 339
  • 序言:一個原本活蹦亂跳的男人離奇死亡倍试,死狀恐怖讯屈,靈堂內的尸體忽然破棺而出,到底是詐尸還是另有隱情县习,我是刑警寧澤涮母,帶...
    沈念sama閱讀 34,253評論 4 328
  • 正文 年R本政府宣布,位于F島的核電站躁愿,受9級特大地震影響叛本,放射性物質發(fā)生泄漏。R本人自食惡果不足惜彤钟,卻給世界環(huán)境...
    茶點故事閱讀 39,829評論 3 312
  • 文/蒙蒙 一来候、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧逸雹,春花似錦营搅、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,715評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至辫樱,卻和暖如春峭拘,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背狮暑。 一陣腳步聲響...
    開封第一講書人閱讀 31,945評論 1 264
  • 我被黑心中介騙來泰國打工鸡挠, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人搬男。 一個月前我還...
    沈念sama閱讀 46,248評論 2 360
  • 正文 我出身青樓拣展,卻偏偏與公主長得像,于是被迫代替她去往敵國和親缔逛。 傳聞我的和親對象是個殘疾皇子备埃,可洞房花燭夜當晚...
    茶點故事閱讀 43,440評論 2 348

推薦閱讀更多精彩內容

  • 題目描述 假設你是一位很棒的家長姓惑,想要給你的孩子們一些小餅干。但是按脚,每個孩子最多只能給一塊餅干于毙。 對每個孩子 i,...
    珺王不早朝閱讀 159評論 0 0
  • 假設你是一位很棒的家長辅搬,想要給你的孩子們一些小餅干唯沮。但是,每個孩子最多只能給一塊餅干堪遂。 對每個孩子 i介蛉,都有一個胃...
    阿里猴閱讀 330評論 0 0
  • 題目: 假設你是一位很棒的家長,想要給你的孩子們一些小餅干溶褪。但是币旧,每個孩子最多只能給一塊餅干。對每個孩子 i 猿妈,都...
    唧唧復唧唧丨閱讀 69評論 0 0
  • 假設你是一位很棒的家長于游,想要給你的孩子們一些小餅干毁葱。但是,每個孩子最多只能給一塊餅干贰剥。對每個孩子 i 倾剿,都有一個胃...
    上行彩虹人閱讀 111評論 0 0
  • 今天感恩節(jié)哎,感謝一直在我身邊的親朋好友蚌成。感恩相遇前痘!感恩不離不棄。 中午開了第一次的黨會担忧,身份的轉變要...
    迷月閃星情閱讀 10,556評論 0 11