扩展区间的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

相关文章

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

Spring 基于XML配置 bean管理 Bean-IOC的方法

《Spring基于XML配置bean管理Bean-IOC的方法》:本文主要介绍Spring基于XML配置bean管理Bean-IOC的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录一. spring学习的核心内容二. 基于 XML 配置 bean1. 通过类型来获取 bean2. 通过

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil

Python处理函数调用超时的四种方法

《Python处理函数调用超时的四种方法》在实际开发过程中,我们可能会遇到一些场景,需要对函数的执行时间进行限制,例如,当一个函数执行时间过长时,可能会导致程序卡顿、资源占用过高,因此,在某些情况下,... 目录前言func-timeout1. 安装 func-timeout2. 基本用法自定义进程subp

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1:集合(set)去重法(最快速)方法2:顺序遍历法(保持顺序)方法3:副本删除法(原地修改)方法4:

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a