当前位置: 首页 > news >正文

leetCode 455.分发饼干 贪心算法

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.

>>贪心思路(以下文字来自代码随想录代码随想录 (programmercarl.com)

为了满足更多的小孩,就不要造成饼干尺寸的浪费。大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子,那么就应该优先满足胃口大的。这里的局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩。可以尝试使用贪心策略,先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组,用大饼干优先满足胃口大的,并统计满足小孩数量。

  • ① 排序
  • ② 确定遍历顺序
  • ③ 统计

  • 先遍历小孩数组,再遍历饼干数组
class Solution {
public:// 方法一:// 局部最优 : 大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个// 全局最优就是喂饱尽可能多的小孩// 时间复杂度:O(nlogn) 空间复杂度:O(1)int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int j = s.size()-1;// 饼干数组的下标int result = 0;for (int i = g.size() - 1; i >= 0; i--) { // 遍历胃口if(j>=0 && s[j]>=g[i]) {// 遍历饼干result++;j--;}}return result;}
};
  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(1)

  • 先遍历饼干数组,再遍历小孩数组
class Solution {
public:// 方法二// 小饼干先喂饱小胃口// 时间复杂度:O(nlogn) 空间复杂度:O(1)int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int i = 0;// 饼干数组的下标int result = 0;for (int j = 0; j < s.size(); j++) { // 遍历饼干if(i < g.size() && s[j]>=g[i]) { // 遍历胃口result++;i++;}}return result;}
};
  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(1)

来自代码随想录课堂截图:

参考和推荐文章、视频

代码随想录 (programmercarl.com)

贪心算法,两者兼顾很容易顾此失彼!LeetCode:135.分发糖果_哔哩哔哩_bilibili

相关文章:

leetCode 455.分发饼干 贪心算法

455. 分发饼干 - 力扣&#xff08;LeetCode&#xff09; 假设你是一位很棒的家长&#xff0c;想要给你的孩子们一些小饼干。但是&#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i&#xff0c;都有一个胃口值 g[i]&#xff0c;这是能让孩子们满足胃口的饼干的最小尺寸&…...

vue3简易文字验证码

大神勿喷&#xff0c;简易版本&#xff0c;demo中可以用一下。 需要几个文字自己codelen 赋值 灵活点直接父组件传过去&#xff0c;可以自己改造 首先创建一个生成数字的js **mathcode.js**function MathCode(num){let str "寻寻觅觅冷冷清清凄凄惨惨戚戚乍暖还寒时候…...

Java 23种设计模式分类概括以及应用介绍

话不多说进入正题~ 创建型模式&#xff1a;5种 单例模式&#xff08;Singleton Pattern&#xff09; 确保一个类只有一个实例&#xff0c;并提供全局访问点&#xff0c;它的主要目的是限制类的实例化并确保所有代码都共享相同的实例。 – 应用&#xff1a;Runtime类、数据库连…...

运筹优化算法常用求解器汇总

运筹学从形成到发展&#xff0c;在此过程中积累的大量理论和方法在国防、能源、制造、交通、金融、通信等各个领域发挥着越来越重要的作用。我们在生产生活中遇到的很多实际问题&#xff0c;都可以通过运筹学所涉及的优化方法对其进行数学建模&#xff0c;表示为数学问题&#…...

字符串函数(一)

✨博客主页&#xff1a;小钱编程成长记 &#x1f388;博客专栏&#xff1a;进阶C语言 字符串函数&#xff08;一&#xff09; 0.前言1.求字符串长度的函数1.1 strlen&#xff08;字符串长度&#xff09; 2.长度不受限制的字符串函数2.1 strcpy&#xff08;字符串拷贝&#xff0…...

Ubuntu 安装 Docker 的详细步骤

文章目录 简介1.更新2.安装必要的软件包2.1 基于阿里源 3.验证 Docker 安装是否成功4.安装后的一些常规设置及常用的命令4.1 启动 Docker4.2 Docker 在系统启动时自动运行4.3 运行一个 Hello World 镜像4.4 查看docker运行状态 欢迎来到这篇关于在 Ubuntu 上安装 Docker 的教程…...

使用Python进行App用户细分

App用户细分是根据用户与App的互动方式对用户进行分组的任务。它有助于找到保留用户&#xff0c;找到营销活动的用户群&#xff0c;并解决许多其他需要基于相似特征搜索用户的业务问题。这篇文章中&#xff0c;将带你完成使用Python进行机器学习的App用户细分任务。 App用户细…...

博弈论——伯特兰德寡头模型(Bertrand Model)

伯特兰德寡头模型(Bertrand Model) 0 引言 在前面几篇文章中&#xff0c;我们介绍了古诺模型(Cournot duopoly model)和斯塔克尔伯格模型(Stackelberg model) 博弈论——连续产量古诺模型(Cournot duopoly model) 博弈论——斯塔克尔伯格模型(Stackelberg model) 这两个模型…...

第一百六十回 SliverPadding组件

文章目录 概念介绍使用方法示例代码 我们在上一章回中介绍了SliverAppBar组件相关的内容&#xff0c;本章回中将介绍 SliverPadding组件.闲话休提&#xff0c;让我们一起Talk Flutter吧。 概念介绍 我们在本章回中介绍的SliverPadding组件类似Pading组件&#xff0c;它主要用…...

Mapfree智驾方案,怎样实现成本可控?

整理|睿思 编辑|祥威 编者注&#xff1a;本文是HiEV出品的系列直播「智驾地图之变」第二期问答环节内容整理。 元戎启行副总裁刘轩与连线嘉宾奥维咨询董事合伙人张君毅、北汽研究总院智能网联中心专业总师林大洋、主持嘉宾周琳展开深度交流&#xff0c;并进行了答疑。 本期元…...

javascript: Bubble Sort

// Sorting Algorithms int JavaScript /** * file Sort.js * 1. Bubble Sort冒泡排序法 */ function BubbleSort(arry, nszie) {var i, j, temp;var swapped;for (i 0; i < nszie - 1; i){swapped false;for (j 0; j < nszie - i - 1; j){if (arry[j] > arry[j …...

DM数据库根据rowid删除重复的记录

oracle中rowid的用法-CSDN博客 delete from stu a where rowid not in (select max(b.rowid) from stu b where a.nob.no and a.name b.name and a.sex b.sex); //这里max使用min也可以...

【AI视野·今日Robot 机器人论文速览 第四十期】Mon, 25 Sep 2023

AI视野今日CS.Robotics 机器人学论文速览 Mon, 25 Sep 2023 Totally 36 papers &#x1f449;上期速览✈更多精彩请移步主页 Interesting: &#x1f4da;CloudGripper, 一套云化的机器抓取人数据采集系统&#xff0c;包含了32个机械臂的集群。(from KTH Royal Institute of Te…...

HashMap底层源码,数据结构

HashMap的底层结构在jdk1.7中由数组链表实现&#xff0c;在jdk1.8中由数组链表红黑树实现&#xff0c;以数组链表的结构为例。 JDK1.8之前Put方法&#xff1a; JDK1.8之后Put方法&#xff1a; HashMap基于哈希表的Map接口实现&#xff0c;是以key-value存储形式存在&#xff0c…...

计算机等级考试—信息安全三级真题八

一、单选题...

番外6:下载+安装+配置Linux

#########配置Linux---后续 step08: 点击编辑虚拟机设置&#xff0c;选择下载好的映像文件.iso进行挂载&#xff1b; step09: 点击编辑虚拟机选项&#xff0c;选择UEFI启动模式并点击确定&#xff1b; step10: 点击开启虚拟机&#xff0c;选择Install rhel &#xff1b; 备注&…...

javascript验证表单字段有效性,使用checkValidity()方法和他的属性

<script type"text/javascript">function LoginCheckValidity(){var txt"";var rmb1document.getElementById("rmb1");if(rmb1.checkValidity()false){if(rmb1.validitionMessageundefined){txt"输入金额有误,金额10-200之间";}…...

pdf怎么调整大小kb?pdf文件过大这样压缩

在日常的工作和生活中&#xff0c;我们常常会遇到需要调整PDF文件大小的问题。有时候&#xff0c;我们需要将大型的PDF文件上传到某些平台&#xff0c;但平台的限制让我们不得不压缩文件的大小。那么&#xff0c;如何有效地调整PDF文件的大小呢&#xff1f; 一、使用嗨格式压缩…...

vue3中的watch

在Vue3中&#xff0c;watch中的参数可以分为两部分&#xff0c;即要监听的响应式数据以及回调函数。 语法格式如下&#xff1a; watch(要监听的响应式数据, 回调函数)除了以上的两个还有其他的参数 immediate&#xff1a;是否在初始化时立即执行一次回调函数&#xff0c;默认…...

开绕组电机零序Bakc EMF-based无感控制以及正交锁相环inverse Park-based

前言 最近看论文遇到了基于反Park变换的锁相环&#xff0c;用于从开绕组永磁同步电机零序电压信号中提取转子速度与位置信息&#xff0c;实现无感控制。在此记录 基于零序Back EMF的转子估算 开绕组电机的零序反电动势 e 0 − 3 ω e ψ 0 s i n 3 θ e e_0-3\omega_e\psi_…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

算法刷题-回溯

今天给大家分享的还是一道关于dfs回溯的问题&#xff0c;对于这类问题大家还是要多刷和总结&#xff0c;总体难度还是偏大。 对于回溯问题有几个关键点&#xff1a; 1.首先对于这类回溯可以节点可以随机选择的问题&#xff0c;要做mian函数中循环调用dfs&#xff08;i&#x…...