天天一道算法题——分发饼干

发布时间:2022-05-11 00:42 阅读次数:
本文摘要:题目假设你是一位很棒的家长,想要给你的孩子们一些小饼干。可是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;而且每块饼干 j,都有一个尺寸 s[j]。如果 s[j] = g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会获得满足。你的目的是尽可能满足越多数量的孩子,并输出这个最大数值。

威尼斯网址下载

题目假设你是一位很棒的家长,想要给你的孩子们一些小饼干。可是,每个孩子最多只能给一块饼干。

对每个孩子 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.思路首先想到了贪心算法,让尽可能大的饼干满足胃口更大的孩子,为了利便获取最大的饼干和胃口最大的孩子,则需要将2个数组举行排序。代码/** * @param {number[]} g * @param {number[]} s * @return {number} */var findContentChildren = function(g, s) { // 划分将2个数组举行排序 g = g.sort((a,b) => a - b) s = s.sort((a,b) => a - b) let i = g.length - 1 let j = s.length - 1 let sum = 0 // 分到饼干的孩子数量 // 循环终止条件是没有孩子可以分了或者没有饼干可以分了 while(j >= 0 && i >= 0) { // 如果最大的饼干可以满足胃口最大的孩子,则分发 if(s[j] >= g[i]) { j-- i-- sum++ // 否则寻找下一个胃口更小一点的孩子分饼干 } else { i-- } } return sum};。


本文关键词:天天,威尼斯网址下载,一道,算法,题,—,分发,饼干,题目,假设

本文来源:威尼斯官方网址下载-www.jlsztz.com

在线客服 联系方式 二维码

电话

012-22209630

扫一扫,关注我们