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

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 <= 105
  • 1 <= coins.length <= 105
  • 1 <= coins[i] <= target

解题方法:排序 + 贪心

二话不说先对coins数组从小到大排个序。使用变量to记录当前能组成到几(初始值为0)。遍历coins数组:

  • 如果coins[i] <= to + 1,那么coins[i]就可以“拼接上”,原本可以组成的数据范围[1, 2, ..., to]加上coins[i]后就可以组成范围[1, 2, ..., to + coins[i]]。因此,更新toto + 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.需要添加的硬币的最小数量&#xff1a;贪心&#xff08;排序&#xff09; 力扣题目链接&#xff1a;https://leetcode.cn/problems/minimum-number-of-coins-to-be-added/ 给你一个下标从 0 开始的整数数组 coins&#xff0c;表示可用的硬币的面值&#xff…...

基于SpringBoot + Vue实现的在线装修管理系统设计与实现+毕业论文

介绍 系统包含用户、装修队、管理员三个角色 管理员&#xff1a; 管理员管理&#xff1a;管理其他管理员的账号和权限&#xff0c;确保系统管理的层次化和安全性。 装修队管理&#xff1a;审核装修队的资质&#xff0c;管理装修队的人员信息&#xff0c;监控工程进度&#xff…...

阿里云安全产品简介,Web应用防火墙与云防火墙产品各自作用介绍

在阿里云的安全类云产品中&#xff0c;Web应用防火墙与云防火墙是用户比较关注的安全类云产品&#xff0c;二则在作用上并不是完全一样的&#xff0c;Web应用防火墙是一款网站Web应用安全的防护产品&#xff0c;云防火墙是一款公共云环境下的SaaS化防火墙&#xff0c;本文为大家…...

作业 二维数组-定位问题

图形相似度 描述 给出两幅相同大小的黑白图像&#xff08;用0-1矩阵&#xff09;表示&#xff0c;求它们的相似度。 说明&#xff1a;若两幅图像在相同位置上的像素点颜色相同&#xff0c;则称它们在该位置具有相同的像素点。 两幅图像的相似度定义为相同像素点数占总像素点数…...

通过Jmeter准备压测数据-mysql示例

1、新建线程组 总共30万条数据 2、创建jdbc链接 创建jdbc连接配置 配置mysql连接 需要在jmeter安装的路径\apache-jmeter-5.6.3\lib\ext 目录下添加mysql 驱动 3、创建jdbc请求 jdbc链接名称需要与上一步中的保持一致&#xff0c;同时添加insert语句 例如 INSERT INTO test…...

如何系统的自学python?

系统地自学Python是一个循序渐进的过程&#xff0c;以下是一份详细的指南&#xff0c;帮助你从零开始逐步掌握这门语言&#xff1a; 1、了解Python及其应用场景&#xff1a; 阅读关于Python的简介&#xff0c;理解它为何流行&#xff0c;以及在哪些领域&#xff08;如Web开发…...

记录一个写自定义Flume拦截器遇到的错误

先说结论&#xff1a; 【结论1】配置文件中包名要写正确 vim flume1.conf ... a1.sources.r1.interceptors.i1.type com.atguigu.flume.interceptor.MyInterceptor2$MyBuilder ... 标红的是包名&#xff0c;表黄的是类名&#xff0c;标蓝的是自己加的内部类名。这三个都…...

Codeforces Round 934 (Div. 2) D. Non-Palindromic Substring

题目 思路&#xff1a; #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. 使用防火墙 配置好网络防火墙&#xff0c;以允许仅必要的端口…...

探究 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. 所有可能的路径 - 力扣&#xff08;LeetCode&#xff09; 描述 给你一个有 n 个节点的 有向无环图&#xff08;DAG&#xff09;&#xff0c;请你找出所有从节点 0 到节点 n-1 的路径并输出&#xff08;不要求按特…...

Stable Diffusion 模型下载:epiCPhotoGasm(真实、照片)

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里&#xff0c;订阅后可阅读专栏内所有文章。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八 下载地址 模型介绍 该模型对照片是什么有很高的了解&#xff0c;所以…...

WPF 路由事件 数据驱动 、Window 事件驱动

消息层层传递&#xff0c;遇到安装有事件侦听器的对象&#xff0c;通过事件处理器响应事件&#xff0c;并决定事件是否继续传递&#xff1b; 后置代码中使用AddHandler方法设置事件监听器&#xff0c;该方法的 第一个参数是指定监听的路由事件类型对象&#xff0c; 第二个参数…...

【UI框架】——保姆式使用教程

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…...

第10讲:操作符详解

第10讲&#xff1a;操作符详解 1. 操作符的分类2. 二进制和进制转换2.1 二进制转十进制10进制转2进制数 ![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/45fb3048f5164084b9d494b3d233bc42.png)2.2 二进制转八进制和十六进制2.2.1 二进制转八进制2.2.2 二进制转十六…...

数据可视化Grafana Windows 安装使用教程(中文版)

1.跳转连接 天梦星服务平台 (tmxkj.top)https://tmxkj.top/#/site?url 2.下载应用程序 官网地址&#xff1a;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&#xff08;XMR&#xff09;&#xff0c;世界语中货币的意思&#xff0c;是一种去中心化的加密货币&#xff0c;旨在提供隐私和匿名性。与比特币等公开区块链不同&#xff0c;Monero专注于隐私保护&#xff0c;使用户的交易记录和余…...

C#中让字典、列表、数组作为只读的方法参考

一、字典 在 C# 中&#xff0c;可以通过使用 ReadOnlyDictionary<TKey, TValue> 类或者是通过调用普通字典的 .AsReadOnly() 方法来创建一个只读的字典。ReadOnlyDictionary 不允许修改字典&#xff0c;任何试图改变字典的操作都会抛出 NotSupportedException。 以下是使…...

深入理解 React 中的 children props 和 render props

深入理解 React 中的 children props 和 render props 在 React 中&#xff0c;children props 和 render props 是两种常见的组件复用模式&#xff0c;它们都可以帮助我们更好地组织和复用组件代码。虽然它们的实现方式有所不同&#xff0c;但都能够有效地实现组件之间的数据…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...