【算法思考记录】力扣2952. 需要添加的硬币的最小数量【C++,思路挖掘,贪心与证明】
原题链接
文章目录
- 需要添加的硬币的最小数量:贪心算法实现
- 题目概述
- 示例分析
- 关键思路分析
- 贪心算法的优化选择证明
- 案例推演与算法实现
- C++ 实现
- 结论
需要添加的硬币的最小数量:贪心算法实现
题目概述
在这个困难难度的算法题中,我们要解决的问题是确定在给定一系列硬币面值的情况下,为了使[1, target]区间内的每个整数都可以由这些硬币的某种组合表示出来,需要向数组中添加的最小数量的硬币。
示例分析
- 示例 1:
- 输入:
coins = [1,4,10], target = 19 - 输出:
2(需要添加面值2和8的硬币)
- 输入:
- 示例 2:
- 输入:
coins = [1,4,10,5,7,19], target = 19 - 输出:
1(仅需要添加面值为2的硬币)
- 输入:
- 示例 3:
- 输入:
coins = [1,1,1], target = 20 - 输出:
3(需要添加面值为4、8和16的硬币)
- 输入:
关键思路分析
解决问题的关键在于贪心算法的应用。核心思想是对于每个无法直接凑出的金额x,添加面值为x的硬币以达到最优效果。通过这种方法,我们可以逐步构建出一个能够覆盖[1, target]区间的硬币集合。
贪心算法的优化选择证明
我们可以根据这个案例抽象出普遍性做法。如果要靠添加硬币的方式,才能凑出金额x,如果此时已经能凑出[1, s]的金额(x = s + 1),我们应该选择添加面值x,以得到更优结果。
证明:
选择1. 如果添加小于x的面值:
比如说添加面值small,此时面值small与金额x - small也可以凑出金额x。增加了面值small后,[small + 1, small + 2, small + 3…small + s]这些金额都可以通过与前面的金额相加凑出,不妨想象一个区间[small + 1, small + s],因为x - small是位于[1, s]之中的(x = s + 1,且small至少为1,因此x - small至少为x - 1 = s),所以现在可以凑出x了,还可以凑出[x, small + s]中的金额,结合原来的[1, s],我们可以凑出[1, small + s]的金额。
选择2. 添加面值x:
增加了面值x后,[x + 1, x + 2, x + 3…x + s]这些金额都可以通过与前面的金额相加凑出,因此可以结合前面的区间凑出[1, x + s]。
选择3. 添加大于x的面值:
如果添加面值x + 1,原先能凑出的区间为[1, s],因为x = s + 1,x + 1 = s + 2,此时依然无法凑出金额x,因为区间没有覆盖到x这个点上,因此这个方案无效。
综合以上3个选择,我们可以比对[1, small + s]和[1, x + s],因为small < x,所以毫无疑问选择x是最优做法。
案例推演与算法实现
[案例推演与算法实现的内容保持不变]
C++ 实现
实现中,首先对硬币进行排序,然后遍历每个硬币,同时维护一个变量x表示当前考虑的金额,以及一个变量s表示目前可以凑出的最大金额。若当前硬币面值大于x,则添加面值为x的硬币,直到可以凑出当前考虑的硬币面值为止。这个过程一直重复,直到可以凑出目标金额target。
class Solution {
public:int minimumAddedCoins(vector<int>& coins, int target) {sort(coins.begin(), coins.end());long long ans = 0, s = 0, x = 1;for (auto c : coins) {if (c > x) {while (c > x) {s = s + x;x = s + 1;ans++;}}s = s + c;x = s + 1;}while (s < target) {s = s + x;x = s + 1;ans++; }return ans;}
};
结论
通过贪心算法的应用,我们可以有效地解决这个算法问题,确保在给定硬币面值的情况下,以最小的硬币数量覆盖[1, target]的所有整数。
相关文章:
【算法思考记录】力扣2952. 需要添加的硬币的最小数量【C++,思路挖掘,贪心与证明】
原题链接 文章目录 需要添加的硬币的最小数量:贪心算法实现题目概述示例分析 关键思路分析贪心算法的优化选择证明案例推演与算法实现 C 实现结论 需要添加的硬币的最小数量:贪心算法实现 题目概述 在这个困难难度的算法题中,我们要解决的…...
用友NC JiuQiClientReqDispatch反序列化RCE漏洞复现
0x01 产品简介 用友NC是一款企业级ERP软件。作为一种信息化管理工具,用友NC提供了一系列业务管理模块,包括财务会计、采购管理、销售管理、物料管理、生产计划和人力资源管理等,帮助企业实现数字化转型和高效管理。 0x02 漏洞概述 用友 NC JiuQiClientReqDispatch 接口存在…...
Linux:docker镜像的创建(5)
1.基于已有镜像创建 步骤: 1.将原始镜像加入容器并运行 2.在原始镜像中部署各种服务 3.退出容器 4.使用下面命令将容器生成新的镜像 现在我们在这个容器里做了一些配置,我们要把他做成自己镜像 docker commit -m "centos7_123" -a "tarr…...
数据结构与算法-D2D3线性表之顺序表
线性表:包含若干数据元素的一个线性序列,特征如下: 1)对非空表,a0是表头,无前驱; 2)an-1是表尾,无后继; 3)其他元素仅且仅有一个前驱,…...
01_W5500简介
目录 W5500简介: 芯片特点: 全硬件TCPIP协议栈: 引脚分布: W5500简介: W5500是一款高性价比的以太网芯片,其全球独一无二的全硬件TCPIP协议栈专利技术,解决了嵌入式以太网的接入问题,简单易用ÿ…...
异常 Exception 练习题 (未完成)
异常 Exception 练习题 try-catch异常处理1234 异常1(没有自己写)234 try-catch异常处理 1 class Exception01 {public static int method() {try {String[] names new String[3];//String[]数组if (names[1].equals("tom")) {//NullPointe…...
Linux系统编程:并发与信号总结
并发 并发是指两个或多个同时独立进行的活动。在计算机系统中,并发指的是同一个系统中多个独立活动同时进行,而非依次进行。 并发在计算机系统中的表现: 一个时间段中有几个程序都处于已启动运行到运行完毕之间,且这几个程序都是…...
Jmeter 接口-加密信息发送(一百九十九)
方式1:使用函数助手 比如MD5加密方式: 如图,需要对${user}进行MD5加密 1、打开函数助手,找到MD5,输入需要加密的值 2、将${__MD5(${user},)}放到请求中 3、查看请求,请求成功 方式2:导入jar包…...
微信小程序nodejs+vue+uniapp视力保养眼镜店连锁预约系统
作为一个视力保养连锁预约的网络系统,数据流量是非常大的,所以系统的设计必须满足使用方便,操作灵活的要求。所以在设计视力保养连锁预约系统应达到以下目标: (1)界面要美观友好,检索要快捷简易…...
掌握Vue侦听器(watch)的应用
文章目录 🍁watch 的优缺点🍂Watch 优点🍂Watch 缺点 🍁watch 的用法🍂对象式 watch🍂函数式 watch 🍁代码示例🍂监听基本数据类型🍂监听复杂数据类型(Object…...
SAP-PP:PP顾问管理系统的相关建议
本博客将探讨生产计划领域的控制要点。这将有助于减少仓库库存不准确情况,因为库存不准确会导致实物库存、发货、成本核算和计划方面出现许多效率低下的问题。 在物料主数据关键字段中,必须配置计划交货时间、GR处理时间、内部生产时间、计划交货时间&a…...
Unity资源路径与读取
Unity资源路径有: 1、StreamingAssets:只读,一般用于存放应用程序运行时需要加载的资源文件,可以通过Application.streamingAssetsPath来获取。 2、PersistentDataPath:可读写,一般用于存放应用程序运行时…...
“大+小模型”赋能油气行业高质量发展
近日,中国石油石化科技创新大会暨新技术成果展在北京盛大举行,九章云极DataCanvas公司携油气行业一站式AI综合解决方案重磅亮相,充分展示了公司助推油气行业实现AI规模化应用深厚的AI技术实力和领先的AI应用水准,赢得了行业专家和…...
【win32_004】字符串处理函数
StringCbPrintf 函数 (strsafe.h):格式化字符串 STRSAFEAPI StringCbPrintf([out] STRSAFE_LPSTR pszDest,//目的缓冲区 LPSTR指针或者数组[in] size_t cbDest,//目的缓冲区大小[in] STRSAFE_LPCSTR pszFormat,//格式 例如: TEXT("%d&…...
如果不小心修改了按钮的名字并且忘记了原名字
出现上述情况,可以右边点击转到代码,注释掉问题行,此页的设计界面就恢复了。...
opencv阈值处理
阈值处理 二值化 自适应阈值 OTSU二值化...
html之JS
1、JS的引入 <!-- 内嵌 --><!-- <script>alert(4)</script> --><!-- 外引 --><!-- 内嵌和外引同时有的时候,内嵌被覆盖 --><script src"js/index.js" defer></script>//defer 延迟执行 2、js的变量使用…...
SQL Server的安装和首个库的创建
一、熟悉SQL Server的安装环境; 1.安装Microsoft的数据库管理系统SQL Server 2022 先把SQL Server 2022下载好后进行解压后出现以下界面然后点击基本进行安装 然后会出现以下界面: 一步步按照提示往下走即可,把SQL Server 2022安装完成后再…...
STM32下载程序的五种方法
刚开始学习 STM32 的时候,很多小伙伴满怀热情买好了各种设备,但很快就遇到了第一个拦路虎——如何将写好的代码烧进去这个黑乎乎的芯片~ STM32 的烧录方式多样且灵活,可以根据实际需求选择适合的方式来将程序烧录到芯片中。本文将…...
基于springboot + vue大学生竞赛管理系统
qq(2829419543)获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:springboot 前端:采用vue技术开发 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
