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

LeetCode:2952. 需要添加的硬币的最小数量(贪心 Java)

目录

2952. 需要添加的硬币的最小数量

题目描述:

实现代码与解析:

贪心

原理思路:


2952. 需要添加的硬币的最小数量

题目描述:

        给你一个下标从 开始的整数数组 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 <= 105
  • 1 <= coins.length <= 105
  • 1 <= 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. 需要添加的硬币的最小数量 题目描述&#xff1a; 实现代码与解析&#xff1a; 贪心 原理思路&#xff1a; 2952. 需要添加的硬币的最小数量 题目描述&#xff1a; 给你一个下标从 0 开始的整数数组 coins&#xff0c;表示可用的硬币的面值&#xff0c;以及一个…...

企业员工在线培训系统功能介绍

随着信息技术的飞速发展&#xff0c;企业员工培训方式正逐步从传统的面授转向灵活高效的在线培训。一个综合性的企业员工在线培训系统能够为员工提供多样化的学习资源、便捷的学习途径和有效的学习监督&#xff0c;以下是该系统的主要功能详细介绍&#xff1a; 1. 课程功能 线…...

服了,一线城市的后端都卷成这样了吗!?

声明&#xff1a;本文首发在同名公众号&#xff1a;王中阳Go&#xff0c;未经授权禁止转载。 先听TA的故事 投稿的主人公是一名工作5年的后端开发工程师&#xff0c;最近2年用Golang&#xff0c;之前其他语言。去年春节前被裁员了&#xff0c;各种心酸史&#xff0c;好愁人啊。…...

Qt扫盲-QAssisant 集成其他qch帮助文档

QAssisant 集成其他qch帮助文档 一、概述二、Cmake qch例子1. 下载 Cmake.qch2. 添加qch1. 直接放置于Qt 帮助的目录下2. 在 QAssisant中添加 一、概述 QAssisant是一个很好的帮助文档&#xff0c;他提供了供我们在外部添加新的 qch帮助文档的功能接口&#xff0c;一般有两中添…...

[lesson01]学习C++的意义

学习C的意义 C语言特点 C语言是在实践的过程中逐步完善起来的 没有深思熟路的设计过程残留量过多低级语言的特征 C语言的目标是高效 最终程序执行效率的高效 软件方法论的发展 面相过程程序设计&#xff1a;数据结构 算法 主要解决科学计算问题&#xff0c;用户需求简单而…...

LabVIEW双通道太阳射电频谱观测系统

LabVIEW双通道太阳射电频谱观测系统 开发了一个基于LabVIEW平台开发的双通道高速太阳射电频谱观测系统。该系统实时监测太阳射电爆发&#xff0c;具有随机性、持续时间短、变化快等特点。通过高速信号采集卡实现1.5 GS/s的信号采集&#xff0c;时间分辨率可达4ms&#xff0c;频…...

Trapcode Particular---打造惊艳粒子效果

Trapcode Particular是Adobe After Effects中的一款强大3D粒子系统插件&#xff0c;其能够创造出丰富多样的自然特效&#xff0c;如烟雾、火焰和闪光&#xff0c;以及有机的和高科技风格的图形效果。Trapcode Particular功能丰富且特色鲜明&#xff0c;是一款为Adobe After Eff…...

从0到1利用express搭建后端服务

目录 1 架构的选择2 环境搭建3 安装express4 创建启动文件5 express的核心功能6 加入日志记录功能7 日志记录的好处本节代码总结 不知不觉学习低代码已经进入第四个年头了&#xff0c;既然低代码很好&#xff0c;为什么突然又自己架构起后端了呢&#xff1f;我有一句话叫低代码…...

pytest和unittest 如何选择?

目录 如何选择?pytest和unittest哪个更强大pytest和unittest是否可同时应用如何选择? pytest和unittest都是Python中常用的测试框架,它们各自具有一些特点和优势,选择哪一个取决于你的具体需求和偏好。以下是一些关于这两个框架的对比和选择建议: 易用性和简洁性: pytes…...

《QT实用小工具·四》屏幕拾色器

1、概述 源码放在文章末尾 该项目实现了屏幕拾色器的功能&#xff0c;可以根据鼠标指定的位置识别当前位置的颜色 项目功能包含&#xff1a; 鼠标按下实时采集鼠标处的颜色。 实时显示颜色值。 支持16进制格式和rgb格式。 实时显示预览颜色。 根据背景色自动计算合适的前景色…...

【Linux C | 多线程编程】线程的连接、分离,资源销毁情况

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; ⏰发布时间⏰&#xff1a;2024-04-01 1…...

kubernetes-Pod基于污点、容忍度、亲和性的多种调度策略(二)

Pod调度策略 一.污点-Taint二.容忍度-Tolerations三.Pod常见状态和重启策略1.Pod常见状态2.Pod的重启策略2.1测试Always重启策略2.2测试Never重启策略2.3测试OnFailure重启策略&#xff08;生产环境中常用&#xff09; 一.污点-Taint 在 Kubernetes 中&#xff0c;污点&#x…...

数码管时钟--LABVIEW编程

一、程序的前面板 1.获取系统时钟&#xff0c;年月日&#xff0c;时分秒&#xff0c;用14个数码管显示。 2.闹钟设定小时和分钟。 二、程序的后面板 三、程序运行图 四、程序源码 源程序可以在百度网盘自行下载&#xff0c;地址链接见下方。 链接&#xff1a;https://pan.b…...

linux安装指定版本docker

目录 查看主机上docker版本 配置docker的yum源 安装指定版本docker-20.10.14 查看yum中docker的版本 此命令装完后&#xff0c;任然会是最新版本的docker 卸载已安装docker 安装docker docker依赖包有冲突 解决冲突报错 再次执行安装docker命令 查看主机上docker版本 …...

C++刷题篇——05静态扫描

一、题目 二、解题思路 注意&#xff1a;注意理解题目&#xff0c;缓存的前提是先扫描一次 1、使用两个map&#xff0c;两个map的key相同&#xff0c;map1&#xff1a;key为文件标识&#xff0c;value为文件出现的次数&#xff1b;map2&#xff1a;key为文件标识&#xff0c;va…...

Unity AI Navigation自动寻路

目录 前言一、Unity中AI Navigation是什么&#xff1f;二、使用步骤1.安装AI Navigation2.创建模型和材质3.编写向目标移动的脚本4.NavMeshLink桥接组件5.NavMeshObstacle组件6.NavMeshModifler组件 三、效果总结 前言 Unity是一款强大的游戏开发引擎&#xff0c;而人工智能&a…...

HarmonyOS实战开发-如何实现一个简单的健康生活应用(上)

介绍 本篇Codelab介绍了如何实现一个简单的健康生活应用&#xff0c;主要功能包括&#xff1a; 用户可以创建最多6个健康生活任务&#xff08;早起&#xff0c;喝水&#xff0c;吃苹果&#xff0c;每日微笑&#xff0c;刷牙&#xff0c;早睡&#xff09;&#xff0c;并设置任…...

React中使用antDesign框架

1.在React项目中使用Ant Design&#xff0c;首先需要安装Ant Design: npm install antd --save 2.按需引入Ant Design组件&#xff0c;以减小最终打包的大小。使用babel-plugin-import插件可以实现按需加载。首先安装插件&#xff1a; npm install babel-plugin-import --save-…...

Electron安全防护实战:应对常见安全问题及权限控制措施

Electron安全防护实战&#xff1a;应对常见安全问题及权限控制措施 引言常见安全问题及其危害提升 Electron 应用安全性的措施限制渲染进程权限防止XSS与内容注入加固应用更新流程严格管理硬件权限使用安全的第三方模块加密敏感数据存储实现进程间通信&#xff08;IPC&#xff…...

StringBuffer与StringBuilder

1.区别 (1). String : 不可变字符序列. (2). StringBuffer : 可变字符序列.线程安全&#xff0c;但效率低. (3). StringBuilder : 可变字符序列.线程不安全&#xff0c;但效率高. 既然StringBuffer与StringBuilder都是可变字符序列&#xff0c;但二者咋区分开呢&#xff1f…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

2025年- H71-Lc179--39.组合总和(回溯,组合)--Java版

1.题目描述 2.思路 当前的元素可以重复使用。 &#xff08;1&#xff09;确定回溯算法函数的参数和返回值&#xff08;一般是void类型&#xff09; &#xff08;2&#xff09;因为是用递归实现的&#xff0c;所以我们要确定终止条件 &#xff08;3&#xff09;单层搜索逻辑 二…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)

目录 &#x1f50d; 若用递归计算每一项&#xff0c;会发生什么&#xff1f; Horners Rule&#xff08;霍纳法则&#xff09; 第一步&#xff1a;我们从最原始的泰勒公式出发 第二步&#xff1a;从形式上重新观察展开式 &#x1f31f; 第三步&#xff1a;引出霍纳法则&…...

Qt Quick Controls模块功能及架构

Qt Quick Controls是Qt Quick的一个附加模块&#xff0c;提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中&#xff0c;这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构&#xff0c;与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...

在ubuntu等linux系统上申请https证书

使用 Certbot 自动申请 安装 Certbot Certbot 是 Let’s Encrypt 官方推荐的自动化工具&#xff0c;支持多种操作系统和服务器环境。 在 Ubuntu/Debian 上&#xff1a; sudo apt update sudo apt install certbot申请证书 纯手动方式&#xff08;不自动配置&#xff09;&…...

Qt 按钮类控件(Push Button 与 Radio Button)(1)

文章目录 Push Button前提概要API接口给按钮添加图标给按钮添加快捷键 Radio ButtonAPI接口性别选择 Push Button&#xff08;鼠标点击不放连续移动快捷键&#xff09; Radio Button Push Button 前提概要 1. 之前文章中所提到的各种跟QWidget有关的各种属性/函数/方法&#…...