LeetCode:2952. 需要添加的硬币的最小数量(贪心 Java)
目录
2952. 需要添加的硬币的最小数量
题目描述:
实现代码与解析:
贪心
原理思路:
2952. 需要添加的硬币的最小数量
题目描述:
给你一个下标从 0 开始的整数数组 coins,表示可用的硬币的面值,以及一个整数 target 。
如果存在某个 coins 的子序列总和为 x,那么整数 x 就是一个 可取得的金额 。
返回需要添加到数组中的 任意面值 硬币的 最小数量 ,使范围 [1, target] 内的每个整数都属于 可取得的金额 。
数组的 子序列 是通过删除原始数组的一些(可能不删除)元素而形成的新的 非空 数组,删除过程不会改变剩余元素的相对位置。
示例 1:
输入:coins = [1,4,10], target = 19 输出:2 解释:需要添加面值为 2 和 8 的硬币各一枚,得到硬币数组 [1,2,4,8,10] 。 可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到,且需要添加到数组中的硬币数目最小为 2 。
示例 2:
输入:coins = [1,4,10,5,7,19], target = 19 输出:1 解释:只需要添加一枚面值为 2 的硬币,得到硬币数组 [1,2,4,5,7,10,19] 。 可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到,且需要添加到数组中的硬币数目最小为 1 。
示例 3:
输入:coins = [1,1,1], target = 20 输出:3 解释: 需要添加面值为 4 、8 和 16 的硬币各一枚,得到硬币数组 [1,1,1,4,8,16] 。 可以证明从 1 到 20 的所有整数都可由数组中的硬币组合得到,且需要添加到数组中的硬币数目最小为 3 。
提示:
1 <= target <= 1051 <= coins.length <= 1051 <= coins[i] <= target
实现代码与解析:
贪心
class Solution {public int minimumAddedCoins(int[] coins, int target) {Arrays.sort(coins);int n = coins.length;int s = 1;int i = 0;int res = 0;while (s <= target) {if (i < n && coins[i] <= s) {s += coins[i++];} else {s *= 2;res++;}}return res;}
}
原理思路:
假设当前需要构造的金额为 s,且我们已经构造出了 [0,...,s−1]内的所有金额。若此时有一个新的硬币 x,我们把它加入到数组中,可以构造出 [x,s+x−1]内的所有金额。
如果 x≤s,可以将上面两个区间合并,得到 [0,s+x−1]内的所有金额。
如果 x>s,就需要添加一个面值为 s 的硬币,这样可以构造出 [0,2s−1]内的所有金额。
所以,将数组 coins按照升序排序,小到大遍历数组中的硬币。对于每个硬币 x,进行和s的比对。直到大于等于target
相关文章:
LeetCode:2952. 需要添加的硬币的最小数量(贪心 Java)
目录 2952. 需要添加的硬币的最小数量 题目描述: 实现代码与解析: 贪心 原理思路: 2952. 需要添加的硬币的最小数量 题目描述: 给你一个下标从 0 开始的整数数组 coins,表示可用的硬币的面值,以及一个…...
企业员工在线培训系统功能介绍
随着信息技术的飞速发展,企业员工培训方式正逐步从传统的面授转向灵活高效的在线培训。一个综合性的企业员工在线培训系统能够为员工提供多样化的学习资源、便捷的学习途径和有效的学习监督,以下是该系统的主要功能详细介绍: 1. 课程功能 线…...
服了,一线城市的后端都卷成这样了吗!?
声明:本文首发在同名公众号:王中阳Go,未经授权禁止转载。 先听TA的故事 投稿的主人公是一名工作5年的后端开发工程师,最近2年用Golang,之前其他语言。去年春节前被裁员了,各种心酸史,好愁人啊。…...
Qt扫盲-QAssisant 集成其他qch帮助文档
QAssisant 集成其他qch帮助文档 一、概述二、Cmake qch例子1. 下载 Cmake.qch2. 添加qch1. 直接放置于Qt 帮助的目录下2. 在 QAssisant中添加 一、概述 QAssisant是一个很好的帮助文档,他提供了供我们在外部添加新的 qch帮助文档的功能接口,一般有两中添…...
[lesson01]学习C++的意义
学习C的意义 C语言特点 C语言是在实践的过程中逐步完善起来的 没有深思熟路的设计过程残留量过多低级语言的特征 C语言的目标是高效 最终程序执行效率的高效 软件方法论的发展 面相过程程序设计:数据结构 算法 主要解决科学计算问题,用户需求简单而…...
LabVIEW双通道太阳射电频谱观测系统
LabVIEW双通道太阳射电频谱观测系统 开发了一个基于LabVIEW平台开发的双通道高速太阳射电频谱观测系统。该系统实时监测太阳射电爆发,具有随机性、持续时间短、变化快等特点。通过高速信号采集卡实现1.5 GS/s的信号采集,时间分辨率可达4ms,频…...
Trapcode Particular---打造惊艳粒子效果
Trapcode Particular是Adobe After Effects中的一款强大3D粒子系统插件,其能够创造出丰富多样的自然特效,如烟雾、火焰和闪光,以及有机的和高科技风格的图形效果。Trapcode Particular功能丰富且特色鲜明,是一款为Adobe After Eff…...
从0到1利用express搭建后端服务
目录 1 架构的选择2 环境搭建3 安装express4 创建启动文件5 express的核心功能6 加入日志记录功能7 日志记录的好处本节代码总结 不知不觉学习低代码已经进入第四个年头了,既然低代码很好,为什么突然又自己架构起后端了呢?我有一句话叫低代码…...
pytest和unittest 如何选择?
目录 如何选择?pytest和unittest哪个更强大pytest和unittest是否可同时应用如何选择? pytest和unittest都是Python中常用的测试框架,它们各自具有一些特点和优势,选择哪一个取决于你的具体需求和偏好。以下是一些关于这两个框架的对比和选择建议: 易用性和简洁性: pytes…...
《QT实用小工具·四》屏幕拾色器
1、概述 源码放在文章末尾 该项目实现了屏幕拾色器的功能,可以根据鼠标指定的位置识别当前位置的颜色 项目功能包含: 鼠标按下实时采集鼠标处的颜色。 实时显示颜色值。 支持16进制格式和rgb格式。 实时显示预览颜色。 根据背景色自动计算合适的前景色…...
【Linux C | 多线程编程】线程的连接、分离,资源销毁情况
😁博客主页😁:🚀https://blog.csdn.net/wkd_007🚀 🤑博客内容🤑:🍭嵌入式开发、Linux、C语言、C、数据结构、音视频🍭 ⏰发布时间⏰:2024-04-01 1…...
kubernetes-Pod基于污点、容忍度、亲和性的多种调度策略(二)
Pod调度策略 一.污点-Taint二.容忍度-Tolerations三.Pod常见状态和重启策略1.Pod常见状态2.Pod的重启策略2.1测试Always重启策略2.2测试Never重启策略2.3测试OnFailure重启策略(生产环境中常用) 一.污点-Taint 在 Kubernetes 中,污点&#x…...
数码管时钟--LABVIEW编程
一、程序的前面板 1.获取系统时钟,年月日,时分秒,用14个数码管显示。 2.闹钟设定小时和分钟。 二、程序的后面板 三、程序运行图 四、程序源码 源程序可以在百度网盘自行下载,地址链接见下方。 链接:https://pan.b…...
linux安装指定版本docker
目录 查看主机上docker版本 配置docker的yum源 安装指定版本docker-20.10.14 查看yum中docker的版本 此命令装完后,任然会是最新版本的docker 卸载已安装docker 安装docker docker依赖包有冲突 解决冲突报错 再次执行安装docker命令 查看主机上docker版本 …...
C++刷题篇——05静态扫描
一、题目 二、解题思路 注意:注意理解题目,缓存的前提是先扫描一次 1、使用两个map,两个map的key相同,map1:key为文件标识,value为文件出现的次数;map2:key为文件标识,va…...
Unity AI Navigation自动寻路
目录 前言一、Unity中AI Navigation是什么?二、使用步骤1.安装AI Navigation2.创建模型和材质3.编写向目标移动的脚本4.NavMeshLink桥接组件5.NavMeshObstacle组件6.NavMeshModifler组件 三、效果总结 前言 Unity是一款强大的游戏开发引擎,而人工智能&a…...
HarmonyOS实战开发-如何实现一个简单的健康生活应用(上)
介绍 本篇Codelab介绍了如何实现一个简单的健康生活应用,主要功能包括: 用户可以创建最多6个健康生活任务(早起,喝水,吃苹果,每日微笑,刷牙,早睡),并设置任…...
React中使用antDesign框架
1.在React项目中使用Ant Design,首先需要安装Ant Design: npm install antd --save 2.按需引入Ant Design组件,以减小最终打包的大小。使用babel-plugin-import插件可以实现按需加载。首先安装插件: npm install babel-plugin-import --save-…...
Electron安全防护实战:应对常见安全问题及权限控制措施
Electron安全防护实战:应对常见安全问题及权限控制措施 引言常见安全问题及其危害提升 Electron 应用安全性的措施限制渲染进程权限防止XSS与内容注入加固应用更新流程严格管理硬件权限使用安全的第三方模块加密敏感数据存储实现进程间通信(IPCÿ…...
StringBuffer与StringBuilder
1.区别 (1). String : 不可变字符序列. (2). StringBuffer : 可变字符序列.线程安全,但效率低. (3). StringBuilder : 可变字符序列.线程不安全,但效率高. 既然StringBuffer与StringBuilder都是可变字符序列,但二者咋区分开呢?…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
