如何用leetcode分发饼干

<详细解答>

问题背景:

假设你是一个老师，班级里有n个孩子，每个孩子有一个满意度值g[i]。你有m个饼干，饼干的大小分别为s[j]。现在你想按照以下规则给孩子分发饼干：

（1）每个孩子最多只能分到一块饼干。

（2）满意度值高的孩子会优先分到饼干，满意度值相同的孩子，饼干尺寸大的会优先分到。

请问你最多能满足多少个孩子的需求？

贪心算法解法

贪心算法适用于问题的最优解可以通过局部最优决策得到的情况。对于分发饼干的问题，我们可以通过贪心算法来找到局部最优解。

1. 首先，对孩子的满意度值g和饼干的尺寸s分别进行排序，确保满意度值高的孩子和尺寸大的饼干排在前面。

2. 使用两个指针i和j分别指向孩子和饼干的数组。

3. 当满意度值g[i] <= 饼干尺寸s[j]时，说明可以满足当前孩子的需求，将结果+1，同时i和j分别向后移动一位。

4. 否则，说明当前饼干尺寸无法满足孩子的需求，将j向后移动一位。

5. 重复步骤3和4，直到两个数组遍历完。

具体实现

下面是用Python实现贪心算法解决分发饼干问题的代码示例：

def findContentChildren(g, s):
    g.sort()   # 排序孩子的满意度值
    s.sort()   # 排序饼干的尺寸
    satisfied = 0   # 记录满足的孩子数量
    i, j = 0, 0
    while i < len(g) and j < len(s):
        if g[i] <= s[j]:
            satisfied += 1
            i += 1
        j += 1
    return satisfied

同时，我们可以用测试数据来验证算法的正确性：

g = [1,2,3]
s = [1,1]
print(findContentChildren(g, s))   # 输出 1

在上述测试数据中，有3个孩子和2块饼干，第一个孩子的满意度为1，第一个饼干的尺寸也为1，因此只能满足一个孩子的需求。