扩展区间的logn的方法(需要添加的最少的硬币数目)

2024-04-03 22:28

本文主要是介绍扩展区间的logn的方法(需要添加的最少的硬币数目),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这个题目的描述其实很简单,大致意思如下:
给你一个下标从 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 。

这个题目其实最开始我看到这个样例的时候就感觉到这个添加的数字都是2的n次幂的数字,那么我们考虑一下为什么会是这样的呢?
其实之所以会出现这样的情况,就在于我们在拓展区间的时候是,也就是当我们之前数组的元素的值无法满足连续区间的时候我们就要拓展我们的区间,而且拓展的区间要成倍数扩展,当然这只是一种情况,具体分析如下:

为方便描述,把 0也算作可以得到的数。

假设现在得到了区间 [0,s−1]中的所有整数,如果此时遍历到整数 x=coins[i],[0,s−1] 中的每个整数都增加 x,我们就得到了区间 [x,s+x−1]中的所有整数。

思路
把 coins\textit{coins}coins 从小到大排序,遍历 x=coins[i]x=\textit{coins}[i]x=coins[i]。分类讨论,看是否要添加数字:

1.如果 x≤s,那么合并 [0,s−1][和 [x,s+x−1]这两个区间,我们可以得到 [0,s+x−1]中的所有整数。
2.如果 x>s,或者遍历完了 coins 数组,这意味着我们无法得到 s,那么就一定要把 s 加到数组中(加一个比 s 还小的数字就没法得到更大的数,不够贪 这里实际上也就是我们看到得到的区间结果每次都是拓展为2倍的原因,贪心的思想就是以s为基准拓展2倍,是当前可以拓展的最大区间),这样就可以得到了 [s,2s−1]中的所有整数,再与 [0,s−1] 合并,可以得到 [0,2s−1]中的所有整数。
当 s>targets 时,我们就得到了 [1,target]中的所有整数,退出循环。

实现代码:

int minimumAddedCoins(vector<int>& coins, int target) {sort(coins.begin(), coins.end());int i = 0,ans = 0, s = 1;while(s <= target){if(i < coins.size() && coins[i] <= s){s += coins[i++];//直接拓展区间把cions加上即可,因为区间可以取交集合并}else{cout << s << endl;//s就是我们要添加的数字s *= 2;//拓展区间为[0,2*s-1]ans += 1;//需要添加的数字+1    }}return ans;}

时间复杂度和空间复杂度:
时间复杂度:O(nlog⁡n+log⁡(target))其中 n 为 coins的长度。s至多翻倍 O(log(⁡target))次。瓶颈主要在排序上。
空间复杂度:O(1)。忽略排序的栈开销。

这篇关于扩展区间的logn的方法(需要添加的最少的硬币数目)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/874135

相关文章

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

CentOS 7部署主域名服务器 DNS的方法

《CentOS7部署主域名服务器DNS的方法》文章详细介绍了在CentOS7上部署主域名服务器DNS的步骤,包括安装BIND服务、配置DNS服务、添加域名区域、创建区域文件、配置反向解析、检查配置... 目录1. 安装 BIND 服务和工具2.  配置 BIND 服务3 . 添加你的域名区域配置4.创建区域

mss32.dll文件丢失怎么办? 电脑提示mss32.dll丢失的多种修复方法

《mss32.dll文件丢失怎么办?电脑提示mss32.dll丢失的多种修复方法》最近,很多电脑用户可能遇到了mss32.dll文件丢失的问题,导致一些应用程序无法正常启动,那么,如何修复这个问题呢... 在电脑常年累月的使用过程中,偶尔会遇到一些问题令人头疼。像是某个程序尝试运行时,系统突然弹出一个错误提

电脑提示找不到openal32.dll文件怎么办? openal32.dll丢失完美修复方法

《电脑提示找不到openal32.dll文件怎么办?openal32.dll丢失完美修复方法》openal32.dll是一种重要的系统文件,当它丢失时,会给我们的电脑带来很大的困扰,很多人都曾经遇到... 在使用电脑过程中,我们常常会遇到一些.dll文件丢失的问题,而openal32.dll的丢失是其中比较

Java常用注解扩展对比举例详解

《Java常用注解扩展对比举例详解》:本文主要介绍Java常用注解扩展对比的相关资料,提供了丰富的代码示例,并总结了最佳实践建议,帮助开发者更好地理解和应用这些注解,需要的朋友可以参考下... 目录一、@Controller 与 @RestController 对比二、使用 @Data 与 不使用 @Dat

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3