455. Assign Cookies (Easy)

简介: 455. Assign Cookies (Easy)

455. Assign Cookies (Easy)


题目描述


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


输入输出样例


输入两个数组,分别代表孩子的饥饿度和饼干的大小。输出最多有多少孩子可以吃饱的数量。


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


在这个样例中,我们可以给两个孩子喂 [1,2]、[1,3]、[2,3] 这三种组合的任意一种。


题解


因为饥饿度最小的孩子最容易吃饱,所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子,所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后,我们采取同样的策略,考虑剩下孩子里饥饿度最小的孩子,直到没有满足条件的饼干存在。


简而言之,这里的贪心策略是,给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。


至于具体实现,因为我们需要获得大小关系,一个便捷的方法就是把孩子和饼干分别排序。


这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发,计算有多少个对子可以满足条件。


注意


  • 对数组或字符串排序是常见的操作,方便之后的大小比较。



  • 在之后的讲解中,若我们谈论的是对连续空间的变量进行操作,我们并不会明确区分数组和字符串,因为他们本质上都是在连续空间上的有序变量集合。一个字符串“abc”可以被看作一个数组 [‘a’,‘b’,‘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())
        {
            // 如果当前胃口最小的孩子 小于等于最小尺寸的饼干  child++  变成下一个孩子
            // 如果当前胃口最小的孩子 大于 最小尺寸的饼干 孩子不+1  饼干+1
            if(g[child]<= s[cookie])
                child++;
            cookie++;
        }
        return child;
    }
};
相关文章
|
7月前
Request Headers 中的 Accept 是 text/event-stream
Request Headers 中的 Accept 是 text/event-stream
762 0
|
5月前
|
CTfshow 卷王杯 easy unserialize(特详)
CTfshow 卷王杯 easy unserialize(特详)
83 0
|
5月前
|
Could not fetch/save url https://download.docker.com/linux/centos/docker-ce.repo
CentOS 安装Docker时,将 Docker 官方的 YUM 存储库添加到 CentOS 系统中出现错误。
864 0
Could not fetch/save url http://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repoError 403
Could not fetch/save url http://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repoError 403
1764 1
curl: symbol lookup error: curl: undefined symbol: curl_mime_free
curl: symbol lookup error: curl: undefined symbol: curl_mime_free
351 0
axios.post请求出错:Request header field content-type is not allowed by Access-Control-Allow-Headers in……
axios.post请求出错:Request header field content-type is not allowed by Access-Control-Allow-Headers in……
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等