分发饼干(贪心算法+图解)

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.

提示:

  • 1 <= g.length <= 3 * 104
  • 0 <= s.length <= 3 * 104
  • 1 <= g[i], s[j] <= 231 - 1

题解

贪心思想

首先对饼干的大小个孩子们的胃口大小从到大排序,遍历饼干数组,指针i指向当前的饼干,指针index指向当前的孩子,那么如果当前的饼干大小不能满足当前的孩子胃口,也就是s[i]<g[index],说明这块饼干也不能满足后边孩子的胃口(因为孩子的胃口是从小到大排列的),因此换下一块饼干继续判断(i++),否则就将当前饼干分给孩子,换下一个孩子继续判断(index++)

在整个遍历的过程中,由于饼干无论能不能分给孩子,都需要i++,因为如果饼干不能分给当前的孩子,那么i++直接换下一个饼干尝试,如果饼干分给了当前孩子,那么还是要i++,同时index++,取下一块饼干分给下一个孩子,故而整个遍历的时间是所有饼干的遍历时间

代码

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/191208.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

centos利用find提权反弹shell

需要说明的是利用find命令进行提权的方式已经不存在了&#xff0c;因为Linux默认不会为find命令授予suid权限&#xff0c;这里只是刻意的制造出了一种存在提权的环境 首先我们先介绍一下find命令&#xff0c;find命令主要用来在Linux中查找文件使用&#xff0c;它可以进行最基础…

thinkphp 自定义错误页面

在访问无效的UI 这个效果不好&#xff0c;要改成自定义的 <?php namespace app\controller;class ErrorController {public function __call($method,$args){return error request!;} }之后就是提示

【蓝桥杯 第十三届省赛Java B组】真题训练(A - F)

目录 A、星期计算 - BigInteger B、山 - 暴力判断 字符串 C、字符统计 - 简单哈希 D、最少刷题数 - 排序 思维 二分 分情况讨论 &#xff08;1&#xff09;&#xff08;错误&#xff09;自写哈希表 &#xff08;2&#xff09;正解 E、求阶乘 - 数学思维 二分 F、…

Postman小白安装和注册入门教程

近期在复习Postman的基础知识&#xff0c;在小破站上跟着百里老师系统复习了一遍&#xff0c;也做了一些笔记&#xff0c;希望可以给大家一点点启发。 一&#xff09;安装 访问官网https://www.getpostman.com/downloads/&#xff0c;直接下载安装。 二&#xff09;注册和登录…

【python自动化】Playwright基础教程(六)事件操作③单击双击计数过滤截图JS注入

【python自动化】Playwright基础教程(六)事件操作③单击&双击&计数&过滤&截图&JS注入 本文目录 文章目录 【python自动化】Playwright基础教程(六)事件操作③单击&双击&计数&过滤&截图&JS注入playwright系列回顾前文代码点击 - click…

基于单片机智能输液器监控系统的设计

**单片机设计介绍&#xff0c; 基于单片机智能输液器监控系统的设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的智能输液器监控系统可以实现对输液过程的实时监测和控制&#xff0c;以下是一个基本的设计介绍&am…

简单地聊一聊Spring Boot的构架

本文由葡萄城技术团队发布。转载请注明出处&#xff1a;葡萄城官网&#xff0c;葡萄城为开发者提供专业的开发工具、解决方案和服务&#xff0c;赋能开发者。 前言 本文小编将详细解析Spring Boot框架&#xff0c;并通过代码举例说明每个层的作用。我们将深入探讨Spring Boot的…

二维码智慧门牌管理系统升级,实现综合运营可视化

文章目录 前言一、升级解决方案概述二、重点指标综合展示三、综合运营可视化 前言 随着科技的发展和城市化进程的加速&#xff0c;传统的门牌管理系统已经无法满足现代社会的需求。为了解决这一问题&#xff0c;一款二维码智慧门牌管理系统应运而生&#xff0c;为城市管理和运…

Nginx 使用笔记大全(唯一入口)

Linux服务器因为Nginx日志access.log文件过大项目无法访问 项目处于运行状态下无法访问&#xff0c;第一步查看磁盘状态 1、查看磁盘状态 df -h 2、查找100M以上的文件 find / -size 100M |xargs ls -lh 3、删除文件 rm -rf /usr/local/nginx/logs/access.log 4、配置nginx.…

类和对象(4):Date类.运算符重载 1

一、赋值运算符重载 1.1 运算符重载 运算符重载是具有特殊函数名的函数&#xff0c;函数名字为&#xff1a;关键词operator需要重载的运算符符号。 不能重载C/C中未出现的符号&#xff0c;如&#xff1a;operator。重载操作符必须有一个类类型参数。不能改变用于内置类型运算…

计算机毕业设计选题推荐-公共浴池微信小程序/安卓APP-项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…

【Redis】Zset有序集合

上一篇&#xff1a; Hash哈希类型 https://blog.csdn.net/m0_67930426/article/details/134382507?spm1001.2014.3001.5502 目录 Zadd Zrange Zcard Zcount Zrem set是一个无序且元素不可重复的集合 而Zset是一个有序的集合,集合里的每个元素都有一个评分&#xff08;…

为什么Android 手机这么慢?如何提高 Android 手机的运行速度

速印机&#xff08;理想、荣大等&#xff09;、复印机&#xff08;夏普、东芝、理光、佳能、震旦等全系列&#xff09;、打印机、扫描仪、传真机、多媒体教学一体机、交互式电子白板、报警器材、监控、竞业达监考设备及其它监考设备、听力考试设备、特种安防设备维护及维修。吴…

C++引用 引用做函数参数

一.引用的定义和语法 // 给a取别名为b int &b a; // 修改b的值&#xff0c;a的值也会被修改&#xff0c;因为他们都指向同一个内存空间 b 20; 二.引用的注意事项 1.引用必须初始化如 int&b; 是错误的&#xff0c;因为没有初始化。 2.引用在初始化后&#xff0c;不…

IT服务台与Microsoft集成

Microsoft Teams 旨在通过创建一个共享工作区&#xff0c;使组织中的协作更加轻松&#xff0c;用户可以在其中聊天、开会、共享文件和访问业务应用。为了实现这些数字工作空间的最大效率&#xff0c;这一点很重要&#xff0c;当出现问题时&#xff0c;IT服务台团队始终在前沿。…

RabbitMQ实战

文章目录 1、简介2、MQ优点缺点MQ的应用场景AMQP工作原理市面上常见的MQ 3、Linux安装RabbitMQ3.1 版本对应3.2 安装socat3.3 下载 Erlang/OTP、安装、验证 erlang方法一&#xff1a;1. 下载2. 将下载的Erlang服务上传到服务器上面3. 解压4. 编译erlang的依赖环境5. 安装Erlang…

简洁高效的微信小程序分页器封装实践

前言 在现今的移动应用开发中&#xff0c;微信小程序已经成为了一个备受欢迎的平台。然而&#xff0c;随着应用的复杂性增加&#xff0c;数据的管理和加载成为了一个问题。本文将探讨微信小程序中的一个关键概念&#xff1a;封装分页器&#xff0c;它是提升小程序性能和用户体验…

聚观早报 |滴滴发布Q3财报;小鹏G9连续销量排行第一

【聚观365】11月14日消息 滴滴发布Q3财报 小鹏G9连续销量排行第一 XREAL双11实现7倍增长 真我GT5 Pro真机图 2024年智能手机AI功能竞争激烈 滴滴发布Q3财报 滴滴在其官网发布2023年三季度业绩报告。报告显示&#xff0c;三季度滴滴实现总收入514亿元&#xff0c;同比增长…

④【数据查询】MySQL查询语句,拿来即用。

个人简介&#xff1a;Java领域新星创作者&#xff1b;阿里云技术博主、星级博主、专家博主&#xff1b;正在Java学习的路上摸爬滚打&#xff0c;记录学习的过程~ 个人主页&#xff1a;.29.的博客 学习社区&#xff1a;进去逛一逛~ MySQL查询操作 ④【数据查询】MySQL查询语句&a…

Docker 中的端口

Docker 中的端口 0.0.0.0:8080->80/tcp &#xff0c;主机&#xff08;即运行 Docker 的机器&#xff09;监听8080端口&#xff0c;如果有请求转发到容器的 80 端口上去。 详细解释一下&#xff1a; 0.0.0.0:8080->80/tcp &#xff1a;这是一个端口映射规则。 0.0.0.0:80…