LeetCode 2952.需要添加的硬币的最小数量:贪心(排序)
【LetMeFly】2952.需要添加的硬币的最小数量:贪心(排序)
力扣题目链接:https://leetcode.cn/problems/minimum-number-of-coins-to-be-added/
给你一个下标从 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
解题方法:排序 + 贪心
二话不说先对coins数组从小到大排个序。使用变量to记录当前能组成到几(初始值为0)。遍历coins数组:
- 如果
coins[i] <= to + 1,那么coins[i]就可以“拼接上”,原本可以组成的数据范围[1, 2, ..., to]加上coins[i]后就可以组成范围[1, 2, ..., to + coins[i]]。因此,更新to为to + coins[i]; - 否则(
coins[i] > to + 1)无法“拼接”,必须添加新的硬币。既然无法组成to + 1,那么必须要添加硬币to + 1。添加后便能组成到to + to + 1。
直到to >= target为止。
- 时间复杂度 O ( c o i n s log c o i n s + log t a r g e t ) O(coins\log coins + \log target) O(coinslogcoins+logtarget)(最多新增硬币
\log target次) - 空间复杂度 O ( log c o i n s ) O(\log coins) O(logcoins)
AC代码
C++
class Solution {
public:int minimumAddedCoins(vector<int>& coins, int target) {sort(coins.begin(), coins.end());int ans = 0, to = 0, i = 0;while (to < target) {if (i < coins.size() && coins[i] <= to + 1) {to += coins[i];i++;}else {to += to + 1;ans++;}}return ans;}
};
Python
# from typing import Listclass Solution:def minimumAddedCoins(self, coins: List[int], target: int) -> int:coins.sort()to, ans, i = 0, 0, 0while to < target:if i < len(coins) and coins[i] <= to + 1:to += coins[i]i += 1else:to += to + 1ans += 1return ans
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/137185903
相关文章:
LeetCode 2952.需要添加的硬币的最小数量:贪心(排序)
【LetMeFly】2952.需要添加的硬币的最小数量:贪心(排序) 力扣题目链接:https://leetcode.cn/problems/minimum-number-of-coins-to-be-added/ 给你一个下标从 0 开始的整数数组 coins,表示可用的硬币的面值ÿ…...
基于SpringBoot + Vue实现的在线装修管理系统设计与实现+毕业论文
介绍 系统包含用户、装修队、管理员三个角色 管理员: 管理员管理:管理其他管理员的账号和权限,确保系统管理的层次化和安全性。 装修队管理:审核装修队的资质,管理装修队的人员信息,监控工程进度ÿ…...
阿里云安全产品简介,Web应用防火墙与云防火墙产品各自作用介绍
在阿里云的安全类云产品中,Web应用防火墙与云防火墙是用户比较关注的安全类云产品,二则在作用上并不是完全一样的,Web应用防火墙是一款网站Web应用安全的防护产品,云防火墙是一款公共云环境下的SaaS化防火墙,本文为大家…...
作业 二维数组-定位问题
图形相似度 描述 给出两幅相同大小的黑白图像(用0-1矩阵)表示,求它们的相似度。 说明:若两幅图像在相同位置上的像素点颜色相同,则称它们在该位置具有相同的像素点。 两幅图像的相似度定义为相同像素点数占总像素点数…...
通过Jmeter准备压测数据-mysql示例
1、新建线程组 总共30万条数据 2、创建jdbc链接 创建jdbc连接配置 配置mysql连接 需要在jmeter安装的路径\apache-jmeter-5.6.3\lib\ext 目录下添加mysql 驱动 3、创建jdbc请求 jdbc链接名称需要与上一步中的保持一致,同时添加insert语句 例如 INSERT INTO test…...
如何系统的自学python?
系统地自学Python是一个循序渐进的过程,以下是一份详细的指南,帮助你从零开始逐步掌握这门语言: 1、了解Python及其应用场景: 阅读关于Python的简介,理解它为何流行,以及在哪些领域(如Web开发…...
记录一个写自定义Flume拦截器遇到的错误
先说结论: 【结论1】配置文件中包名要写正确 vim flume1.conf ... a1.sources.r1.interceptors.i1.type com.atguigu.flume.interceptor.MyInterceptor2$MyBuilder ... 标红的是包名,表黄的是类名,标蓝的是自己加的内部类名。这三个都…...
Codeforces Round 934 (Div. 2) D. Non-Palindromic Substring
题目 思路: #include <bits/stdc.h> using namespace std; #define int long long #define pb push_back #define fi first #define se second #define lson p << 1 #define rson p << 1 | 1 const int maxn 1e6 5, inf 1e9, maxm 4e4 5; co…...
如何避免公网IP安全风险
目录 1. 使用防火墙 2. 定期更新和打补丁 3. 使用入侵检测和预防系统 4. 进行安全审计和监控 5. 实施最小权限原则 6. 使用VPN 7. 配置SSL/TLS 8. 使用DDoS保护服务 9. 强化认证措施 10. 定期备份数据 1. 使用防火墙 配置好网络防火墙,以允许仅必要的端口…...
探究 HTTPS 的工作过程
目录 1. HTTPS 协议原理 1.1. 为什么要有HTTPS协议 1.2. 如何理解安全 1.3. HTTPS 协议是什么 2. HTTPS 的前置概念 2.1. 什么是加密 && 解密 2.2. 为什么要加密 2.3. 常见的加密方式 2.3.1. 对称加密 2.3.2. 非对称加密 2.4. 数据摘要 && 数据指纹…...
算法学习——LeetCode力扣图论篇1
算法学习——LeetCode力扣图论篇1 797. 所有可能的路径 797. 所有可能的路径 - 力扣(LeetCode) 描述 给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特…...
Stable Diffusion 模型下载:epiCPhotoGasm(真实、照片)
本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里,订阅后可阅读专栏内所有文章。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八 下载地址 模型介绍 该模型对照片是什么有很高的了解,所以…...
WPF 路由事件 数据驱动 、Window 事件驱动
消息层层传递,遇到安装有事件侦听器的对象,通过事件处理器响应事件,并决定事件是否继续传递; 后置代码中使用AddHandler方法设置事件监听器,该方法的 第一个参数是指定监听的路由事件类型对象, 第二个参数…...
【UI框架】——保姆式使用教程
👨💻个人主页:开发者-曼亿点 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 曼亿点 原创 👨💻 收录于专栏:…...
第10讲:操作符详解
第10讲:操作符详解 1. 操作符的分类2. 二进制和进制转换2.1 二进制转十进制10进制转2进制数 2.2 二进制转八进制和十六进制2.2.1 二进制转八进制2.2.2 二进制转十六…...
数据可视化Grafana Windows 安装使用教程(中文版)
1.跳转连接 天梦星服务平台 (tmxkj.top)https://tmxkj.top/#/site?url 2.下载应用程序 官网地址:Grafana get started | Cloud, Self-managed, Enterprisehttps://grafana.com/get/ 3.修改配置文件 grafana\conf\defaults 4.启动\bin\目录下serve应用程序 浏…...
【No.21】蓝桥杯组合数学|数位排序|加法计数原理|乘法计数原理|排列数|组合数|抽屉原理|小蓝吃糖果|二项式定理|杨辉三角|归并排序(C++)
组合数学 数位排序 【问题描述】 小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。 例如,2022 排在 409 前面, 因为 2022 的数位之和是 6,小于 409 的数位 之和 13。…...
主流公链 - Monero
Monero: 加密货币的隐私标杆 1. 简介 Monero(XMR),世界语中货币的意思,是一种去中心化的加密货币,旨在提供隐私和匿名性。与比特币等公开区块链不同,Monero专注于隐私保护,使用户的交易记录和余…...
C#中让字典、列表、数组作为只读的方法参考
一、字典 在 C# 中,可以通过使用 ReadOnlyDictionary<TKey, TValue> 类或者是通过调用普通字典的 .AsReadOnly() 方法来创建一个只读的字典。ReadOnlyDictionary 不允许修改字典,任何试图改变字典的操作都会抛出 NotSupportedException。 以下是使…...
深入理解 React 中的 children props 和 render props
深入理解 React 中的 children props 和 render props 在 React 中,children props 和 render props 是两种常见的组件复用模式,它们都可以帮助我们更好地组织和复用组件代码。虽然它们的实现方式有所不同,但都能够有效地实现组件之间的数据…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
