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

【算法思考记录】力扣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++,思路挖掘,贪心与证明】

原题链接 文章目录 需要添加的硬币的最小数量&#xff1a;贪心算法实现题目概述示例分析 关键思路分析贪心算法的优化选择证明案例推演与算法实现 C 实现结论 需要添加的硬币的最小数量&#xff1a;贪心算法实现 题目概述 在这个困难难度的算法题中&#xff0c;我们要解决的…...

用友NC JiuQiClientReqDispatch反序列化RCE漏洞复现

0x01 产品简介 用友NC是一款企业级ERP软件。作为一种信息化管理工具,用友NC提供了一系列业务管理模块,包括财务会计、采购管理、销售管理、物料管理、生产计划和人力资源管理等,帮助企业实现数字化转型和高效管理。 0x02 漏洞概述 用友 NC JiuQiClientReqDispatch 接口存在…...

Linux:docker镜像的创建(5)

1.基于已有镜像创建 步骤&#xff1a; 1.将原始镜像加入容器并运行 2.在原始镜像中部署各种服务 3.退出容器 4.使用下面命令将容器生成新的镜像 现在我们在这个容器里做了一些配置&#xff0c;我们要把他做成自己镜像 docker commit -m "centos7_123" -a "tarr…...

数据结构与算法-D2D3线性表之顺序表

线性表&#xff1a;包含若干数据元素的一个线性序列&#xff0c;特征如下&#xff1a; 1&#xff09;对非空表&#xff0c;a0是表头&#xff0c;无前驱&#xff1b; 2&#xff09;an-1是表尾&#xff0c;无后继&#xff1b; 3&#xff09;其他元素仅且仅有一个前驱&#xff0c;…...

01_W5500简介

目录 W5500简介&#xff1a; 芯片特点: 全硬件TCPIP协议栈: 引脚分布&#xff1a; W5500简介&#xff1a; W5500是一款高性价比的以太网芯片&#xff0c;其全球独一无二的全硬件TCPIP协议栈专利技术&#xff0c;解决了嵌入式以太网的接入问题&#xff0c;简单易用&#xff…...

异常 Exception 练习题 (未完成)

异常 Exception 练习题 try-catch异常处理1234 异常1&#xff08;没有自己写&#xff09;234 try-catch异常处理 1 class Exception01 {public static int method() {try {String[] names new String[3];//String[]数组if (names[1].equals("tom")) {//NullPointe…...

Linux系统编程:并发与信号总结

并发 并发是指两个或多个同时独立进行的活动。在计算机系统中&#xff0c;并发指的是同一个系统中多个独立活动同时进行&#xff0c;而非依次进行。 并发在计算机系统中的表现&#xff1a; 一个时间段中有几个程序都处于已启动运行到运行完毕之间&#xff0c;且这几个程序都是…...

Jmeter 接口-加密信息发送(一百九十九)

方式1&#xff1a;使用函数助手 比如MD5加密方式&#xff1a; 如图&#xff0c;需要对${user}进行MD5加密 1、打开函数助手&#xff0c;找到MD5&#xff0c;输入需要加密的值 2、将${__MD5(${user},)}放到请求中 3、查看请求&#xff0c;请求成功 方式2&#xff1a;导入jar包…...

微信小程序nodejs+vue+uniapp视力保养眼镜店连锁预约系统

作为一个视力保养连锁预约的网络系统&#xff0c;数据流量是非常大的&#xff0c;所以系统的设计必须满足使用方便&#xff0c;操作灵活的要求。所以在设计视力保养连锁预约系统应达到以下目标&#xff1a; &#xff08;1&#xff09;界面要美观友好&#xff0c;检索要快捷简易…...

掌握Vue侦听器(watch)的应用

文章目录 &#x1f341;watch 的优缺点&#x1f342;Watch 优点&#x1f342;Watch 缺点 &#x1f341;watch 的用法&#x1f342;对象式 watch&#x1f342;函数式 watch &#x1f341;代码示例&#x1f342;监听基本数据类型&#x1f342;监听复杂数据类型&#xff08;Object…...

SAP-PP:PP顾问管理系统的相关建议

本博客将探讨生产计划领域的控制要点。这将有助于减少仓库库存不准确情况&#xff0c;因为库存不准确会导致实物库存、发货、成本核算和计划方面出现许多效率低下的问题。 在物料主数据关键字段中&#xff0c;必须配置计划交货时间、GR处理时间、内部生产时间、计划交货时间&a…...

Unity资源路径与读取

Unity资源路径有&#xff1a; 1、StreamingAssets&#xff1a;只读&#xff0c;一般用于存放应用程序运行时需要加载的资源文件&#xff0c;可以通过Application.streamingAssetsPath来获取。 2、PersistentDataPath&#xff1a;可读写&#xff0c;一般用于存放应用程序运行时…...

“大+小模型”赋能油气行业高质量发展

近日&#xff0c;中国石油石化科技创新大会暨新技术成果展在北京盛大举行&#xff0c;九章云极DataCanvas公司携油气行业一站式AI综合解决方案重磅亮相&#xff0c;充分展示了公司助推油气行业实现AI规模化应用深厚的AI技术实力和领先的AI应用水准&#xff0c;赢得了行业专家和…...

【win32_004】字符串处理函数

StringCbPrintf 函数 (strsafe.h)&#xff1a;格式化字符串 STRSAFEAPI StringCbPrintf([out] STRSAFE_LPSTR pszDest,//目的缓冲区 LPSTR指针或者数组[in] size_t cbDest,//目的缓冲区大小[in] STRSAFE_LPCSTR pszFormat,//格式 例如&#xff1a; TEXT("%d&…...

如果不小心修改了按钮的名字并且忘记了原名字

出现上述情况&#xff0c;可以右边点击转到代码&#xff0c;注释掉问题行&#xff0c;此页的设计界面就恢复了。...

opencv阈值处理

阈值处理 二值化 自适应阈值 OTSU二值化...

html之JS

1、JS的引入 <!-- 内嵌 --><!-- <script>alert(4)</script> --><!-- 外引 --><!-- 内嵌和外引同时有的时候&#xff0c;内嵌被覆盖 --><script src"js/index.js" defer></script>//defer 延迟执行 2、js的变量使用…...

SQL Server的安装和首个库的创建

一、熟悉SQL Server的安装环境&#xff1b; 1.安装Microsoft的数据库管理系统SQL Server 2022 先把SQL Server 2022下载好后进行解压后出现以下界面然后点击基本进行安装 然后会出现以下界面&#xff1a; 一步步按照提示往下走即可&#xff0c;把SQL Server 2022安装完成后再…...

STM32下载程序的五种方法

刚开始学习 STM32 的时候&#xff0c;很多小伙伴满怀热情买好了各种设备&#xff0c;但很快就遇到了第一个拦路虎——如何将写好的代码烧进去这个黑乎乎的芯片&#xff5e; STM32 的烧录方式多样且灵活&#xff0c;可以根据实际需求选择适合的方式来将程序烧录到芯片中。本文将…...

基于springboot + vue大学生竞赛管理系统

qq&#xff08;2829419543&#xff09;获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;springboot 前端&#xff1a;采用vue技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xf…...

C++的std--ranges算法自定义比较器与等价关系在集合操作中的运用

C20引入的std::ranges库为算法操作带来了革命性改进&#xff0c;其中自定义比较器与等价关系的灵活运用&#xff0c;显著提升了集合操作的表达能力。通过精确控制元素间的比较逻辑&#xff0c;开发者能够实现更复杂的业务需求&#xff0c;例如处理自定义对象集合或实现非标准排…...

ArcGIS Desktop绘图工具条实战:从基础图形到专业地图注记的进阶指南

1. ArcGIS绘图工具条初探&#xff1a;你的地图设计起点 第一次打开ArcGIS Desktop的绘图工具条时&#xff0c;我就像拿到了一盒全新的彩色铅笔。这个看似简单的工具条&#xff0c;实际上包含了从基础绘图到专业地图注记的全套功能。绘图工具条位于软件界面顶部&#xff0c;右键…...

3大核心功能:让iOS推送调试效率提升10倍的SmartPush工具全解析

3大核心功能&#xff1a;让iOS推送调试效率提升10倍的SmartPush工具全解析 【免费下载链接】SmartPush SmartPush,一款iOS苹果远程推送测试程序,Mac OS下的APNS工具APP,iOS Push Notification Debug App 项目地址: https://gitcode.com/gh_mirrors/smar/SmartPush 一、问…...

能源监控项目避坑指南:为什么DLT645电表直连Modbus系统会失败?

能源监控项目避坑指南&#xff1a;为什么DLT645电表直连Modbus系统会失败&#xff1f; 在智慧能源项目的实施过程中&#xff0c;数据采集的可靠性直接关系到整个系统的运行效果。许多项目团队在遇到DLT645规约电表与Modbus系统对接时&#xff0c;往往会尝试直接连接&#xff0c…...

UniAppX项目数据可视化升级:用lime-echart + ECharts打造高性能图表(从Vue2/Vue3到uni-app-x全流程)

UniAppX高性能数据可视化实战&#xff1a;lime-echart与ECharts的深度整合指南 当移动端数据可视化需求遭遇性能瓶颈时&#xff0c;UniAppX框架与lime-echart的组合正在成为技术决策者的新选择。本文将揭示如何在不同技术栈中实现图表渲染性能的突破性提升&#xff0c;从原理剖…...

深入解析Golang中的占位符:%w、%v、%s的应用与最佳实践

1. Golang占位符基础入门 刚开始接触Golang时&#xff0c;fmt包里的那些百分号开头的占位符确实让我有点懵。记得第一次看到%s、%v、%w这些符号时&#xff0c;我还以为是什么特殊运算符。后来在实际项目中用多了才发现&#xff0c;这些看似简单的占位符&#xff0c;其实是Gola…...

著名学者、顶尖大学教授近期失联

点击下方卡片&#xff0c;关注“CVer”公众号AI/CV重磅干货&#xff0c;第一时间送达点击进入—>【顶会/顶刊】投稿交流群添加微信号&#xff1a;CVer2233&#xff0c;小助手拉你进群&#xff01;扫描下方二维码&#xff0c;加入CVer学术星球&#xff01;可以获得最新顶会/顶…...

Obsidian Local Images Plus 终极指南:如何一键解决所有本地图片管理难题

Obsidian Local Images Plus 终极指南&#xff1a;如何一键解决所有本地图片管理难题 【免费下载链接】obsidian-local-images-plus This repo is a reincarnation of obsidian-local-images plugin which main aim was downloading images in md notes to local storage. 项…...

OpenClaw量化对比:Qwen3.5-4B-Claude-4.6-Opus-Reasoning-Distilled-GGUF不同精度版本的自动化任务表现

OpenClaw量化对比&#xff1a;Qwen3.5-4B-Claude-4.6-Opus-Reasoning-Distilled-GGUF不同精度版本的自动化任务表现 1. 测试背景与实验设计 去年在开发一个自动化文档处理流程时&#xff0c;我发现OpenClaw的任务成功率与底层模型量化精度密切相关。当时使用Q8版本处理Excel文…...

Mojo 1.2正式版发布后,Python互操作API发生3处破坏性变更——紧急迁移指南与向下兼容降级方案(含自动转换脚本)

第一章&#xff1a;Mojo 1.2互操作API破坏性变更全景概览Mojo 1.2 版本对与 Python、C/C 及系统原生库的互操作接口进行了深度重构&#xff0c;核心目标是提升类型安全性和运行时性能&#xff0c;但由此引入了多项不兼容的破坏性变更。开发者在升级至 1.2 时必须审慎评估现有绑…...