Java 求解分发饼干

Java 求解分发饼干

文章目录

• • 一、题目
  • 二、贪心算法分析
  • 三、代码
  • 四、总结

一、题目

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

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；

并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。

你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

二、贪心算法分析

贪心算法的核心，就是通过局部的最优解，推出整体的最优解

比如本题，目标是尽可能满足越多数量的孩子，这里的局部最优解就是：大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩

既然想要获取最优解，所以首先就需要排序，这样才能每次都从局部最优解下手

这个例子可以看出饼干9只有喂给胃口为7的小孩，这样才是整体最优解

三、代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        //贪心算法，为了每次取最优解，需要先排序
        Arrays.sort(g);
        Arrays.sort(s);
        //记录饼干的下标
        int index = s.length - 1;
        //大饼干先喂给胃口大的孩子
        for (int i = g.length - 1; i >= 0 && index >= 0; i--) {
            //都采用倒叙，如果当前饼干满足当前孩子的胃口，则记录
            if (s[index] >= g[i]) {
                index--;
            }
        }
        return s.length - 1 - index;
    }
}

四、总结

贪心算法，由局部最优，推到全局最优

既然想要获取局部最优，就需要首先排序