leetcode with python: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 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.

给定两个阵列,一个表示各饼乾的分量(s),一个表示各孩童的食量(g)
一个孩童最多只能拿一个饼乾,算出这些饼乾最多能餵饱几个孩童

这题我採用双指标的作法

class Solution:    def findContentChildren(self, g: List[int], s: List[int]) -> int:        g=sorted(g)        s=sorted(s)                i=0        j=0        while i<len(g) and j<len(s):            if g[i]<=s[j]:                i=i+1            j=j+1                        return i

先将两个阵列进行排序
将份量小的饼乾优先和食量小的孩童配对
才能达成分配饼乾的最大效益

设好两个指标(i,j),i在孩童食量阵列,j在饼乾份量阵列
若当前的饼乾能餵饱当前的孩童(g[i]<=s[j])
i,j都+1去找下一个孩童跟下一个饼乾配对

反之若饼乾餵不饱孩童
j+1往下去找下一个更大的饼乾好餵饱这个孩童

如此持续到孩童都被餵饱或饼乾都被用完
此时的i刚好表示餵饱的孩童的数量
最后执行时间166ms(faster than 96.87%)

今天也先更一题就好

那我们下题见