leetcode【贪心算法—简单】455.分发饼干

文章目录

• 前言
• 题目
• 题解
• NO1：排序+贪心（先满足胃口小的）
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为贪心算法专题。

---

题目

题目来源leetcode

leetcode地址：455. 分发饼干，难度：简单。

题目描述(摘自leetcode)：

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 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 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

本地调试代码：

class Solution {

    public int findContentChildren(int[] g, int[] s) {
        ...
    }

    public static void main(String[] args) {
        int[] g = new int[]{10, 9, 8, 7};
        int[] s = new int[]{5, 6, 7, 8};
        int count = new Solution().findContentChildren(g, s);
        System.out.println(count);
    }

}

---

题解

NO1：排序+贪心（先满足胃口小的）

思路： 先将饼干大小以及小孩子胃口大小按照从小到大排序，紧接着以小孩子为中心，来从前往后依次与饼干比对是否有满足的若是有的话饼干位置以及孩子位置往后一格，若是不满足仅仅移动饼干位置。

代码：

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    int count = 0;
    //childPos：孩子的位置
    //sweetPos：糖果的位置
    //从小胃口开始，优先喂给小胃口的。每次比对糖果数量位置必+1
    for (int childPos = 0, sweetPos = 0; childPos < g.length && sweetPos < s.length; sweetPos++) {
        //能满足时，孩子位置+1，满足数量+1
        if (g[childPos] <= s[sweetPos]) {
            count++;
            childPos++;
        }
    }
    return count;
}

---

参考文章

[1]. leetcode题解

[2]. 代码随想录— 455.分发饼干

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.9