需要添加的硬币的最小数量(Lc2952)——贪心+构造
给你一个下标从 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
问题简要描述:返回需要添加的硬币的最小数量
细节阐述:
- s 表示已经构造出了 [0,...,s−1] 内的所有金额。如果 x≤s,那么我们可以将上面两个区间合并,得到 [0,s+x−1] 内的所有金额;如果 x>s,那么我们就需要添加一个面值为 s 的硬币,这样可以构造出 [0,2s−1] 内的所有金额,然后再考虑 x 和 s 的大小关系,其中x = coins[i]
Java
class Solution {public int minimumAddedCoins(int[] coins, int target) {int ans = 0, s = 1;Arrays.sort(coins);for (int i = 0; s <= target; ) {if (i < coins.length && coins[i] <= s) {s += coins[i++];} else {ans++;s <<= 1;}}return ans;}
}
Python3
class Solution:def minimumAddedCoins(self, coins: List[int], target: int) -> int:ans = i = 0s = 1coins.sort()while s <= target: if i < len(coins) and coins[i] <= s:s += coins[i]i += 1else:s <<= 1ans += 1return ans
TypeScript
function minimumAddedCoins(coins: number[], target: number): number {coins.sort((a, b) => a - b);let ans = 0, s = 1;for (let i = 0; s <= target;) {if (i < coins.length && coins[i] <= s) {s += coins[i++];} else {ans++;s <<= 1;}}return ans;
};
相关文章:
需要添加的硬币的最小数量(Lc2952)——贪心+构造
给你一个下标从 0 开始的整数数组 coins,表示可用的硬币的面值,以及一个整数 target 。 如果存在某个 coins 的子序列总和为 x,那么整数 x 就是一个 可取得的金额 。 返回需要添加到数组中的 任意面值 硬币的 最小数量 ,使范围 …...
军工保密资质介绍及申请要求
军工保密资质介绍 军工保密资质是指国家对从事军工研发、生产、销售等活动的企事业单位进行的一种资质认证。该资质的核心目标是保护国家军事机密和军事技术秘密,确保国家安全和国防利益。军工保密资质的认证标准非常严格,涉及企业的安全管理、技术保密…...
ES6的编程风格
ES6 提出了两个新的声明变量的命令:let和const。其中,let完全可以取代var,因为两者语义相同,而且let没有副作用。 var命令存在变量提升效用,let命令没有这个问题 if (true) {console.log(x); // ReferenceErrorlet x…...
springboot 载入自定义的yml文件转DTO
json解析的pom引入 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-json</artifactId><version>5.8.20</version></dependency>resources目录下的my-data.yml project:data:- name: service-genbase-package:…...
webpack-(plugin,本地服务器,路径别名,安装vue)
安装vue npm i vue-loader -D npm i vue 编写一个vue文件: 在index.html中设置 一个id为app的div 将vue文件挂载到app中 vue比较特殊,除了使用loader外,还使用了plugin const path require("path"); const { VueLoaderPlugin …...
http请求头导致了dial tcp:lookup xxxx on 10.43.0.10:53 no sunch host
事实证明人有的时候也不能太偷懒,太偷懒容易给自己埋坑。 问题的背景: web端调用服务A,服务A异步调用服务B。服务A有四个场景需要调用服务B,所以,服务A中封装了一个公用的方法,唯一的区别是,场…...
想要设计放大电路,必须掌握哪些?
放大电路是电子系统中的核心组成部分,其设计好坏将直接影响到整个系统的性能,对电子工程师来说,在设计放大电路时,必须掌握且关注多方面,以此确保电路的稳定性和放大效果,那么需要注意哪些? 1、…...
每天五分钟计算机视觉:基于卷积操作完成滑动窗口的图片分类?
本文重点 我们前面学习了使用不同大小的滑动窗口来滑动图片,然后切分成许多小的图片,然后依次应用到我们已经训练好的图像分类模型中,但是这种方式效率太低了,本节课程我们学习一种新的方式,来看一下如何并行识别这些剪切的图片。 原始结构 首先我们先来看一下,如何把…...
UI设计/交互设计/视觉设计项目汇报/作品集Figma/PPT模板
作为UI设计/交互设计/视觉设计师,创建作品集对于向潜在客户或雇主展示您的技能、创造力和风格至关重要。以下分步指南可帮助您创建令人印象深刻的作品集: 选择您的最佳作品:选择您最强大且最相关的设计项目,将其纳入您的作品集。…...
25、Lua 学习笔记之三(高阶话题)
Lua 学习笔记之三 高阶话题迭代实例代码有关迭代的描述 协作线程实例代码有关协作线程的描述 高阶话题 迭代 实例代码 --迭代 local function enum(array)local index 1return function()local ret array[index]index index 1return retend endlocal function foreach(a…...
企业网盘搭建——LNMP
php包链接:https://pan.baidu.com/s/1RElYTQx320pN6452N_7t1Q?pwdp8gs 提取码:p8gs 网盘源码包链接:https://pan.baidu.com/s/1BaYqwruka1P6h5wBBrLiBw?pwdwrzo 提取码:wrzo 目录 一.手动部署 二.自动部署 一.手动部署 …...
Go语言异常处理方式
Go 语言没有传统的异常处理机制,如 Java、C 或 Python 中的 try-catch 语句。取而代之,Go 采用了基于返回错误值和 panic/recover 机制的混合模式来进行错误处理。以下是 Go 语言中处理异常(或称错误)的两种主要方式: …...
时序分析基本知识点
【FPGA开发/IC开发之时序约束最全面的归纳总结】时序路径基本概念及时序约束分析方法_时序约束指令-CSDN博客...
ELK(Elasticsearch+Logstash+Kibana)日志分析系统
目录 前言 一、ELK日志分析系统概述 1、三大组件工具介绍 1.1 Elasticsearch 1.1.1 Elasticsearch概念 1.1.2 关系型数据库和ElasticSearch中的对应关系 1.1.3 Elasticsearch提供的操作命令 1.2 Logstash 1.2.1 Logstash概念 1.2.2 Logstash的主要组件 1.2.3 Logsta…...
【投稿优惠-EI稳定检索】2024年地理信息技术与遥感测绘国际学术会议(ICGITRSM 2024)
2024 International Conference on Geographic Information Technology and Remote Sensing Mapping (ICGITRSM 2024) ●会议简介 2024年地理信息技术与遥感测绘国际学术会议将聚焦于地理信息技术及遥感测绘领域的最新发展与应用。本次会议汇聚了来自世界各地的顶尖专家和学者…...
MySQL的内外连接
📟作者主页:慢热的陕西人 🌴专栏链接:MySQL 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 本博客主要内容主要介绍了MySQL中的内外连接 文章目录 MySQL的内外连接…...
Pandas连接MySQL数据库
pandas是一个强大的Python工具包,能够快速帮助我们做很多数据处理。但是在利用pandas连接数据库时,也会遇到很多问题,在此我总结了一个相对较为简单的连接范式,供大家参考学习。 先上代码: import pandas as pd# 数据…...
2024华中杯数学建模参考思路+完整代码+后续成品论文预约
(完整版资料获取在文末哦) 关于24年华中杯的更新进度,大家可以参考我们前年比赛。 22年华中杯思路: 大家也可以看这一篇 A题思路 一订单包含多种货品,每种商品有不同的数量,题目没说订单的需求时间&am…...
ARM_day8:基于iic总线的通信
一、IIC总线的基本概念: iic总线是一种带应答的同步的、串行、半双工的通信方式,支持一个主机对应多个从机。它有一根SCL(时钟线)和一根SDA(数据线)组成,由于只有一根数据线,所以它是…...
33、Lua Cocos2d-x使用Luajit实现加密
项目要求对lua脚本进行加密,查了一下相关的资料 ,得知lua本身可以使用luac将脚本编译为字节码(bytecode)从而实现加密,试了一下,确实可行。下面是使用原生的lua解释器编译字节码: 新建一个名为1.lua的文件,…...
3分钟破解微信小程序加密包:wxappUnpacker极速解析实战指南
3分钟破解微信小程序加密包:wxappUnpacker极速解析实战指南 【免费下载链接】wxappUnpacker 项目地址: https://gitcode.com/gh_mirrors/wxappu/wxappUnpacker wxappUnpacker是一款专注于微信小程序逆向解析的开源工具,能够快速破解wxapkg格式(微…...
QwQ-32B在ollama中的推理效果展示:数学定理推导、算法设计全过程
QwQ-32B在ollama中的推理效果展示:数学定理推导、算法设计全过程 1. 模型简介与部署准备 QwQ-32B是Qwen系列中专注于推理能力的语言模型,与传统指令调优模型相比,它在解决复杂问题和推理任务方面表现突出。这款中等规模模型拥有325亿参数&a…...
编译原理避坑指南:自顶向下语法分析的5个常见错误及解决方法
编译原理避坑指南:自顶向下语法分析的5个常见错误及解决方法 第一次接触自顶向下语法分析时,我盯着那个无限循环的递归文法整整三天没想明白——为什么明明按照教材步骤操作,程序却始终报错?直到助教指出我忽略了间接左递归的隐蔽…...
告别树莓派溢价!Radxa ROCK 5A 8GB版开箱实测,652元真香体验与避坑指南
652元平替树莓派4B?Radxa ROCK 5A深度体验与实战避坑手册 当树莓派4B的价格突破900元大关时,许多开发者开始寻找更具性价比的替代方案。Radxa ROCK 5A的出现恰逢其时——这款搭载RK3588S芯片的单板计算机不仅性能翻倍,价格却仅为652元&#…...
效率飙升:借助快马平台生成全自动OpenClaw本地部署一体化工具
最近在折腾OpenClaw的本地部署时,发现传统方式实在太费时间了。每次都要手动查文档、拼命令、调环境,经常卡在某个依赖项版本冲突上。后来尝试用InsCode(快马)平台生成了一体化部署工具,效率直接翻倍。这里分享下具体实现思路和优化点&#x…...
突破运营商限制:中兴光猫配置文件解密工具完全指南
突破运营商限制:中兴光猫配置文件解密工具完全指南 【免费下载链接】ZET-Optical-Network-Terminal-Decoder 项目地址: https://gitcode.com/gh_mirrors/ze/ZET-Optical-Network-Terminal-Decoder 一、用户痛点解析:你是否正遭遇这些网络管理困境…...
FedMeta: Accelerating Federated Learning with Meta-Learning for Enhanced Privacy and Efficiency
1. FedMeta:当联邦学习遇上元学习 想象一下,你正在训练一个能识别手写数字的AI模型,但数据分散在成千上万个用户的手机里。传统联邦学习就像让每个用户都从头开始训练完整模型,既耗流量又费时间。而FedMeta的聪明之处在于——它让…...
Python实战:5分钟搞定小红书自动点赞脚本(附完整代码)
Python实战:5分钟实现小红书自动化互动工具开发指南 在当今内容爆炸的时代,社交媒体运营已成为个人品牌和商业推广的重要阵地。小红书作为国内领先的生活方式分享平台,其互动数据直接影响内容曝光和账号权重。对于开发者而言,掌握…...
springboot框架健康饮食营养管理信息系统
目录需求分析与系统设计技术栈选型与环境搭建核心功能实现数据可视化与报告生成测试与部署项目技术支持源码获取详细视频演示 :文章底部获取博主联系方式!同行可合作需求分析与系统设计 明确健康饮食营养管理系统的核心需求,包括用户注册登录…...
C++ 内存分配器工作原理
C内存分配器工作原理探秘 在C中,动态内存管理是程序性能优化的关键环节,而内存分配器则是幕后英雄。它负责在堆上高效分配和释放内存,直接影响程序的运行效率和资源利用率。无论是标准库中的std::allocator,还是自定义的高性能分…...
