当前位置: 首页 > 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…...

从教程到实战:在快马平台部署企业级openclaw数据采集与监控系统

今天想和大家分享一个实战经验&#xff1a;如何把openclaw这个数据采集工具从教程变成真正的企业级应用。最近我在InsCode(快马)平台上完整走通了从开发到部署的全流程&#xff0c;整个过程比想象中顺畅很多。 任务调度器的实现 首先需要解决的是任务调度问题。传统教程里可能…...

终极指南:如何从零开始打造你的第一台六足机器人

终极指南&#xff1a;如何从零开始打造你的第一台六足机器人 【免费下载链接】hexapod 项目地址: https://gitcode.com/gh_mirrors/hexapod5/hexapod 你是否梦想过亲手制作一台能够灵活行走、稳定爬行的六足机器人&#xff1f;想要体验机器人制作的乐趣&#xff0c;却担…...

D-Net:动态大内核与特征融合如何革新三维医学影像分割?

1. 为什么医学影像分割需要动态大内核&#xff1f; 医学影像分割就像给CT或MRI照片上的器官、肿瘤画精确边界线。传统方法像用固定倍数的放大镜观察——要么看不清细节&#xff08;小内核&#xff09;&#xff0c;要么错过整体结构&#xff08;大内核&#xff09;。我在处理腹…...

UE5场景过曝/白屏排查指南:从后期处理体积到项目设置的实战修复

1. 当UE5场景变成"雪盲症"时该怎么办&#xff1f; 第一次打开UE5项目看到白茫茫一片的时候&#xff0c;我差点以为显卡烧了。这种场景过曝现象就像在雪山没戴墨镜&#xff0c;所有细节都被强光吞噬。新手遇到这种情况别慌&#xff0c;我整理了从"急救措施"…...

Stable Diffusion像素艺术工作站:Pixel Fashion Atelier支持LoRA在线热切换

Stable Diffusion像素艺术工作站&#xff1a;Pixel Fashion Atelier支持LoRA在线热切换 1. 像素时装锻造坊简介 Pixel Fashion Atelier是一款基于Stable Diffusion与Anything-v5的图像生成工作站&#xff0c;专为像素艺术创作而设计。与传统AI工具不同&#xff0c;它采用了复…...

Word自动编号的隐藏玩法:用题注和交叉引用,打造能“自我修复”的智能文档

Word文档工程化&#xff1a;构建自动编号与交叉引用的智能系统 在技术文档撰写过程中&#xff0c;最令人头疼的莫过于图表编号的维护。当你在200页的文档中插入新图表时&#xff0c;手动编号意味着要逐个修改后续所有编号和引用——这种痛苦只有经历过的人才懂。但很少有人意识…...

OFA模型微调实战:适配特定领域的小样本学习

OFA模型微调实战&#xff1a;适配特定领域的小样本学习 用最少的数据&#xff0c;让通用大模型听懂你的专业语言 1. 引言&#xff1a;当通用模型遇到专业领域 你有没有遇到过这样的情况&#xff1a;一个在通用场景下表现优秀的AI模型&#xff0c;一到你的专业领域就"水土…...

用 OpenAI Codex 打造你的 AI 结对编程助手

用 OpenAI Codex 打造你的 AI 结对编程助手 告别重复劳动&#xff0c;让 AI 直接帮你写代码、修 Bug、跑测试 在 AI 编程工具层出不穷的今天&#xff0c;OpenAI Codex 依然是许多开发者心目中的“神器”。与普通的代码补全工具不同&#xff0c;Codex 是一款终端原生的 AI 编程助…...

Spring PetClinic实战解析:从单体应用到云原生部署的5大架构亮点

Spring PetClinic实战解析&#xff1a;从单体应用到云原生部署的5大架构亮点 【免费下载链接】spring-petclinic A sample Spring-based application 项目地址: https://gitcode.com/gh_mirrors/sp/spring-petclinic 你是否遇到过这样的困境&#xff1a;在学习Spring框架…...

高效获取数字资源工具:Internet Archive下载器全方位应用指南

高效获取数字资源工具&#xff1a;Internet Archive下载器全方位应用指南 【免费下载链接】internet_archive_downloader A chrome/firefox extension that download books from Internet Archive(archive.org) and HathiTrust Digital Library (hathitrust.org) 项目地址: h…...