455.分发饼干

LeetCode LeetCode 数组贪心排序双指针

发布时间 : 2000-01-10 04:05

字数:1.5k 阅读 :

455.分发饼干

455.分发饼干

455.1 题目

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

对每个孩子 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 * 10^4
0 <= s.length <= 3 * 10^4
1 <= g[i], s[j] <= 2^31 - 1

455.2 题解

排序+贪心算法

// 方法一：排序+贪心算法
// 先对胃口数组和饼干数组进行排序，然后从最小的胃口和最小的饼干开始匹配，
// 如果当前饼干能满足当前孩子，则计数器加一并且继续匹配下一个孩子和饼干；
// 如果不能满足，则移动到下一个饼干继续尝试。
static int FindContentChildren1(int[] g, int[] s)
{
    //对胃口数组和饼干数组进行排序
    Array.Sort(g);
    Array.Sort(s);

    // 初始化孩子指针和饼干指针
    int child = 0; // 孩子指针，用于指向孩子数组的当前位置
    int cookie = 0; // 饼干指针，用于指向饼干数组的当前位置

    // 循环匹配孩子和饼干
    while (child < g.Length && cookie < s.Length)
    {
        // 如果当前饼干能满足当前孩子，则孩子指针向后移动一个位置，并继续匹配下一个孩子和饼干
        if (s[cookie] >= g[child])
        {
            child++;
        }

        // 不管是否满足当前孩子，饼干指针都要向后移动一个位置，准备匹配下一个孩子
        cookie++;
    }

    // 返回满足孩子的数量，即孩子指针的值
    return child;
}

455.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

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

        #endregion

        #region 测试

        // 示例 1
        int[] g1 = { 1, 2, 3 };
        int[] s1 = { 1, 1 };
        int result1_1 = FindContentChildren1(g1, s1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");

        // 示例 2
        int[] g2 = { 1, 2 };
        int[] s2 = { 1, 2, 3 };
        int result2_1 = FindContentChildren1(g2, s2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");

        #endregion
    }

    #region 答案

    // 方法一：排序+贪心算法
    // 先对胃口数组和饼干数组进行排序，然后从最小的胃口和最小的饼干开始匹配，
    // 如果当前饼干能满足当前孩子，则计数器加一并且继续匹配下一个孩子和饼干；
    // 如果不能满足，则移动到下一个饼干继续尝试。
    static int FindContentChildren1(int[] g, int[] s)
    {
        //对胃口数组和饼干数组进行排序
        Array.Sort(g);
        Array.Sort(s);

        // 初始化孩子指针和饼干指针
        int child = 0; // 孩子指针，用于指向孩子数组的当前位置
        int cookie = 0; // 饼干指针，用于指向饼干数组的当前位置

        // 循环匹配孩子和饼干
        while (child < g.Length && cookie < s.Length)
        {
            // 如果当前饼干能满足当前孩子，则孩子指针向后移动一个位置，并继续匹配下一个孩子和饼干
            if (s[cookie] >= g[child])
            {
                child++;
            }

            // 不管是否满足当前孩子，饼干指针都要向后移动一个位置，准备匹配下一个孩子
            cookie++;
        }

        // 返回满足孩子的数量，即孩子指针的值
        return child;
    }

    #endregion
}

455.4 运行结果

示例1 方法1 返回长度：6，修改后数组：[a, 2, b, 2, c, 3, c]
示例2 方法1 返回长度：1，修改后数组：[a]
示例3 方法1 返回长度：4，修改后数组：[a, b, 1, 2, b, b, b, b, b, b, b, b, b]
示例1 方法2 返回长度：6，修改后数组：[a, 2, b, 2, c, 3, c]
示例2 方法2 返回长度：1，修改后数组：[a]
示例3 方法2 返回长度：4，修改后数组：[a, b, 1, 2, b, b, b, b, b, b, b, b, b]

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com