当前位置: 首页 > 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 相当于通过这些点练成的线的圈起来的部分就是剩…...

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

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

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

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

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

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...