广州市建设工程安监站网站,福州建设项目管理公司,上海正规网站建设怎么样,我想承包小工程从0开始的秋招刷题路#xff0c;记录下所刷每道题的题解#xff0c;帮助自己回顾总结
455. 分发饼干
假设你是一位很棒的家长#xff0c;想要给你的孩子们一些小饼干。但是#xff0c;每个孩子最多只能给一块饼干。
对每个孩子 i#xff0c;都有一个胃口值 g[i]#x…从0开始的秋招刷题路记录下所刷每道题的题解帮助自己回顾总结
455. 分发饼干
假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。
对每个孩子 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.
提示 1 g.length 3 ∗ 1 0 4 3 * 10^4 3∗104 0 s.length 3 ∗ 1 0 4 3 * 10^4 3∗104 1 g[i], s[j] 2 31 − 1 2^{31} - 1 231−1
题目解析 这道分发饼干是典型的用贪心算法解题难度简单很适合的入门题。
这道题你看着题意这么多其实可以抽象成从 n 个孩子中抽出一部分孩子给他们饼干吃让满足孩子的个数是最大的。
这个如何用贪心解决呢
很简单其实你可以这么想因为要求满足孩子的个数是最大的那对于一个孩子来说如果小尺寸的饼干可以满足就没必要用大尺寸的饼干这样我们就可以把相对大尺寸的饼干留给胃口更大的孩子。
小尺寸的饼干能满足小胃口的孩子满足不了大胃口的孩子大尺寸的饼干能满足大胃口的孩子也能满足小胃口的孩子因为对于我们来说满足一个胃口小的孩子和满足一个胃口大的孩子的期望值是一样的那就应该小尺寸的饼干用来满足小胃口的孩子大尺寸的饼干来满足大胃口的孩子。
这就套路就成了我们每次从剩下的孩子中找出胃口最小的孩子给他能满足他胃口的最小尺寸饼干即可这样我们得到的分配方案是满足孩子的个数最大的。
代码实现
class Solution {public int findContentChildren(int[] g, int[] s) {// 将胃口和饼干排序Arrays.sort(g);Arrays.sort(s);// 孩子的数量int n g.length;// 饼干的数量int m s.length;// 记录结果int res 0;for(int i 0; i m; i){// 从胃口小的开始喂if(res n g[res] s[i]){res 1;}}return res;}
}
