LeetCode0455.AssignCookies分发饼干【易】【Python】【贪心】问题LeetCode假设你是一个很棒的父母，想给你的孩子一些饼干。但是，您最多应该给每个孩子一块饼干。每个孩子i都有一个贪婪因子gi，这是孩子会满足的最小cookie大小；每个cookiej的大小为sj。如果sj>=gi，我们可以把c??ookiej分配给孩子i，孩子i会很满意。您的目标是最大化您的内容孩子的数量并输出最大数量。注意：您可以假设贪婪因子始终为正。您不能为一个孩子分配多个cookie。示例1：输入：[1,2,3],[1,1]输出：1解释：你有3个孩子和2个饼干。3个孩子的贪婪因子是1,2,3。即使你有2个饼干，因为它们的大小都是1，你只能让贪婪因子为1的孩子满足。你需要输出1.Example2:输入：[1,2],[1,2,3]输出：2解释：你有2个孩子和3个饼干。2个孩子的贪婪因子是1、2。你有3个饼干，它们的大小足够满足所有的孩子，你需要输出2。问题是假设你是一个伟大的父母，想给你的孩子一些小饼干，但每个孩子最多只能给一块饼干。对于每个孩子i，都有一个食欲值gi，这是满足孩子食欲的最小尺寸的饼干；对于每个饼干j，都有一个大小sj。如果sj>=gi，我们可以将这个cookiej分配给孩子i并且这个孩子会满意。你的目标是让尽可能多的孩子满意，输出这个最大值。注意：您可以假设胃口值为正。一个孩子最多只能吃一块饼干。示例1：输入：[1,2,3],[1,1]输出：1解释：你有三个孩子和两块饼干，三个孩子的食欲值分别为：1,2,3。虽然你有两块小饼干，但由于它们的大小都是1，你只能满足一个胃口值为1的孩子。所以你应该输出1。例子2：输入：[1,2]，[1,2,3]输出：2解释：你有两个孩子和三个饼干，两个孩子的食欲值分别为1，2。你有足够的饼干，无论是数量还是大小，都能让所有的孩子都满意。所以你应该输出2.IdeaGreedy先把贪心指数和饼干大小从小到大排序，然后i,j指针分别指向贪心指数和饼干大小的末尾。如果贪心索引小于等于饼干大小，说明可以满足这个贪心索引，于是count加1，j指针左移一位。不管贪心索引是否满足，i指针都要向左移动，因为如果满足了，那么就可以判断下一位，如果不满足，自然就不考虑了。时间复杂度：O(max(len(g),len(s)))空间复杂度：O(1)PythoncodeclassSolution(object):deffindContentChildren(self,g,s):""":typeg:List[int]:types:List[int]:rtype:int"""#greedycnt=0g,s=sorted(g),sorted(s)#从小到大排序i,j=len(g)-1,len(s)-1#指向末尾whilemin(i,j)>=0:ifg[i]<=s[j]:#greedyindexmustbe<=biscuitsizecnt+=1j-=1i-=1#不管size是否满，i都要左移一位返回cnt代码地址GitHub链接
