LeetCode-455-分发饼干-贪心算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode-455-分发饼干-贪心算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述：
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

LeetCode-455-分发饼干-贪心算法,LeetCode,leetcode,贪心算法,算法

解题思路：贪心算法，根据局部最优推全局最优

将胃口数组和饼干数组都排序；

遍历数组，统计可以喂饱小孩的个数。注意从最大的饼干开始遍历，循环有两层，一个循环是满足了才能走下一个的，就是饼干数组 s，一个是可以一直重复走的，即胃口数组 g，这点要区分好。

代码实现文章来源地址https://www.toymoban.com/news/detail-686198.html

class Solution {
    /**
     * 分发饼干
     * @param g 胃口数组
     * @param s 饼干数组
     * @return
     */
    public int findContentChildren(int[] g, int[] s) {
        // 对两个数组排序
        Arrays.sort(g);
        Arrays.sort(s);
        int lenG = g.length;
        int res = 0;// 能喂饱小孩的个数
        // 由局部最优推全局最优，此处从最大的饼干开始遍历
        int sIndex = s.length-1;
        for (int i = lenG-1; i >=0 ; i--) {// 遍历g[]
            if (sIndex>=0 && s[sIndex] >= g[i]){// 遍历s[]
                // System.out.println(sIndex);
                res += 1;
                sIndex--;
            }
        }
        return res;
    }
}