分饼干
程序员文章站
2022-06-22 23:50:38
...
LeetCode每日一题(12.25日)
Merry Christmas : D
给你的孩子们一些小饼干。每个孩子最多只能给一块饼干。
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。目标是尽可能满足多数量的孩子,并输出最大数值。
示例:g=[1,2,3] s=[1,1]→1
explain: 三个孩子胃口分别为1,2,3,只有两块小饼干尺寸为1. 则最多只能满足胃口为1的小孩,所以返回1.
链接:https://leetcode-cn.com/problems/assign-cookies
要满足尽可能多的小孩,则考虑贪心算法。找局部最优解,找满足当前胃口的最小尺寸饼干。
所以先从小到大排序,在依次遍历。
对每一个小孩找到它的最小尺寸饼干,选到以后,这块饼干取出。
def findContentChildren(self, g, s) -> int:
g.sort()
s.sort()
i=0;j=0;n=0
gn=len(g);sn=len(s)
while i<gn and j<sn:
while j<sn and s[j]<g[i]:
j+=1
if j<sn :
n+=1
i+=1
j+=1
return n