贪心策略、分配问题

题目

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

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

示例1：

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例2：

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

提示：

$1 <= g.length <= 3 * 10^4$

$0 <= s.length <= 3 * 10^4$

$1 <= g[i], s[j] <= 2^{31} - 1$

题解

贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。
至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。
这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对子可以满足条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findContentChildren(self, g, s) -> int:
        new_g=sorted(g)
        new_s=sorted(s)
        i=0
        j=0
        sum=0
        
        while True:
            if j<len(new_s) and i<len(new_g):
                if new_s[j]>=new_g[i]:
                    sum+=1
                    j = j+1
                    i = i+1
                else:
                    j=j+1
            else:
                break
            
        return sum
1
2
3
4
g=[10,9,8,7]
s=[5,6,7,8]
a=Solution()
a.findContentChildren(g,s)
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def findContentChildren(self, g, s) -> int:
        new_g=sorted(g)
        new_s=sorted(s)
        ng = len(new_g)
        ns = len(new_s)
        
        i=j = 0
        sum=0
        
        while i<ng and j<ns:
            while j<ns and new_g[i]>new_s[j]:
                j =j+1
            if j < ns:
                sum += 1
            i += 1
            j += 1
        return sum
1
2
3
4
g=[10,9,8,7]
s=[5,6,7,8]
a=Solution()
a.findContentChildren(g,s)
2

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://fishni.github.io/2020/12/29/LeetCode-D-%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95-455.%20%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2/