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

刷题记录 贪心算法-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 * 104
  • 0 <= s.length <= 3 * 104
  • 1 <= 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. 分发饼干

题目&#xff1a;455. 分发饼干 难度&#xff1a;简单 假设你是一位很棒的家长&#xff0c;想要给你的孩子们一些小饼干。但是&#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i&#xff0c;都有一个胃口值 g[i]&#xff0c;这是能让孩子们满足胃口的饼干的最小尺寸&a…...

Android --- CameraX讲解

预备知识 surface surfaceView SurfaceHolder surface 是什么&#xff1f; 一句话来说&#xff1a; surface是一块用于填充图像数据的内存。 surfaceView 是什么&#xff1f; 它是一个显示surface 的View。 在app中仍在 ViewHierachy 中&#xff0c;但在wms 中可以理解为…...

ElasticSearch view

基础知识类 elasticsearch和数据库之间区别&#xff1f; elasticsearch&#xff1a;面向文档&#xff0c;数据以文档的形式存储&#xff0c;即JSON格式的对象。更强调数据的搜索、索引和分析。 数据库&#xff1a;更侧重于事务处理、数据的严格结构化和完整性&#xff0c;适用于…...

list的使用,及部分功能的模拟实现(C++)

目录&#xff08;文章中"节点"和"结点"是同一个意思&#xff09; 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+本地部署

直接上手搓了&#xff1a; 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详解

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏: &#x1f9ca; Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm1001.2014.3001.5482 &#x1f355; 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/工作簿权限配置

场景&#xff1a; 按事业部配置工作簿权限&#xff1b; 1、创建用户 事务码&#xff1a;SU01&#xff0c;用户主数据的维护&#xff0c;可以创建、修改、删除、锁定、解锁、修改密码等 用户设置详情页 2、创建权限角色 用户的权限菜单是通过权限角色分配来实现的 2.1、自定…...

C++ 字母大小写转换两种方法统计数字字符的个数

目录 题目&#xff1a; 代码1&#xff1a; 代码2&#xff1a; 题目描述输入一行字符&#xff0c;统计出其中数字字符的个数。 代码如下&#xff1a; 判断⼀个字符是否是数字字符有⼀个函数是 isdigit ,可以直接使⽤。 代码如下&#xff1a; 题目&#xff1a; 大家都知道…...

如何使用 ChatBox AI 简化本地模型对话操作

部署模型请看上一篇帖子&#xff1a;本地部署DeepSeek教程&#xff08;Mac版本&#xff09;-CSDN博客 使用 ChatBox AI 简化本地模型对话操作&#xff1a; 打开 ChatBox AI 官网&#xff1a;Chatbox AI官网&#xff1a;办公学习的AI好助手&#xff0c;全平台AI客户端&#xf…...

前端面试笔试题目(一)

以下模拟了大厂前端面试流程&#xff0c;并给出了涵盖HTML、CSS、JavaScript等基础和进阶知识的前端笔试题目&#xff0c;以帮助你更好地准备面试。 面试流程模拟 1. 自我介绍&#xff08;5 - 10分钟&#xff09;&#xff1a;面试官会请你进行简单的自我介绍&#xff0c;包括…...

Docker Hello World

Docker Hello World 引言 Docker 是一个开源的应用容器引擎,可以让开发者打包他们的应用以及应用的依赖包到一个可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化。本文将带领您从零开始,学习如何使用 Docker 运行一个简单的 "Hello World"…...

UE 5.3 C++ 对垃圾回收的初步认识

一.UObject的创建 UObject 不支持构造参数。 所有的C UObject都会在引擎启动的时候初始化&#xff0c;然后引擎会调用其默认构造器。如果没有默认的构造器&#xff0c;那么 UObject 将不会编译。 有修改父类参数的需求&#xff0c;就使用指定带参构造 // Sets default value…...

ARM内核:嵌入式时代的核心引擎

引言 在当今智能设备无处不在的时代&#xff0c;ARM&#xff08;Advanced RISC Machines&#xff09;处理器凭借其高性能、低功耗的特性&#xff0c;成为智能手机、物联网设备、汽车电子等领域的核心引擎。作为精简指令集&#xff08;RISC&#xff09;的典范&#xff0c;ARM核…...

需求分析应该从哪些方面来着手做?

需求分析一般可从以下几个方面着手&#xff1a; 业务需求方面 - 与相关方沟通&#xff1a;与业务部门、客户等进行深入交流&#xff0c;通过访谈、问卷调查、会议讨论等方式&#xff0c;明确他们对项目的期望、目标和整体业务需求&#xff0c;了解项目要解决的业务问题及达成的…...

【Unity2D 2022:C#Script】DoTween插件的使用

一、插件介绍 DOTween 是一个快速、高效、完全类型安全的 Unity 面向对象的动画引擎&#xff0c;针对 C# 用户进行了优化&#xff0c;免费和开源&#xff0c;具有大量高级功能 二、插件的下载 1. DoTween官网&#xff1a;DOTween (HOTween v2) 2. DoTween下载&#xff1a; …...

【Docker】ubuntu中 Docker的使用

之前记录了 docker的安装 【环境配置】ubuntu中 Docker的安装&#xff1b; 本篇博客记录Dockerfile的示例&#xff0c;docker 的使用&#xff0c;包括镜像的构建、容器的启动、docker compose的使用等。   当安装好后&#xff0c;可查看docker的基本信息 docker info ## 查…...

【数据结构篇】时间复杂度

一.数据结构前言 1.1 数据结构的概念 数据结构(Data Structure)是计算机存储、组织数据的⽅式&#xff0c;指相互之间存在⼀种或多种特定关系的数 据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤&#xff0c;所以我们要学各式各样的数据结构&#xff0c; 如&#xff1a…...

linux 环境安装 dlib 的 gpu 版本

默认使用 pip 安装的 dlib 是不使用 gpu 的 在国内社区用百度查如何安装 gpu 版本的 dlib 感觉信息都不太对&#xff0c;都是说要源码编译还有点复杂 还需要自己安装 cuda 相关的包啥的&#xff0c;看着就头大 于是想到这个因该 conda 自己就支持了吧&#xff0c;然后查了一下…...

springboot集成钉钉,发送钉钉日报

目录 1.说明 2.示例 3.总结 1.说明 学习地图 - 钉钉开放平台 在钉钉开放文档中可以查看有关日志相关的api&#xff0c;主要用到以下几个api&#xff1a; ①获取模板详情 ②获取用户发送日志的概要信息 ③获取日志接收人员列表 ④创建日志 发送日志时需要根据模板规定日志…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...