目錄
- 題目
- 自己的思路以及AC代碼
- 參考思路
題目
假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。
對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值。
提示：
自己的思路以及AC代碼
首先將數組s、g排序(按照值從小到大)，這樣就將小胃口孩子，小尺寸的餅干放在前面了。
接下來對餅干進行遍歷：
如果這個餅干大于當前的孩子胃口，把它給這個孩子，轉向下一個孩子，餅干也到下一個餅干。
如果不滿足，孩子還是當前的孩子，餅干轉到下一個餅干。
這樣就能保證每個孩子吃到的是滿足胃口的最小的尺寸餅干了。我想這也許就是貪心吧。
下面是AC代碼：
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {//將孩子按照胃口大小排序，從小到大sort(g.begin(), g.end());//將餅干按照尺寸大小排序，從小到大sort(s.begin(), s.end());int i=0;for(int j=0;j<s.size();j++){if(i<g.size() && s[j] >= g[i]) {i++;}}return i; }
};
接下來看看我參考的公眾號的思路：
參考思路
大尺寸的餅干既可以滿足胃口大的孩子也可以滿足胃口小的孩子，那么就應該優先滿足胃口大的。
局部最優：大餅干喂給胃口大的，充分利用餅干尺寸喂飽一個。
全局最優就是喂飽盡可能多的小孩。
從后向前遍歷小孩數組，用大餅干優先滿足胃口大的，并統計小孩數量。
這個思路正好和我是反過來的。
從代碼實現上來說，我的外才能循環是餅干尺寸s，而這里的代碼外層循環是胃口g。
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {//將孩子按照胃口大小排序，從小到大sort(g.begin(), g.end());//將餅干按照尺寸大小排序，從小到大sort(s.begin(), s.end());//餅干從最大的開始int j=s.size()-1;int result=0;//胃口從大到小for(int i=g.size()-1;i<g.size();i--){if(j>=0 && s[j] >= g[i]) {j--;result++;}}return result; }
};
)