63.幼儿园分饼干(贪心算法)
幼儿园分饼干(先排序,贪心算法,按饼干最小满足小朋友遍历了一下饼干数组)
题目
假设有一个饼干数组 cookies 和一个小朋友需求数组 kids,每个元素代表饼干的大小或小朋友需求的最小饼干大小。如何设计一个算法来最大化满足小朋友的数量?
提示
DETAILS
- 排序:首先对饼干数组和小朋友需求数组进行排序,以便能够从小到大依次比较。
- 双指针遍历:使用两个指针分别遍历饼干数组和小朋友需求数组。
- 满足条件:如果当前饼干能满足当前小朋友的需求,则增加满足的小朋友数量,并将小朋友指针向后移动一位。
- 继续尝试:无论当前饼干是否满足当前小朋友,饼干指针都向后移动一位,尝试下一个饼干。
- 返回结果:最终返回满足的小朋友数量。
参考答案
DETAILS
<script>
function findContentChildren(cookies, kids) {
// 先对饼干数组和小朋友需求数组进行排序
cookies.sort((a, b) => a - b);
kids.sort((a, b) => a - b);
let cookieIndex = 0; // 饼干数组的指针
let kidIndex = 0; // 小朋友数组的指针
let satisfiedKids = 0; // 满足的小朋友数量
while (cookieIndex < cookies.length && kidIndex < kids.length) {
if (cookies[cookieIndex] >= kids[kidIndex]) {
// 如果当前饼干能满足当前小朋友
satisfiedKids++;
kidIndex++; // 尝试满足下一个小朋友
}
cookieIndex++; // 尝试下一个饼干
}
return satisfiedKids;
}
// 示例使用
const cookies = [1, 2, 3];
const kids = [1, 2];
console.log(findContentChildren(cookies, kids)); // 输出: 2,两个小朋友都能被满足
</script>