455.分发饼干(Easy)

题目描述

有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃 一个饼干，且只有饼干的大小不小于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子 可以吃饱。

样例

Input: [1,2], [1,2,3]
Output: 1

Input: [1,1], [1,1,3]
Output: 2

题解

贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。

第一步：孩子数组排序，饼干数组排序

第二步：遍历饼干，遍历结束后孩子的序号就是吃饱的数目

Python示例

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        child = 0
        for cookie in s:
            if child < len(g) and cookie >= g[child]: # child 的范围特别容易漏掉
                child += 1
        return child 

C++题解

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int child = 0, cookie = 0;
        while (child < g.size() && cookie < s.size()) {
            if (s[cookie] >= g[child]) { ++child;}
            ++cookie;
        }
        return child;
    }
};

Go 示例

func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)
    child := 0
    for i := 0; i < len(s); i++ {
        if child < len(g) && s[i] >= g[child] {
            child++
        }
    }
    return child
}