455. Assign Cookies 贪心算法

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.

Input: [1,2,3], [1,1]

Output: 1

Explanation: 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.

让我们使用贪心算法来解决它!贪心算法的核心思想是 坚持当下的最好选择 。那么在这道题中, 当下的最好选择 是什么?答案是,先将“较小的饼干”分给“对饼干尺寸要求最小”、“最好说话”的孩子,因为他们最容易满足,这样才能最大化满足孩子的数量。那么,整个分配流程就应该是这样的:

首先,将孩子们按“对饼干尺寸要求最小”排序,将饼干按尺寸大小排序。
然后,判断第一块饼干是否能满足第一个孩子,能就分给他,否则就换个稍微大点的,直到满足这个孩子。
满足第一个孩子后,再对第二个、第三个以及后面的孩子重复上面一步,直到饼干分完为止。
最后统计满足了多少个孩子,并返回结果。

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        if not g or not s :
            return 0
        g = sorted(g)
        s = sorted(s)
        gi = 0
        si = 0
        while gi < len(g) and si < len(s):
            if g[gi]<=s[si]:
                gi+=1
            si+=1
        return gi

请多多指教。

文章标题:455. Assign Cookies 贪心算法

本文作者:顺强

发布时间:2019-12-11, 23:59:00

原始链接:http://shunqiang.ml/leetcode-455-assign-cookies/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏