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

相关文章

关于数据埋点,你需要了解这些基本知识

产品汪每天都在和数据打交道,你知道数据来自哪里吗? 移动app端内的用户行为数据大多来自埋点,了解一些埋点知识,能和数据分析师、技术侃大山,参与到前期的数据采集,更重要是让最终的埋点数据能为我所用,否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式,可以区分为: 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理:自动程度高的,能解决通用统计,便于统一化管理,但个性化定

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

webm怎么转换成mp4?这几种方法超多人在用!

webm怎么转换成mp4?WebM作为一种新兴的视频编码格式,近年来逐渐进入大众视野,其背后承载着诸多优势,但同时也伴随着不容忽视的局限性,首要挑战在于其兼容性边界,尽管WebM已广泛适应于众多网站与软件平台,但在特定应用环境或老旧设备上,其兼容难题依旧凸显,为用户体验带来不便,再者,WebM格式的非普适性也体现在编辑流程上,由于它并非行业内的通用标准,编辑过程中可能会遭遇格式不兼容的障碍,导致操

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

业务中14个需要进行A/B测试的时刻[信息图]

在本指南中,我们将全面了解有关 A/B测试 的所有内容。 我们将介绍不同类型的A/B测试,如何有效地规划和启动测试,如何评估测试是否成功,您应该关注哪些指标,多年来我们发现的常见错误等等。 什么是A/B测试? A/B测试(有时称为“分割测试”)是一种实验类型,其中您创建两种或多种内容变体——如登录页面、电子邮件或广告——并将它们显示给不同的受众群体,以查看哪一种效果最好。 本质上,A/B测