分发饼干( LeetCode 455 )
一、题目描述
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干j 分配给孩子i,这个孩子会得到满足。
你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 分发饼干( LeetCode 455 ):https://leetcode-cn.com/problems/assign-cookies/
class Solution {
public int findContentChildren(int[] g, int[] s) {
// 1、将孩子们的胃口值按照从小到大的顺序排列
// 优先满足胃口小的孩子
Arrays.sort(g);
// 2、将饼干按照从小到大的顺序排列
Arrays.sort(s);
// child 代表 g 的下标,即表示有多少孩子的胃口得到满足
int child = 0;
// child 代表 s 的下标,即表示目前有多少饼干被使用了
int cookie = 0;
// 遍历所有的饼干
// 遍历过后,饼干只有两种状态
// 1、要么找到了需要这个饼干的孩子
// 2、要么剩下的孩子中,胃口值最低的孩子都大于这个饼干的值,那么这个饼干没人要
while(cookie < s.length && child < g.length){
// 孩子的胃口得到了满足
if(s[cookie] >= g[child]){
// 得到满足的孩子数量加 1
child++;
}
// 查看下一个饼干能否找到需要的孩子
cookie++;
}
// 最后返回孩子数量
return child;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 分发饼干( LeetCode 455 ):https://leetcode-cn.com/problems/assign-cookies/
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
// 1、将孩子们的胃口值按照从小到大的顺序排列
// 优先满足胃口小的孩子
sort(g.begin(), g.end());
// 2、将饼干按照从小到大的顺序排列
sort(s.begin(), s.end());
// child 代表 g 的下标,即表示有多少孩子的胃口得到满足
int child = 0;
// child 代表 s 的下标,即表示目前有多少饼干被使用了
int cookie = 0;
// 遍历所有的饼干
// 遍历过后,饼干只有两种状态
// 1、要么找到了需要这个饼干的孩子
// 2、要么剩下的孩子中,胃口值最低的孩子都大于这个饼干的值,那么这个饼干没人要
while(cookie < s.size() && child < g.size()){
// 孩子的胃口得到了满足
if(s[cookie] >= g[child]){
// 得到满足的孩子数量加 1
child++;
}
// 查看下一个饼干能否找到需要的孩子
cookie++;
}
// 最后返回孩子数量
return child;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 分发饼干( LeetCode 455 ):https:#leetcode-cn.com/problems/assign-cookies/
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
# 1、将孩子们的胃口值按照从小到大的顺序排列
# 优先满足胃口小的孩子
g.sort()
# 2、将饼干按照从小到大的顺序排列
s.sort()
# child 代表 g 的下标,即表示有多少孩子的胃口得到满足
child = 0
# child 代表 s 的下标,即表示目前有多少饼干被使用了
cookie = 0
# 遍历所有的饼干
# 遍历过后,饼干只有两种状态
# 1、要么找到了需要这个饼干的孩子
# 2、要么剩下的孩子中,胃口值最低的孩子都大于这个饼干的值,那么这个饼干没人要
while cookie < len(s) and child < len(g) :
# 孩子的胃口得到了满足
if s[cookie] >= g[child] :
# 得到满足的孩子数量加 1
child += 1
# 查看下一个饼干能否找到需要的孩子
cookie += 1
# 最后返回孩子数量
return child