贪心算法-leetcode：455.分发饼干

曾经终败给现在 2024-03-29 16:23 16阅读 0赞

### 问题描述 ###

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

对每个孩子 i，都有一个胃口值 g\[i\]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s\[j\] 。如果 s\[j\] >= g\[i\]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 :

*  输入: g = \[1,2,3\], s = \[1,1\]

*  输出: 1 解释:你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。

### **思路** ###

为了满足更多的小孩，就不要造成饼干尺寸的浪费。

大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。

**这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩**。

可以尝试使用贪心策略，先将饼干数组和小孩数组排序。

然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

#### **注意事项** ####

注意版本一的代码中，可以看出来，是先遍历的胃口，再遍历的饼干，那么可不可以 先遍历 饼干，在遍历胃口呢？

其实是不可以的。

外面的for 是里的下标i 是固定移动的，而if里面的下标 index 是符合条件才移动的。

如果 for 控制的是饼干， if 控制胃口，就是出现index不会移动，那么当i 持续向前移动，最后所有的饼干都匹配不上情况 。

#### **其他思路** ####

**也可以换一个思路，小饼干先喂饱小胃口**

### 代码实现 ###

class Solution {
        //思路1：优先考虑胃口，先喂饱大胃口
        public int findContentChildren(int[] g, int[] s){
            Arrays.sort(g);
            Arrays.sort(s);
            int count = 0;
            int index = s.length - 1;
            for(int i = g.length-1; i >= 0; i--){
                if(index >= 0 && s[index] >= g[i]) {
                    index--;
                    count++;
                }
            }
            return count;
        }
    }

class Solution {
        //思路2：优先考虑饼干，小饼干先喂小胃口
        public int findContentChildren(int[] g, int[] s){
            Arrays.sort(g);
            Arrays.sort(s);
            int count = 0;
            int index = 0;
            for(int i = 0; i < s.length; i++){
                if(index < g.length && s[i] >= g[index]) {
                    index++;
                    count++;
                }
            }
            return count;
        }
    }

### **总结** ###

--------------------

这道题是贪心很好的一道入门题目，思路还是比较容易想到的。

文中详细介绍了思考的过程，**想清楚局部最优，想清楚全局最优，感觉局部最优是可以推出全局最优，并想不出反例，那么就试一试贪心**。