分发饼干

Leetcode Link: 455. 分发饼干 - 力扣（LeetCode）

题目

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

解法一

思路：贪心就行，用两个指针分别指向胃口和饼干的位置，然后往后走

需要先排序，不排序结果不对，不然就用两个 for，时间爆炸

贪心，每一个孩子用能够满足其胃口的最小的尺寸的饼干就行，用更大的没什么必要，剩的中不溜的给谁留着呢?

题解：

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
		# 指针
        gp, sp = 0, 0
        # 结果
        cnt = 0
        while(gp < len(g) and sp < len(s)):
            if g[gp] <= s[sp]:
                cnt += 1
                gp += 1
                sp += 1
            else:
                sp += 1
        return cnt

启发和联系

排序非常关键。