刷题记录 贪心算法-2:455. 分发饼干
题目:455. 分发饼干
难度:简单
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 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 * 1040 <= s.length <= 3 * 1041 <= g[i], s[j] <= 231 - 1
一、模式识别
1.贪心算法
局部最优解:找到满足胃口最小(大)的孩子的最小(大)饼干
从局部到全局:每满足一个孩子继续用剩余的饼干满足剩余的孩子
反例:想不到。。。
2.双指针
根据题干条件想到双指针并不难,其实我一开始是用双指针的思路做的:
题目条件:两个数组 + 逐个数字比大小(s[j] >= g[i]) -> 解法:双指针
官方解法中的解释是:排序 + 双指针 + 贪心:
为了尽可能满足最多数量的孩子,从贪心的角度考虑,应该按照孩子的胃口从小到大的顺序依次满足每个孩子,且对于每个孩子,应该选择可以满足这个孩子的胃口且尺寸最小的饼干。
还给出了证明,但我觉得思路上理解起来并不难,所以证明过程不用细看
二.代码实现
1.双指针 + 从小胃口孩子开始喂(最简洁实现)
步骤:1.排序 2.双指针 3.循环数字比大小
写法有while循环写法和for循环写法,推荐while循环写法,可读性较强,
可以理解为for循环写法衍生于while循环写法
while循环写法:
class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:if not s:return 0m, n = len(g), len(s)g.sort()s.sort()i, j = 0, 0while i < n and j < m:if s[i] >= g[j]:j += 1i += 1return j
for循环写法:
class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:if not s:return 0m, n = len(g), len(s)s.sort()g.sort()j = 0for i in range(n):if j < m and s[i] >= g[j]:j += 1return j
- 时间复杂度:O(nlogn)
- 空间复杂度:O(1)
2.双指针 + 从大胃口孩子开始喂
步骤:1.排序 2.双指针 3.循环数字比大小
不同于从小胃口孩子喂,除了倒序访问的区别外,
从大胃口孩子开始喂不能直接返回索引,因此多了一个变量ans
和从小胃口一样,写法有while循环写法和for循环写法,推荐while循环写法,可读性较强,
可以理解为for循环写法衍生于while循环写法
while循环写法:
class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:if not s:return 0g.sort()s.sort()m, n = len(g), len(s)i, j = n - 1, m - 1ans = 0while i >= 0 and j >= 0:if s[i] >= g[j]:i -= 1ans += 1j -= 1return ans
for循环写法:
class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:if not s:return 0g.sort()s.sort()m, n = len(g), len(s)i = n - 1ans = 0for j in range(m - 1, -1, -1):if i >= 0 and s[i] >= g[j]:i -= 1ans += 1return ans
- 时间复杂度:O(nlogn)
- 空间复杂度:O(1)
3.可以用栈/队列代替双指针
实现的逻辑相同,就是用栈/队列的抛出操作代替了移动指针操作,但队列比指针操作耗时略大:
从小胃口孩子开始喂(栈):
class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:if not s:return 0ans = 0g.sort()s.sort()while g and s:ch_g = g.pop()if s[-1] >= ch_g:s.pop()ans += 1return ans
从大胃口孩子开始喂(队列):
class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:if not s:return 0ans = 0g.sort()s.sort()gdeque = deque(g)sdeque = deque(s)while gdeque and sdeque:ch_s = sdeque.popleft()if ch_s >= gdeque[0]:gdeque.popleft()ans += 1return ans
- 时间复杂度:O(nlogn)
- 空间复杂度:O(n)
三、为什么两种实现方式遍历的数组不同
模式识别目的是快速找到一个解法,
但为了满足自己好奇心以及加快以后的模式识别,我想探究一下这个问题
配对条件是饼干大小s[j] >= 胃口g[i],即饼干大于胃口
从小到大配对时,需要遍历要求较大者饼干,保证所有大饼干配对
即从小到大遍历要求较大者(饼干),防止小饼干无法配对导致错过大饼干,
如果遍历胃口,面临饼干组左端尺寸过小的饼干时,无法继续找更大的饼干
从大到小配对时,需要遍历要求较小者胃口,保证所有小胃口配对
即从大到小遍历要求较小者(胃口),防止大胃口无法配对导致错过小胃口,
如果遍历饼干,面临胃口组右端胃口过大的孩子时,无法继续找更小的胃口
相关文章:
刷题记录 贪心算法-2:455. 分发饼干
题目:455. 分发饼干 难度:简单 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸&a…...
Android --- CameraX讲解
预备知识 surface surfaceView SurfaceHolder surface 是什么? 一句话来说: surface是一块用于填充图像数据的内存。 surfaceView 是什么? 它是一个显示surface 的View。 在app中仍在 ViewHierachy 中,但在wms 中可以理解为…...
ElasticSearch view
基础知识类 elasticsearch和数据库之间区别? elasticsearch:面向文档,数据以文档的形式存储,即JSON格式的对象。更强调数据的搜索、索引和分析。 数据库:更侧重于事务处理、数据的严格结构化和完整性,适用于…...
list的使用,及部分功能的模拟实现(C++)
目录(文章中"节点"和"结点"是同一个意思) 1. list的介绍及使用 1.1 list的介绍 1.2 list的使用 1.2.1 list的构造 1.2.2 list iterator的使用 1.2.3 list capacity 1.2.4 list element access 1.2.5 list modifiers 1.2.6 list…...
联想Y7000+RTX4060+i7+Ubuntu22.04运行DeepSeek开源多模态大模型Janus-Pro-1B+本地部署
直接上手搓了: conda create -n myenv python3.10 -ygit clone https://github.com/deepseek-ai/Janus.gitcd Januspip install -e .pip install webencodings beautifulsoup4 tinycss2pip install -e .[gradio]pip install pexpect>4.3python demo/app_januspr…...
[Spring] Gateway详解
🌸个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 🏵️热门专栏: 🧊 Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm1001.2014.3001.5482 🍕 Collection与…...
音叉模态分析
目录 0 序言 1 自由状态下模态求解 1.1 添加模态项目 1.2 生成网格 1.3 设置最大模态阶数 1.4 求解 1.5 结果查看 1.6 结果分析 2 音叉能否释放频率440Hz的音调 3 预应力模态求解 3.1 静态结构分析 3.1.1 添加静态结构项目 3.1.2生成网格 3.1.3添加边界条件 3.1…...
BW AO/工作簿权限配置
场景: 按事业部配置工作簿权限; 1、创建用户 事务码:SU01,用户主数据的维护,可以创建、修改、删除、锁定、解锁、修改密码等 用户设置详情页 2、创建权限角色 用户的权限菜单是通过权限角色分配来实现的 2.1、自定…...
C++ 字母大小写转换两种方法统计数字字符的个数
目录 题目: 代码1: 代码2: 题目描述输入一行字符,统计出其中数字字符的个数。 代码如下: 判断⼀个字符是否是数字字符有⼀个函数是 isdigit ,可以直接使⽤。 代码如下: 题目: 大家都知道…...
如何使用 ChatBox AI 简化本地模型对话操作
部署模型请看上一篇帖子:本地部署DeepSeek教程(Mac版本)-CSDN博客 使用 ChatBox AI 简化本地模型对话操作: 打开 ChatBox AI 官网:Chatbox AI官网:办公学习的AI好助手,全平台AI客户端…...
前端面试笔试题目(一)
以下模拟了大厂前端面试流程,并给出了涵盖HTML、CSS、JavaScript等基础和进阶知识的前端笔试题目,以帮助你更好地准备面试。 面试流程模拟 1. 自我介绍(5 - 10分钟):面试官会请你进行简单的自我介绍,包括…...
Docker Hello World
Docker Hello World 引言 Docker 是一个开源的应用容器引擎,可以让开发者打包他们的应用以及应用的依赖包到一个可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化。本文将带领您从零开始,学习如何使用 Docker 运行一个简单的 "Hello World"…...
UE 5.3 C++ 对垃圾回收的初步认识
一.UObject的创建 UObject 不支持构造参数。 所有的C UObject都会在引擎启动的时候初始化,然后引擎会调用其默认构造器。如果没有默认的构造器,那么 UObject 将不会编译。 有修改父类参数的需求,就使用指定带参构造 // Sets default value…...
ARM内核:嵌入式时代的核心引擎
引言 在当今智能设备无处不在的时代,ARM(Advanced RISC Machines)处理器凭借其高性能、低功耗的特性,成为智能手机、物联网设备、汽车电子等领域的核心引擎。作为精简指令集(RISC)的典范,ARM核…...
需求分析应该从哪些方面来着手做?
需求分析一般可从以下几个方面着手: 业务需求方面 - 与相关方沟通:与业务部门、客户等进行深入交流,通过访谈、问卷调查、会议讨论等方式,明确他们对项目的期望、目标和整体业务需求,了解项目要解决的业务问题及达成的…...
【Unity2D 2022:C#Script】DoTween插件的使用
一、插件介绍 DOTween 是一个快速、高效、完全类型安全的 Unity 面向对象的动画引擎,针对 C# 用户进行了优化,免费和开源,具有大量高级功能 二、插件的下载 1. DoTween官网:DOTween (HOTween v2) 2. DoTween下载: …...
【Docker】ubuntu中 Docker的使用
之前记录了 docker的安装 【环境配置】ubuntu中 Docker的安装; 本篇博客记录Dockerfile的示例,docker 的使用,包括镜像的构建、容器的启动、docker compose的使用等。 当安装好后,可查看docker的基本信息 docker info ## 查…...
【数据结构篇】时间复杂度
一.数据结构前言 1.1 数据结构的概念 数据结构(Data Structure)是计算机存储、组织数据的⽅式,指相互之间存在⼀种或多种特定关系的数 据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤,所以我们要学各式各样的数据结构, 如:…...
linux 环境安装 dlib 的 gpu 版本
默认使用 pip 安装的 dlib 是不使用 gpu 的 在国内社区用百度查如何安装 gpu 版本的 dlib 感觉信息都不太对,都是说要源码编译还有点复杂 还需要自己安装 cuda 相关的包啥的,看着就头大 于是想到这个因该 conda 自己就支持了吧,然后查了一下…...
springboot集成钉钉,发送钉钉日报
目录 1.说明 2.示例 3.总结 1.说明 学习地图 - 钉钉开放平台 在钉钉开放文档中可以查看有关日志相关的api,主要用到以下几个api: ①获取模板详情 ②获取用户发送日志的概要信息 ③获取日志接收人员列表 ④创建日志 发送日志时需要根据模板规定日志…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
