本文共 3149 字，大约阅读时间需要 10 分钟。

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi , which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj . If sj >= gi , we can assign the cookie j to the child i , and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:

• You may assume the greed factor is always positive.
• You cannot assign more than one cookie to one child.

Example 1:

Input: [1,2,3], [1,1]Output: 1Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.You need to output 1.

Example 2:

Input: [1,2], [1,2,3]Output: 2Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. You have 3 cookies and their sizes are big enough to gratify all of the children, You need to output 2.

题意：给孩子们一些小饼干，每个孩子最多只能给一块饼干。每个孩子都有一个胃口指数 gi ，这是能让他满足的饼干的最小尺寸。每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。求能够得到满足的最多的孩子数量。

解法 贪心

将最大尺寸的饼干分配给胃口最大的孩子，如果能满足他的胃口就进行分配，满足的孩子数量 +1 ，然后将次大尺寸的饼干分配给胃口次大的孩子；否则将这块饼干分配给胃口次大的孩子。其他孩子则依次类推。实现的代码很简单：

class Solution {
   public:    int findContentChildren(vector
   
    & g, vector
    
     & s) {
           if (g.empty() || s.empty()) return 0;        sort(g.begin(), g.end(), greater
     
      ());        sort(s.begin(), s.end(), greater
      
       ());        int ans = 0, si = 0, gi = 0;        while (gi < g.size() && si < s.size()) {
               if (s[si] >= g[gi]) {
                   ++ans;                ++si;                ++gi;            } else ++gi;        }        return ans;    }};
      
     
    
   

执行效率如下：

执行用时：92 ms, 在所有 C++ 提交中击败了40.93% 的用户内存消耗：17.2 MB, 在所有 C++ 提交中击败了6.90% 的用户

20201225 Update 今日打卡更新，Python代码如下：

class Solution:    def findContentChildren(self, g: List[int], s: List[int]) -> int:        s.sort(reverse = True)         g.sort(reverse = True) # s,g排序        lens, leng = len(s), len(g)        ans = si = sj = 0        while si < lens and sj < leng:            if s[si] >= g[sj]: # 足够大的饼干满足了这个孩子的胃口                ans += 1 # 分给他                si += 1                sj += 1            else: # 这个孩子的胃口太大,不给他分配,将现在的饼干分给下一个                sj += 1        return ans

执行效率如下：

执行用时：56 ms, 在所有 Python3 提交中击败了95.69% 的用户内存消耗：16 MB, 在所有 Python3 提交中击败了5.24% 的用户

反过来想，这里尽量用小的饼干去满足小需求的孩子。代码如下：

class Solution {
   public:    int findContentChildren(vector
   
    & g, vector
    
     & s) {
           if (g.empty() || s.empty()) return 0;        sort(g.begin(), g.end());        sort(s.begin(), s.end());        int child = 0, cookie = 0;        while (child < g.size() && cookie < s.size()) {
    //当其中一个遍历就结束            if (s[cookie] >= g[child]) ++child;  //用当前饼干可以满足当前孩子的需求，可以满足的孩子数量+1            ++cookie;                            //不能满足时饼干太小,抛弃        }        return child;    }};
    
   

执行效率如下：

执行用时：100 ms, 在所有 C++ 提交中击败了22.80% 的用户内存消耗：17 MB, 在所有 C++ 提交中击败了49.01% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108269396 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！