Go语言题解LeetCode455分发饼干示例详解

目录
  • 题目描述
  • 思路分析
  • AC 代码
  • 分发饼干 贪心算法
    • 解题思路
  • 代码

题目描述

原题链接 :

455. 分发饼干 - 力扣（LeetCode） (leetcode-cn.com)

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

对每个孩子 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

思路分析

其实这道题真的很像田忌赛 马，我们这么想，我们要打败一堆小朋友，其中有上等小朋友，中等小朋友，下等小朋友。

而我们有上等饼干，中等饼干，下等饼干，小朋友只有吃了足够大的饼干才会被打败，我们该怎么做？

答案一定是要，要用最上等的饼干打败最厉害的小朋友，不然就是一种浪费（如果你用上等饼干打败下等小朋友，那么谁来打败上等小朋友？）

其实这也是贪心思想，想法有了，就剩下实现代码了，代码如下

AC 代码

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(s.begin(),s.end(),greater<int>());
        sort(g.begin(),g.end(),greater<int>());
        int i=0,j=0,ans=0;
        while(i<s.size()&&j<g.size())
        {
            if(s[i]>=g[j])
            {
                ++ans;++i;++j;
            }
            else
            ++j;
        }
        return ans;
    }
};

分发饼干 贪心算法

解题思路

先对两个数组排序

从后开始遍历g，使得大饼干给胃口大的孩子

局部最优就是胃口大的孩子匹配大的饼干

代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {//s:饼干
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = s.length - 1;//饼干数量
        for(int index = g.length - 1; index >= 0; index--){
            if(start >= 0 && g[index] <= s[start]){
                count++;
                start--;
            }
        }
        return count;
    }
}

以上就是Go语言题解LeetCode455分发饼干示例详解的详细内容，更多关于Go题解分发饼干的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Go语言题解LeetCode561数组拆分

    目录 一 描述 二 分析 三 答案 Python 语言 - 数组拆分 解题思路 代码一 代码二 代码三 一 描述 561. 数组拆分 I - 力扣(LeetCode) (leetcode-cn.com) 给定长度为 2n 的整数数组 nums ,你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从 1 到 n 的 min(ai, bi) 总和最大. 返回该 最大总和 . 示例 1: 输入:nums = [1,4,3,2] 输出:4

  • go语言题解LeetCode1160拼写单词示例详解

    目录 题目描述 思路分析 AC 代码 别人用int[26] 解题思路 代码 c++几乎双百的哈希解法 代码 题目描述 1160. 拼写单词 - 力扣(LeetCode) 给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars. 假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词. 注意:每次拼写(指拼写词汇表中的一个单词)时,chars 中的每个字母都只能用一次. 返回词汇表 words 中你

  • go语言题解LeetCode506相对名次示例详解

    目录 一 描述 二 分析 三 答案 一 描述 506. 相对名次 给你一个长度为 n 的整数数组 score ,其中 score[i] 是第 i 位运动员在比赛中的得分.所有得分都 互不相同 . 运动员将根据得分 决定名次 ,其中名次第 1 的运动员得分最高,名次第 2 的运动员得分第 2 高,依此类推.运动员的名次决定了他们的获奖情况: 名次第 1 的运动员获金牌 "Gold Medal" . 名次第 2 的运动员获银牌 "Silver Medal" . 名次第

  • go语言题解LeetCode1128等价多米诺骨牌对的数量

    目录 题目描述 思路分析 AC 代码 偷懒解法 思路: 图解: 代码: 哈希表+元素转换 解题思路 代码 复杂度分析 题目描述 1128. 等价多米诺骨牌对的数量 - 力扣(LeetCode) 给你一个由一些多米诺骨牌组成的列表 dominoes. 如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌,我们就认为这两张牌是等价的. 形式上,dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d,或是 

  • Go语言题解LeetCode455分发饼干示例详解

    目录 题目描述 思路分析 AC 代码 分发饼干 贪心算法 解题思路 代码 题目描述 原题链接 : 455. 分发饼干 - 力扣(LeetCode) (leetcode-cn.com) 假设你是一位很棒的家长,想要给你的孩子们一些小饼干.但是,每个孩子最多只能给一块饼干. 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸:并且每块饼干 j,都有一个尺寸 s[j] .如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足.你的目标

  • go语言题解LeetCode66加一示例详解

    目录 题目描述 思路分析 AC 代码 小结 JavaScript 66题 代码 python3 循环判断 分析: JAVA解决进位问题 解题思路 代码 题目描述 原题链接 : 66. 加一 给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一. 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字. 你可以假设除了整数 0 之外,这个整数不会以零开头. 示例 1: 输入:digits = [1,2,3] 输出:[1,2,4] 解释:输入数组表示数字 123. 示例 2:

  • C语言中的正则表达式使用示例详解

    正则表达式,又称正规表示法.常规表示法(英语:Regular Expression,在代码中常简写为regex.regexp或RE).正则表达式是使用单个字符串来描述.匹配一系列符合某个句法规则的字符串. 在c语言中,用regcomp.regexec.regfree 和regerror处理正则表达式.处理正则表达式分三步: 编译正则表达式,regcomp: 匹配正则表达式,regexec: 释放正则表达式,regfree. 函数原型 /* 函数说明:Regcomp将正则表达式字符串regex编译

  • VSCode各语言运行环境配置方法示例详解

    系统环境变量的配置 如:将F:\mingw64\bin添加到系统环境变量Path中 VSCode软件语言json配置C语言 创建个.vscode文件夹,文件夹内创建以下两个文件 launch.json 文件配置 { "version": "0.2.0", "configurations": [ { "name": "(gdb) Launch", "type": "cppdbg&

  • c语言左移和右移的示例详解

    逻辑移位,简单理解就是物理上按位进行的左右移动,两头用0进行补充,不关心数值的符号问题. 算术移位,同样也是物理上按位进行的左右移动,两头用0进行补充,但必须确保符号位不改变. 算术移位指令 算术移位指令有:算术左移SAL(ShiftAlgebraic Left)和算术右移SAR(ShiftAlgebraic Right).算术移位指令的功能描述如下: (1)算术左移SAL把目的操作数的低位向高位移,空出的低位补0: (2)算术右移SAR把目的操作数的高位向低位移,空出的高位用最高位(符号位)填

  • R语言时间序列TAR阈值自回归模型示例详解

    R语言时间序列TAR阈值自回归模型示例详解

    为了方便起见,这些模型通常简称为TAR模型.这些模型捕获了线性时间序列模型无法捕获的行为,例如周期,幅度相关的频率和跳跃现象.Tong和Lim(1980)使用阈值模型表明,该模型能够发现黑子数据出现的不对称周期性行为. 一阶TAR模型的示例: σ是噪声标准偏差,Yt-1是阈值变量,r是阈值参数, {et}是具有零均值和单位方差的iid随机变量序列. 每个线性子模型都称为一个机制.上面是两个机制的模型. 考虑以下简单的一阶TAR模型: #低机制参数 i1 = 0.3 p1 = 0.5 s1 = 1

  • R语言编程重读微积分泰勒级数示例详解

    R语言编程重读微积分泰勒级数示例详解

    一 理解极限 二 微分学 泰勒级数 如果我是泰勒,我会把思考的起点建立在这样的一个等式上 那么接下来我们直观地感受一下Taylor级数时如何逐渐逼近某个函数的.简单起见,在此选择  sinx作为被拟合的函数. library(ggplot2) library(gganimate) library(av) library(tibble) x = seq(-pi,pi,0.1) n = length(x) xs = rep(x,11) ys = rep(sin(0),n) ts = rep(0,n)

  • Go语言基础单元测试与性能测试示例详解

    目录 概述 单元测试 代码说明如下 问题 注意 性能测试 基本使用 自定义测试时间 概述 测试不是Go语言独有的,其实在很多语言都有测试,例如:Go.Java.Python- 要想成为一名合格的大牛,这是程序员必须具备的一项技能,特别是一些大公司,这是加分的一项,主要有如下优点: 代码可以随时测试,保证代码不会产生错误 写出更加高效的代码 testing文档 Testing_flags文档 单元测试 格式:func TestXXX(t *testing.T) //add.go package c

随机推荐