分发饼干
# 📃 题目描述
题目链接:455. 分发饼干 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 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.
# 🔔 解题思路
为了满足更多的小孩,就不要造成饼干尺寸的浪费。
大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子,那么就应该优先满足胃口大的。
这里的局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩。
另外,假设有尺寸为 6 和 7 两块饼干,如果有一个胃口为 5 的小孩,我们应该给他尺寸为 6 的饼干,而不是更大的尺寸 7
可以使用贪心策略,将小孩数组和饼干数组升序排序,然后从后往前遍历小孩数组和饼干数组
二刷的时候写了一个更通俗易懂的版本,注释写的很清楚啦~:
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int res = 0;
int si = s.length - 1;
int gi = g.length - 1;
while (si >= 0 && gi >= 0) {
// 1. 当前饼干可以喂饱这个小孩
if (s[si] >= g[gi]) {
// 该饼干被消耗
si --;
// 该小孩被喂饱
gi --;
// 结果 + 1
res ++;
}
// 2. 当前饼干无法喂饱这个小孩
// 那么再往左遍历就更不能有饼干能够喂饱这个小孩了,即说明这个小孩无法被喂饱
// 用这个饼干去尝试喂饱下一个胃口更小的小孩
else {
gi --;
}
}
return res;
}
}
下面是一刷的时候写的版本:先遍历小孩数组,先把大胃口的小孩喂饱
class Solution {
public int findContentChildren(int[] g, int[] s) {
if (g == null || g.length == 0 || s == null || s.length == 0) {
return 0;
}
// 小孩数组降序排序
Arrays.sort(g);
// 饼干数组升序排序
Arrays.sort(s);
// 能够满足的小孩
int count = 0;
// 从后往前遍历小孩数组和饼干数组
for (int i = g.length - 1; i >= 0; i --) {
for (int j = s.length - 1; j >= 0; j --) {
if (s[j] >= g[i]) {
count ++;
// 表示已经被吃掉了
s[j] = 0;
break;
}
}
}
return count;
}
}
可以看出来,这个时间复杂度是 O(N^2)
事实上,我们可以优化下,用下标来控制饼干数组的遍历,而不是再起一个for循环,采用自减的方式,这也是常用的技巧,时间复杂度降到 O(N)
import java.util.Arrays;
import java.util.Collections;
class Solution {
public int findContentChildren(int[] g, int[] s) {
if (g == null || g.length == 0 || s == null || s.length == 0) {
return 0;
}
// 小孩数组降序排序
Arrays.sort(g);
// 饼干数组升序排序
Arrays.sort(s);
// 能够满足的小孩
int count = 0;
// 饼干数组的下标
int index = s.length - 1;
// 从后往前遍历小孩数组和饼干数组
for (int i = g.length - 1; i >= 0; i --) {
if (index >= 0 && s[index] >= g[i]) {
count ++;
// index-- 表示已经被吃掉了
index --;
}
}
return count;
}
}
当然了,上面的做法是大饼干先满足大胃口
我们也可以小饼干先满足小胃口,从前往后遍历,⭐ 注意这时需要先遍历饼干数组,先把小饼干喂出去
import java.util.Arrays;
import java.util.Collections;
class Solution {
public int findContentChildren(int[] g, int[] s) {
if (g == null || g.length == 0 || s == null || s.length == 0) {
return 0;
}
// 小孩数组降序排序
Arrays.sort(g);
// 饼干数组升序排序
Arrays.sort(s);
// 能够满足的小孩
int count = 0;
// 小孩数组的下标
int index = 0;
// 从前往后遍历饼干数组和小孩数组
for (int i = 0; i < s.length; i ++) {
if (index < g.length && s[i] >= g[index]) {
index ++;
count ++;
}
}
return count;
}
}
下面是我自己最开始做的时候一个想法,比较容易懂,但是其实没必要这么做
大饼干满足大胃口
从后往前遍历小孩数组(升序),假设当前遍历到的小孩胃口是 i,我们只要在饼干数组(升序)中找到第一个大于等于 i 的元素喂给这个小孩就可以了
事实上没必要在饼干数组(升序)中找到第一个大于等于 i 的元素喂给这个小孩,因为小孩数组已经升序了,假设他胃口是 6,你有 7 和 8 两个尺寸的饼干,给这个小孩哪个饼干都不重要了,因为后续的小孩的胃口不存在比 6 还大了。
import java.util.Arrays;
import java.util.Collections;
class Solution {
public int findContentChildren(int[] g, int[] s) {
if (g == null || g.length == 0 || s == null || s.length == 0) {
return 0;
}
// 小孩数组降序排序
Arrays.sort(g);
// 饼干数组升序排序
Arrays.sort(s);
// 能够满足的小孩
int count = 0;
// 从后往前遍历小孩数组,假设当前遍历到的小孩胃口是 i,我们只要在饼干数组(升序)中找到第一个大于等于 i 的元素喂给这个小孩就可
for (int i = g.length - 1; i >= 0; i --) {
for (int j = 0; j < s.length; j ++) {
if (s[j] >= g[i]) {
// 将这个位置的饼干置为 0,表示已经被吃掉了
s[j] = 0;
count ++;
break;
}
}
}
return count;
}
}
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~