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

【3.1】贪心算法-解分发饼干

一、题目

        假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是, 每个孩子最多只能给一块饼干 对每个孩子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) 1 <= g.length <= 3*10^4
2) 0 <= s.length <= 3*10^4
3) 1 <= g[i], s[j] <= 2^31-1

二、解题思路

        贪心算法,亦称贪婪算法,是一种在解决问题时始终选择当前状态下最优解的策略。换言之,该算法并不追求全局最优,而是基于局部最优解的累积效果。

        在《算法导论》一书中,对贪心算法有如下阐述:贪心算法在每一步都做出当时认为最佳的选择,即始终采取局部最优的决策,期望这些局部最优选择能够导向全局最优解。

        针对本题,贪心算法尤为适用。题目要求尽可能多地满足孩子们的需求,由于饼干不可分割,因此我们可以采取一种策略,即让胃口较大的孩子食用较大的饼干,而胃口较小的孩子则食用较小的饼干。具体操作时,可以从胃口最小的孩子开始,尝试用最小的饼干来满足其需求,若无法满足,则逐步尝试更大的饼干,直至找到合适的饼干或遍历完所有饼干。

#include <iostream>
#include <vector>
#include <algorithm>int findContentChildren(std::vector<int>& g, std::vector<int>& s) {// 先对胃口值和饼干尺寸进行排序std::sort(g.begin(), g.end());std::sort(s.begin(), s.end());int count = 0;for (int j = 0; count < g.size() && j < s.size(); j++) {// 如果当前饼干能满足当前孩子的胃口值,count就加1,否则就继续查找更大的饼干if (g[count] <= s[j])count++;}return count;
}int main() {std::vector<int> g = {1, 2, 3}; // 孩子的胃口值std::vector<int> s = {1, 1};    // 饼干的尺寸int result = findContentChildren(g, s);std::cout << "满足的孩子数量: " << result << std::endl;return 0;
}

三、代码实现

        还一种方式就是先从最大的饼干开始,看一下能不能满足胃口最大的,如果不能满足就 找胃口稍微小一点是再试一下,如果还不能满足就一直找。代码实现如下:
#include <iostream>
#include <vector>
#include <algorithm>int findContentChildren(std::vector<int>& g, std::vector<int>& s) {// 先对胃口值和饼干尺寸进行排序std::sort(g.begin(), g.end());std::sort(s.begin(), s.end());int count = 0;int i = s.size() - 1;for (int j = g.size() - 1; i >= 0 && j >= 0; j--) {// 如果当前饼干能满足当前孩子的胃口值,count就加1,否则就继续查找胃口更小的孩子if (g[j] <= s[i]) {count++;i--;}}return count;
}int main() {std::vector<int> g = {1, 2, 3}; // 孩子的胃口值std::vector<int> s = {1, 1};    // 饼干的尺寸int result = findContentChildren(g, s);std::cout << "满足的孩子数量: " << result << std::endl;return 0;
}
贪心算法仅追求局部最优解,它能够界定某些问题的可行域,但无法确保解的最优性。由于贪心算法始终立足于局部视角,并未全面考量整体情况,因此在某些问题上应用贪心算法是适宜的,而在其他问题上则可能不适用。这些都需要针对具体问题进行具体分析。

相关文章:

【3.1】贪心算法-解分发饼干

一、题目 假设你是一位很棒的家长&#xff0c;想要给你的孩子们一些小饼干。但是&#xff0c; 每个孩子最多只能给一块饼干 。 对每个孩子i&#xff0c;都有一个 胃口值 g[i] &#xff0c;这是能让孩子们满足胃口的饼干的最小尺寸&#xff1b;并且每块饼干j&#xff0c;都有一个…...

解决 Error running ‘Application‘: Command line is too long.

一、项目场景&#xff1a; 运行刚拉取下来的项目代码&#xff0c;出现下面问题描述的错误提示。 二、问题描述 Error running Application: Command line is too long. Shorten command line for Application or also for Spring Boot default configuration? 翻译翻译&…...

衡量与归因将是Netflix程序化广告业务的首要任务

作者&#xff1a;刀客doc 8月20日&#xff0c;Netflix宣布今年上半年&#xff0c;品牌的招商收入同比增长了150%&#xff0c;广告主来自旅游、汽车、零售商、快餐和大众快消等行业。这一消息提振了资本市场对Netflix广告业务的信心&#xff0c;8月20日收盘创下每股 698.54 美元…...

关于如何在已有qt项目中添加该项目的单元测试工程

关于如何在已有qt项目中添加该项目的单元测试工程 新建一个子目录工程&#xff0c;把已有项目作为子工程添加进去&#xff0c;然后新建单元测试工程也作为子工程添加进去。单元测试项目要独立于实际项目工程&#xff0c;确保去掉测试项目后&#xff0c;实际项目仍可以正常运行…...

深度剖析数字媒体产业链的无限潜力与创新生态

在当今信息爆炸的时代&#xff0c;数字媒体产业链正以势不可挡的姿态展现出其令人瞩目的无限潜力与创新生态。 数字媒体的发展潜力简直无可限量。从在线视频的爆发式增长&#xff0c;到虚拟现实和增强现实技术带来的沉浸式体验&#xff0c;再到社交媒体平台上丰富多彩的内容创…...

集团数字化转型方案(十二)

集团数字化转型方案致力于通过构建一个集成化的数字平台&#xff0c;全面应用大数据分析、人工智能、云计算和物联网等前沿技术&#xff0c;推动业务流程、管理模式和决策机制的全面升级。该方案将从业务流程的数字化改造开始&#xff0c;优化资源配置&#xff0c;提升运营效率…...

Andrid异步更新UI:Handler(二)深入了解:Message你真的会创建?它是如何子线程和主线程通知?

目录 为什么会有HandlerHandler的原理&#xff0c;以及对象讲解主线程的loop在哪里&#xff0c;为什么主线程loop没有阻塞呢&#xff1f;Looper如何保证唯一Handler为什么会引发内存泄漏呢&#xff1f;Message应该如何创建它&#xff1f; 一、为什么会有Handler 线程分为主线…...

2025计算机毕设50条小众好做的Java题目【计算机毕设选题推荐】

随着2025年的到来&#xff0c;计算机专业的学生们又迎来了毕业设计的关键时刻。对于大多数学生来说&#xff0c;选择一个合适的毕业设计题目往往是一项艰巨的任务。本文旨在为那些正在为毕业设计题目烦恼的同学们提供一些灵感和建议&#xff0c;特别是针对使用Java技术栈的同学…...

day06_算法训练

一. Stream流 1.1 Stream流概述 概念: jdk1.8以后提供的新的API, 主要用于批量操作数据(集合的另外一种操作方式),代码非常简洁 流式处理思想: 2.2 Stream对象获取 1.单列集合的Stream流对象获取 2.双列集合的Stream流对象获取 3.数组的Stream流对象获取 4.散装数据的St…...

@SpringBootTest单元测试中报错:无法自动装配,找不到 ‘XXX‘ 类型的 Bean

一开始照着网上教程讲Springboot原理中的代码来copy写的↓ import com.google.gson.Gson; import com.itheima.pojo.Result; import org.junit.jupiter.api.Test; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.boot.test.cont…...

nodemon学习(一)简介、安装、配置、使用

nodemon用来监视node.js应用程序中的任何更改并自动重启服务,非常适合用在开发环境中。以前&#xff0c;我们开发一个node后端服务时&#xff0c;每次更改文件&#xff0c;均需重启一下&#xff0c;服务才能生效。这使我们的开发效率降低了很多。nodemon的出现&#xff0c;可以…...

【Qt从摄像头视频中获取数据】

有时候需要在视频上画图&#xff0c;所以需要能获取到每一帧视频数据。 以前从视频文件或视频流中得到帧&#xff0c;一般都是使用qt ffmpeg或qt vlc。 qt对显示处理视频大体有以下方法&#xff1a; QMediaPlayer QVideoWidget 这种方法只适合简单的显示视频功能&#xff…...

视频截取中的UI小组件

引言 视频截取在社交类 APP 中十分常见。有了上传视频的功能&#xff0c;就不可避免地需要提供截取和编辑的选项。如果我们过度依赖第三方库&#xff0c;项目的代码可能会变得异常臃肿&#xff0c;因为这些库往往包含许多我们用不到的功能&#xff0c;而且它们的 UI 样式和功能…...

java设计模式--结构型模式

结构性模式&#xff1a;适配器模式、桥接模式、装饰模式、组合模式、外观模式、享元模式、代理模式 适配器模式 适配器模式&#xff08;Adapter Pattern&#xff09; 充当两个不兼容接口之间的桥梁&#xff0c;属于结构型设计模式。目的是将一个类的接口转换为另一个接口&am…...

消息中间件:Kafka消息丢失与堆积问题分析与解决方案

消息中间件&#xff1a;Kafka消息丢失与堆积问题分析与解决方案 Kafka作为分布式消息系统&#xff0c;广泛应用于实时数据流处理、大数据分析等领域。然而&#xff0c;在实际应用中&#xff0c;Kafka可能会面临消息丢失和消息堆积的问题&#xff0c;这些问题如果得不到有效处理…...

mac终端代理配置指南

终端代理配置指南 在 macOS 中&#xff0c;你可以通过几种不同的方法来配置终端代理。这里介绍两种常见的设置方式&#xff1a;使用 alias 和 shell 函数。 方法 1&#xff1a;使用 Alias 配置代理 打开终端配置文件 默认情况下&#xff0c;macOS 终端使用的是 zsh。如果你的系…...

mbedTLS生成客户端,服务端密钥及CA证书

1. mbedTLS源码&#xff1a;https://github.com/Mbed-TLS/mbedtls.git 2. 生成步骤&#xff1a; 2.1 编译上述源码 2.2 生成CA私钥和自签名证书&#xff1a; 进入编译的build目录&#xff0c;比如&#xff1a;/mbedtls-development/build# 2.2.1生成CA私钥 执行下面的命令&…...

如何有效应对突发技术故障:以网易云音乐为例

引言 在互联网行业&#xff0c;任何一个在线服务都可能遭遇突发的技术故障。这些故障不仅影响用户体验&#xff0c;还可能对公司的品牌形象造成损害。因此&#xff0c;如何快速响应并高效解决这些问题成为了每一个开发团队的重要课题。本文将以网易云音乐在2024年8月19日下午遭…...

上传文件到github仓库

REF: https://blog.csdn.net/litianxiang_kaola/article/details/74075151 已有repository&#xff0c;往仓库里更新内容 点击gitlab里的clone 在git bash中使用git clone&#xff0c;这个时候会将网上的仓库下载到本地&#xff0c;你可以把想要更新的内容直接拖到仓库里 …...

clip-path实现图片边角的裁剪

img {clip-path: polygon(0 7px,7px 0,calc(100% - 20px) 0,100% 20px,100% 100%,16px 100%,0 calc(100% - 16px));}每一个逗号隔开的就是路径坐标 左上角的两个点 0 7px &#xff0c;7px 0 右上角 calc(100% - 20px) 0,100% 20px 相当于通过这些点练成的线的圈起来的部分就是剩…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...