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. 分发饼干 - 力扣(LeetCode) 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸&…...
vue3简易文字验证码
大神勿喷,简易版本,demo中可以用一下。 需要几个文字自己codelen 赋值 灵活点直接父组件传过去,可以自己改造 首先创建一个生成数字的js **mathcode.js**function MathCode(num){let str "寻寻觅觅冷冷清清凄凄惨惨戚戚乍暖还寒时候…...
Java 23种设计模式分类概括以及应用介绍
话不多说进入正题~ 创建型模式:5种 单例模式(Singleton Pattern) 确保一个类只有一个实例,并提供全局访问点,它的主要目的是限制类的实例化并确保所有代码都共享相同的实例。 – 应用:Runtime类、数据库连…...
运筹优化算法常用求解器汇总
运筹学从形成到发展,在此过程中积累的大量理论和方法在国防、能源、制造、交通、金融、通信等各个领域发挥着越来越重要的作用。我们在生产生活中遇到的很多实际问题,都可以通过运筹学所涉及的优化方法对其进行数学建模,表示为数学问题&#…...
字符串函数(一)
✨博客主页:小钱编程成长记 🎈博客专栏:进阶C语言 字符串函数(一) 0.前言1.求字符串长度的函数1.1 strlen(字符串长度) 2.长度不受限制的字符串函数2.1 strcpy(字符串拷贝࿰…...
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的互动方式对用户进行分组的任务。它有助于找到保留用户,找到营销活动的用户群,并解决许多其他需要基于相似特征搜索用户的业务问题。这篇文章中,将带你完成使用Python进行机器学习的App用户细分任务。 App用户细…...
博弈论——伯特兰德寡头模型(Bertrand Model)
伯特兰德寡头模型(Bertrand Model) 0 引言 在前面几篇文章中,我们介绍了古诺模型(Cournot duopoly model)和斯塔克尔伯格模型(Stackelberg model) 博弈论——连续产量古诺模型(Cournot duopoly model) 博弈论——斯塔克尔伯格模型(Stackelberg model) 这两个模型…...
第一百六十回 SliverPadding组件
文章目录 概念介绍使用方法示例代码 我们在上一章回中介绍了SliverAppBar组件相关的内容,本章回中将介绍 SliverPadding组件.闲话休提,让我们一起Talk Flutter吧。 概念介绍 我们在本章回中介绍的SliverPadding组件类似Pading组件,它主要用…...
Mapfree智驾方案,怎样实现成本可控?
整理|睿思 编辑|祥威 编者注:本文是HiEV出品的系列直播「智驾地图之变」第二期问答环节内容整理。 元戎启行副总裁刘轩与连线嘉宾奥维咨询董事合伙人张君毅、北汽研究总院智能网联中心专业总师林大洋、主持嘉宾周琳展开深度交流,并进行了答疑。 本期元…...
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 👉上期速览✈更多精彩请移步主页 Interesting: 📚CloudGripper, 一套云化的机器抓取人数据采集系统,包含了32个机械臂的集群。(from KTH Royal Institute of Te…...
HashMap底层源码,数据结构
HashMap的底层结构在jdk1.7中由数组链表实现,在jdk1.8中由数组链表红黑树实现,以数组链表的结构为例。 JDK1.8之前Put方法: JDK1.8之后Put方法: HashMap基于哈希表的Map接口实现,是以key-value存储形式存在,…...
计算机等级考试—信息安全三级真题八
一、单选题...
番外6:下载+安装+配置Linux
#########配置Linux---后续 step08: 点击编辑虚拟机设置,选择下载好的映像文件.iso进行挂载; step09: 点击编辑虚拟机选项,选择UEFI启动模式并点击确定; step10: 点击开启虚拟机,选择Install rhel ; 备注&…...
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文件过大这样压缩
在日常的工作和生活中,我们常常会遇到需要调整PDF文件大小的问题。有时候,我们需要将大型的PDF文件上传到某些平台,但平台的限制让我们不得不压缩文件的大小。那么,如何有效地调整PDF文件的大小呢? 一、使用嗨格式压缩…...
vue3中的watch
在Vue3中,watch中的参数可以分为两部分,即要监听的响应式数据以及回调函数。 语法格式如下: watch(要监听的响应式数据, 回调函数)除了以上的两个还有其他的参数 immediate:是否在初始化时立即执行一次回调函数,默认…...
开绕组电机零序Bakc EMF-based无感控制以及正交锁相环inverse Park-based
前言 最近看论文遇到了基于反Park变换的锁相环,用于从开绕组永磁同步电机零序电压信号中提取转子速度与位置信息,实现无感控制。在此记录 基于零序Back EMF的转子估算 开绕组电机的零序反电动势 e 0 − 3 ω e ψ 0 s i n 3 θ e e_0-3\omega_e\psi_…...
番外5:下载+安装+配置Linux
任务前期工作: 01. 电脑已安装好VMware Workstation软件; 02.提前下载好Rhel-8.iso映像文件(文件较大一般在9.4GB,建议采用迅雷下载),本人使用的以下版本(地址ed2k://|file|rhel-8.4-x86_64-dvd…...
新手--安装好Quartus II13.0(带modelsim集成包)并用Quartus II搭建一个工程
前言 今天是国庆节,我们正式来学习Quartus II13.0软件的安装与使用。学习verilog与学习C语言都是学习一门语言,那么学习一门语言,光看理论不敲代码绝对是学习不好的。要用verilog语言敲代码,就要像C语言那样搭建起语言的编译环境&…...
python监控软件内存、cpu和GDI
目录 前言代码 前言 最近做软件测试需要监控软件内存、cpu和GDI对象数,用psutil库可以很方便的实现监控内存和CPU,但是GDI好像还不行,最后来的win32api来调用的Windows API接口来实现GDI监控的,在此做个记录。 代码 import psu…...
wordpress搭建自己的博客详细过程以及踩坑
WordPress作为一款开源的内容管理系统(CMS),具有诸多优势。首先,它的易用性使得即使对于没有编程经验的用户来说也能轻松上手,通过直观的用户界面和友好的管理工具,用户可以方便地创建、编辑和发布内容。其…...
在jupyter中更改、增加内核
今天在配置llama2的环境,在学院实验室的服务器上面用jupyter,怎么都不会增加内核。今天说一下怎么把创建好的conda环境增加到jupyter列表中。 例如我有个环境叫做llama2,很简单只要两步。 第一步先激活conda环境。 conda activate llama2第…...
Redis代码实践总结(二)
使用 CLI 探索 Redis 外部程序使用 TCP 套接字和 Redis 特定协议与 Redis 进行通信。该协议在不同编程语言的 Redis 客户端库中实现。然而,为了使使用 Redis 进行黑客攻击变得更简单,Redis 提供了一个命令行实用程序,可用于向 Redis 发送命令…...
读取一张图片各种颜色占比
提问之初 <small> 读取一张图片各种颜色占比 /storage/emulated/0/Pictures/Screenshots/Screenshot_20230725_195440.jpg有趣优雅热情沉着的代码与注释/每行每行 from PIL import Image # 导入PIL大法,这是处理图像的必备神器# 图片路径,此处为…...
C程序设计内容与例题讲解 -- 第四章--选择结构程序设计(第五版)谭浩强
前言:在第三章我们介绍了顺序结构程序设计。在顺序结构中,各个语句是按自上而下的顺序执行的,执行完上一个语句就自动执行下一个语句,是无条件的,不必做任何判断。是这最简单的程序结构。实际上,在很多情况…...
Blued引流脚本
于多数人来说,引流都是一个比较困难的操作,因为流量不会听你的。所以任何人在网上做生意,或者开一个实体店,都会为流量而发愁,其实对于流量的吸引来说,我们越是刻意为之,可能所获得的效果也越不…...
数据结构之美:如何优化搜索和排序算法
文章目录 搜索算法的优化1. 二分搜索2. 哈希表 排序算法的优化1. 快速排序2. 归并排序 总结 🎉欢迎来到数据结构学习专栏~数据结构之美:如何优化搜索和排序算法 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒🍹✨博客主页:IT陈寒的博客&#x…...
组合wordpress源码/百度电话号码
本程序媛搞前端的,上班偶有空闲,不妨来学习学习,不然怎么包养小白脸,走上人生巅峰? 说实话,每个语言都相通,有了javascript的基础,并且有了两三年跟java打交道的经验,简单…...
国外印花图案设计网站/网址推荐
概述 go语言版本的kafakaAPI 准备 golang sarama 简单使用 生产和消费的过程都是通过一个配置开始的. 生产者 //设置配置 config : sarama.NewConfig() //等待服务器所有副本都保存成功后的响应 config.Producer.RequiredAcks sarama.WaitForAll //随机的分…...
南京建站方案/seo为什么要进行外部优化
移动互联网从一诞生就不是个需求聚焦和“大众化”的工具,而是一个充满个性化需求,进而有着鲜明“族群化”特性的新世界。这将深刻影响整个商业链条的形态和价值分配规则。除了吃饭睡觉,你的生命中有多少时间是被用在手机上? 实际…...
哈尔滨建站人/最厉害的搜索引擎
文章目录背景知识算术编码二值化CABACctx模型及相关函数ctx模型初始化函数 BinProbModel_Std()函数 BinProbModel_Std::init()函数setLog2WindowSize编码引擎初始化函数 BinEncoderBase::start()函数 BinEncoderBase::restart()CABAC内核普通编码:函数encodeBin()旁…...
wordpress字母头像纯css生成/游戏推广员怎么做
之前我们为大家介绍过一项非常酸爽的研究“Talking Face Generation”:给定音频或视频后(输入),可以让任意一个人的面部特征与输入的音视频信息保持一致,也就是说出输入的这段话。当时就想到了“杨超越的声音高晓松的脸”这样的神仙搭配。不过…...
广州专门做网站/杭州seo排名优化外包
一、数据类型1.Java的数据类型可分为基本数据类型(8种)和引用数据类型(N种)。基本数据类型:int(整型)、long(长整型)、short(短整型)、byte(位)、char(字符)、float(单精度)、double(双精度)。布尔(boolean)类型的变量只有true(真)和flase(假)两种。引用数据类型&am…...