leetcode 455. Assign Cookies(python)

説明
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 g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], 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.
Example 1:

Input: g = [1,2,3], s = [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.

Example 2:

Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: 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.

Note:

1 <= g.length <= 3 * 10^4
0 <= s.length <= 3 * 10^4
1 <= g[i], s[j] <= 2^31 - 1

解析
題意によれば、ケーキサイズリストsがあり、子供が満足する最小ケーキサイズリストgは、子供一人一人に最大1つのケーキしか与えられず、その満足する最小ケーキサイズに達しなければならないので、満足できる子供が何人いるかを見つけることができる.まずgとsを並べ替えてからgとsを巡り、あるケーキが子供のケーキサイズの要求を満たすと、そのケーキを取り除き、結果に1を加えて、遍歴が終わると答えが得られます.
に答える

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        r = 0
        g.sort()
        s.sort()
        for i,v in enumerate(g):
            for j,c in enumerate(s):
                if v<=c:
                    s.pop(j)
                    r+=1
                    break
        return r

実行結果

Runtime: 1088 ms, faster than 10.12% of Python online submissions for Assign Cookies.
Memory Usage: 14.7 MB, less than 94.16% of Python online submissions for Assign Cookies.

解析
上の二重ループは時間がかかりすぎて、一重ループだけで答えを見つけることができて、iがgを表すインデックスを定義して、resは結果を表します.次にgとsをソートし、sを巡回し、gが空の場合、子供リストがない場合、結果0を直接返します.そうでなければ、現在のサイズが子供の要求を満たす場合、結果は1を加え、iも1を加えます.上記の操作を繰り返し続けると、ループが終了して結果が得られます.
に答える

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g.sort()
        s.sort()
        res = 0
        i = 0
        for e in s:
            if i == len(g):
                break
            if e >= g[i]:
                res += 1
                i += 1
        return res

実行結果

Runtime: 124 ms, faster than 98.83% of Python online submissions for Assign Cookies.
Memory Usage: 14.9 MB, less than 54.09% of Python online submissions for Assign Cookies.

原題リンク:https://leetcode.com/problems/assign-cookies/
あなたのサポートは私の最大の原動力です.