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

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

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;}
};

相关文章:

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

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

vue项目路由使用history模式,nginx配置,刷新页面显示404

需要在配置项中添加 try_files $uri $uri/ /index.html;...

redis的redis.service配置

在CentOS中&#xff0c;可以使用以下步骤配置redis.service&#xff1a; 创建redis用户和组 在终端中执行以下命令&#xff1a; 复制插入 sudo useradd -r -s /bin/false redis复制插入 这将创建一个名为redis的系统用户&#xff0c;并禁止该用户登录系统。 安装Redis 在…...

高频SQL50题(基础版)-3

文章目录 主要内容一.SQL练习题1.1174-即时食物配送代码如下&#xff08;示例&#xff09;: 2.550-游戏玩法分析代码如下&#xff08;示例&#xff09;: 3.2356-每位教师所教授的科目种类的数量代码如下&#xff08;示例&#xff09;: 4.1141-查询近30天活跃用户数代码如下&…...

OpenMMlab导出yolov3模型并用onnxruntime和tensorrt推理

导出onnx文件 直接使用脚本 import torch from mmdet.apis import init_detector, inference_detectorconfig_file ./configs/yolo/yolov3_mobilenetv2_8xb24-ms-416-300e_coco.py checkpoint_file yolov3_mobilenetv2_mstrain-416_300e_coco_20210718_010823-f68a07b3.pth…...

单链表的插入删除

#include <iostream>#include <stdio.h> #include <stdlib.h>using namespace std;//带头指针的单链表typedef struct LNode{int data;struct LNode *next;}LNode, *LinkList;bool InitList(LinkList &L){L (LNode *) malloc(sizeof(LNode));if(L NUL…...

github使用手册

核心代码 配置用户名/邮箱 best practice git init #在本地初始化一个仓库 git add . #将当前目录所有的文件加入&#xff08;注意这里是加入&#xff09;到缓存区 git commit -m "xxx" #将当前缓存区里的内容提交到本地仓库 git remote add <remote_rep_name&g…...

怎样做ChatGPT应用开发?

要开发一个基于ChatGPT的应用&#xff0c;你可以按照以下步骤进行&#xff1a; 步骤1&#xff1a;了解ChatGPT API ChatGPT的使用通常通过API进行。你需要了解ChatGPT的API文档&#xff0c;包括如何进行请求、API端点、身份验证等信息。在开发之前&#xff0c;确保你已经获取了…...

漏洞-任意账号注册

一漏洞介绍 1.未验证邮箱/手机号 情景&#xff1a;应用为了方便用户记录用户名&#xff0c;使用邮箱和手机号作为用户名&#xff08;因此很多应用在注册的时候就要求用户填写&#xff0c;多数时候都会给用户发送激活信息&#xff0c;激活后才能登录&#xff09; 缺陷&#xff…...

一个关于jdbc操作mysql和java基础练手的通讯录管理系统小项目

首先 : 整个项目的项目结构为 : 1.第一步先导入数据库的驱动&#xff0c;我的mysql数据库是8.0以上版本&#xff0c;然后导入的驱动就是8.0.16版本的jar包&#xff1b; 1.JdbcBase : JDBC基础操作封装成了JdbcBase类,在里面先静态定义了数据库连接对象和DQL查询结果&#x…...

C++用条件变量实现线程安全的queue容器

#include <queue> #include <memory> #include <mutex> #include <condition_variable> template<typename T> class threadsafe_queue { private:mutable std::mutex mut; // 1 互斥量必须是可变的 std::queue<T> data_queue;std::condi…...

EDA实验-----3-8译码器设计(QuartusII)

目录 一. 实验目的 二. 实验仪器 三. 实验原理及内容 1.实验原理 2.实验内容 四&#xff0e;实验步骤 五. 实验报告 六. 注意事项 七. 实验过程 1.创建Verilog文件&#xff0c;写代码 ​编辑 2.波形仿真 3.连接电路图 4.烧录操作 一. 实验目的 学会Verilog HDL的…...

NFTScan | 11.06~11.12 NFT 市场热点汇总

欢迎来到由 NFT 基础设施 NFTScan 出品的 NFT 生态热点事件每周汇总。 周期&#xff1a;2023.11.06~ 2023.11.12 NFT Hot News 01/ 《辛普森一家》提及 NFT 及区块链&#xff0c;相关 NFT 地板价涨至 0.35 ETH 11 月 6 日&#xff0c;据 Coindesk 报道&#xff0c;美国时间周…...

2022年12月 Python(五级)真题解析#中国电子学会#全国青少年软件编程等级考试

Python等级考试(1~6级)全部真题・点这里 一、单选题(共25题,每题2分,共50分) 第1题 下面哪个语句正确定义了元组类型数据tuple1?( ) A: tuple1=[“张三”,“李四”,“王五”] B: tuple1=(“张三”;“李四”;“王五”) C: tuple1=(张三,李四,王五) D: tuple1=(“张三…...

第三章 将对象映射到 XML - 使用列表或数组定义的属性

文章目录 第三章 将对象映射到 XML - 使用列表或数组定义的属性使用列表或数组定义的属性%ListOfDataTypes 或 %ArrayOfDataTypes 类型的属性%ListOfObjects 或 %ArrayOfObjects 类型的属性 第三章 将对象映射到 XML - 使用列表或数组定义的属性 使用列表或数组定义的属性 对…...

C/S架构学习之基于TCP的本地通信(客户机)

基于TCP的本地通信&#xff08;客户机&#xff09;&#xff1a;创建流程&#xff1a;一、创建字节流式套接字&#xff08;socket函数&#xff09;&#xff1a; int sock_fd socket(AF_LOCAL,SOCK_STREAM,0);二、创建客户机和服务器的本地网络信息结构体并填充客户机和服务器本…...

CCF 备忘

一、不错的网站 CCF CCSP 竞赛历年资料 官网 http://118.190.20.162/home.page 二、基础套路 循环输入 数组标记法&#xff08;数组下标-数值 的映射&#xff09; 两个矩阵相乘 map<long long, map<long long, long long> > ans; for(int i1;i<d;i){for(int…...

Spring Framework中的依赖注入:构造器注入 vs. Setter注入

前言 构造器注入和Setter注入是依赖注入&#xff08;Dependency Injection&#xff0c;DI&#xff09;中两种常见的方式&#xff0c;用于向一个对象注入其所依赖的其他对象或数值。这两种注入方式有各自的特点和用途。 构造器注入&#xff08;Constructor Injection&#xff…...

Java学习之路 —— API篇

文章目录 前言Object类2. Objects类3. 包装类4. StringBuilder和StringBuffer5. StringJoiner6. Math7. System8. JDK8开始新增的日期、时间9. Arrays10. Lambda表达式11. 方法引用 前言 其实转语言来说&#xff0c;语法都比较简单&#xff0c;花个三天就会了&#xff0c;但最…...

Windows下安装Anaconda5.3.1+Python3.8+TensorFlow2.13.0-CPU版本总结

Python3.8安装可以参考博文https://janus.blog.csdn.net/article/details/55274849 进行安装即可。 【1】Anaconda 清华的开源软件镜像站&#xff1a;https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/下载&#xff0c;这里选择的是5.3.1版本。 然后正常安装就可以&am…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...