假设你是一位很棒(多棒???)的家长,想要给你的孩子们一些小饼干(不能给大饼干吗???)但是,每个孩子最多只能给一块饼干(有毒吧。。。)
对每个孩子 i ,都有一个胃口值 gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
注意:你可以假设胃口值为正(特么不正难道往外吐吗???)。一个小朋友最多只能拥有一块饼干。
示例 :
输入: [1,2,3], [1,1]
输出: 1
解释: 你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。所以你应该输出1。
(难道剩下一个饼干喂狗吗?????)
好吧。假如我们按照题目所说的策略来分析,尽可能的让孩纸满足,满足不了就一个饼干都不给他,忘掉那些懵逼的孩子。
其实策略就很简单了:我们只需要在满足孩子胃口的前提下,尽可能分配小的饼干给到他。典型的资本主义。
具体怎么做呢,我们把饼干和小朋友都按照从大到小排列。
但是这里有个问题。凭什么就要先满足肚子最大的孩子。按道理讲,肚子越大应该越扛饿才对吧。所以我们换种思路,从肚子最小的孩子开始。
那这两种其实都算是贪心:
因为要同时控制饼干和小孩,所以我们采用双指针。这里给出先满足小肚子孩子的代码:
1class Solution {
2 public int findContentChildren(int[] grid, int[] size) {
3 if (grid == null || size == null) return 0;
4 Arrays.sort(grid);
5 Arrays.sort(size);
6 int gi = 0, si = 0;
7 while (gi < grid.length && si < size.length) {
8 if (grid[gi] <= size[si]) {
9 gi++;
10 }
11 si++;
12 }
13 return gi;
14 }
15}
如果想先满足大肚子,代码也大同小异。直接从尾部向前遍历即可。