力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
面试题 17.12. BiNode
0001. 两数之和
0020. 有效的括号
0021. 合并两个有序链表
0026. 删除排序数组中的重复项
0053. 最大子序和
0160. 相交链表
0066. 加一
0088. 合并两个有序数组
0101. 对称二叉树
0104. 二叉树的最大深度
0108. 将有序数组转换为二叉搜索树
0121. 买卖股票的最佳时机
0122. 买卖股票的最佳时机 II
0125. 验证回文串
0136. 只出现一次的数字
0155. 最小栈
0167. 两数之和 II 输入有序数组
0169. 多数元素
0172. 阶乘后的零
0190. 颠倒二进制位
0191. 位 1 的个数
0198. 打家劫舍
0203. 移除链表元素
0206. 反转链表
0219. 存在重复元素 II
0226. 翻转二叉树
0232. 用栈实现队列
0263. 丑数
0283. 移动零
0342. 4 的幂
0349. 两个数组的交集
0371. 两整数之和
401. 二进制手表
0437. 路径总和 III
0455. 分发饼干
0504. 七进制数
0575. 分糖果
0665. 非递减数列
0661. 图片平滑器
821. 字符的最短距离
0874. 模拟行走机器人
1128. 等价多米诺骨牌对的数量
1260. 二维网格迁移
1332. 删除回文子序列
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
后序
由
GitBook
提供支持
0455. 分发饼干
题目地址(455. 分发饼干)
https://leetcode-cn.com/problems/assign-cookies/
题目描述
1
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i ,都有一个胃口值 gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
2
3
注意:
4
5
你可以假设胃口值为正。
6
一个小朋友最多只能拥有一块饼干。
7
8
示例 1:
9
10
输入: [1,2,3], [1,1]
11
12
输出: 1
13
14
解释:
15
16
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
17
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
18
所以你应该输出1。
19
20
示例 2:
21
22
输入: [1,2], [1,2,3]
23
24
输出: 2
25
26
解释:
27
28
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
29
你拥有的饼干数量和尺寸都足以让所有孩子满足。
30
所以你应该输出2.
Copied!
前置知识
贪心算法
双指针
公司
阿里
腾讯
字节
思路
本题可用贪心求解。给一个孩子的饼干应当尽量小并且能满足孩子,大的留来满足胃口大的孩子。因为胃口小的孩子最容易得到满足,所以优先满足胃口小的孩子需求。按照从小到大的顺序使用饼干尝试是否可满足某个孩子。
算法:
将需求因子 g 和 s 分别从小到大进行排序
使用贪心思想,配合两个指针,每个饼干只尝试一次,成功则换下一个孩子来尝试,不成功则换下一个饼干🍪来尝试。
关键点
先排序再贪心
代码
语言支持:JS, Python
JS Code:
1
/**
2
* @param {number[]} g
3
* @param {number[]} s
4
* @return {number}
5
*/
6
const findContentChildren = function (g, s) {
7
g = g.sort((a, b) => a - b);
8
s = s.sort((a, b) => a - b);
9
let gi = 0; // 胃口值
10
let sj = 0; // 饼干尺寸
11
let res = 0;
12
while (gi < g.length && sj < s.length) {
13
// 当饼干 sj >= 胃口 gi 时,饼干满足胃口,更新满足的孩子数并移动指针
14
if (s[sj] >= g[gi]) {
15
gi++;
16
sj++;
17
res++;
18
} else {
19
// 当饼干 sj < 胃口 gi 时,饼干不能满足胃口,需要换大的
20
sj++;
21
}
22
}
23
return res;
24
};
Copied!
Python Code:
1
class
Solution
:
2
def
findContentChildren
(
self
,
g
:
List
[
int
],
s
:
List
[
int
])
->
int
:
3
g
.
sort
()
4
s
.
sort
()
5
count
=
gIdx
=
sIdx
=
0
6
while
gIdx
<
len
(
g
)
and
sIdx
<
len
(
s
):
7
if
s
[
sIdx
]
>=
g
[
gIdx
]:
8
gIdx
+=
1
9
count
+=
1
10
sIdx
+=
1
11
return
count
Copied!
复杂度分析
时间复杂度:由于使用了排序,因此时间复杂度为 O(NlogN)
空间复杂度:O(1)
更多题解可以访问我的LeetCode题解仓库:https://github.com/azl397985856/leetcode 。 目前已经37K star啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。
以前
0437. 路径总和 III
下一个
0504. 七进制数
最近更新
5mo ago
复制链接
内容
题目地址(455. 分发饼干)
题目描述
前置知识
公司
思路
关键点
代码