LeetCode 冥想:硬币找零
来源:dev.to
时间:2024-08-20 10:09:46 336浏览 收藏
各位小伙伴们,大家好呀!看看今天我又给各位带来了什么文章?本文标题是《LeetCode 冥想:硬币找零》,很明显是关于文章的文章哈哈哈,其中内容主要会涉及到等等,如果能帮到你,觉得很不错的话,欢迎各位多多点评和分享!
我们先来描述一下这个问题:
给你一个代表不同面额硬币的整数数组硬币和代表总金额的整数金额。
返回弥补该金额所需的最少硬币数量。如果任何硬币组合都无法弥补该金额,则返回-1。
您可以假设您拥有无限数量的每种硬币。
例如:
input: coins = [1, 2, 5], amount = 11 output: 3 explanation: 11 = 5 + 5 + 1
或者:
input: coins = [2], amount = 3 output: -1
或者:
input: coins = [1], amount = 0 output: 0
此外,我们的约束之一表明 1 <=coins.length <= 12.
这个问题实际上是一个熟悉的问题,您可能在贪婪问题的背景下见过它。然而,这个版本要求我们找到最少数量的硬币,贪心的方法是行不通的。
neetcode 视频清楚地展示了为什么会这样:例如,如果我们的硬币是 [1, 3, 4, 5] 并且数量是 7,贪婪方法将首先得到 5,然后它会尝试所有 最大 数量,直到它必须满足两个 1,使其总数为 5、1 和 1。但是,我们可以使用比这更少的硬币:4 和 3。所以,让我们看看如何做到这一点。
我们必须以某种方式积累到我们可以使用的最小硬币数量。为此,我们从初始化一个数组开始:
let dp = array.from({ length: amount + 1 }, () => amount + 1);
我们有这个长度为 amount + 1 的数组,因为每个索引将保存每个金额可以使用的最小硬币数量。例如,dp 数组的索引 0 将保存我们可以使用的最小硬币数量的值使用量为0;同样,索引 7 将保存我们可以使用 7 的最小硬币数量的值。
我们用amount + 1的占位符值初始化每个索引,因为最大硬币数量不能超过amount(例如,我们可以使用7的最大硬币数量是7:1 + 1 + 1 + 1 + 1 + 1 + 1).
注意 |
---|
在这个问题中,最小价值的硬币是 1,正如约束之一所示。 |
对于0的数量,我们可以使用的最小硬币数量是显而易见的:0:
dp[0] = 0;
然后,我们将从索引 1 开始循环遍历这个数组,对于每个索引,我们将迭代硬币:
for (let amountidx = 1; amountidx < dp.length; amountidx++) { for (const coin of coins) { /* ... */ } }
如果我们正在查看的硬币可以用于该金额(即 amountidx - coin >= 0),那么我们将更新 dp 数组中该金额的值。它将是我们已经拥有的值的最小值,或者 1 + dp[amountidx - coin]:
for (let amountidx = 1; amountidx < dp.length; amountidx++) { for (const coin of coins) { if (amountidx - coin >= 0) { dp[amountidx] = math.min(dp[amountidx], 1 + dp[amountidx - coin]); } } }
注意 |
---|
1 + dp[amountidx - coin] 的原因是我们使用已经计算出的值的解,重用子问题。所以,1 是我们目前正在考虑的硬币。 |
如果最后我们无法将总金额与任何硬币组合匹配,我们必须返回-1。
检查的方法是检查最后一个元素等于 amount + 1 的条件。在这种情况下,我们可以返回 -1。否则,我们将只返回包含构成金额的最小硬币数量的最后一个元素:
function coinchange(coins: number[], amount: number): number { /* ... */ if (dp[dp.length - 1] === amount + 1) { return -1; } return dp[dp.length - 1]; }
而且,这是最终的解决方案:
function coinChange(coins: number[], amount: number): number { let dp = Array.from({ length: amount + 1 }, () => amount + 1); dp[0] = 0; for (let amountIdx = 1; amountIdx < dp.length; amountIdx++) { for (const coin of coins) { if (amountIdx - coin >= 0) { dp[amountIdx] = Math.min(dp[amountIdx], 1 + dp[amountIdx - coin]); } } } if (dp[dp.length - 1] === amount + 1) { return -1; } return dp[dp.length - 1]; }
时间和空间复杂度
时间复杂度为o(n*m) 在哪里 n 是金额 + 1 并且 m 是我们拥有的硬币数量。我们迭代每个值直到 amount + 1,并且对于每个值,再次迭代每个硬币,执行恒定操作。
空间复杂度取决于我们给出的数量,因为 dp 数组的大小会随着数量的增加而增长,所以我们可以说它是 o(n) 在哪里 n 是金额。
是时候深呼吸了。尽管我们通常会接受动态规划问题的解决方案,但一开始就很难得到它们——不仅要提出解决方案,还要理解已经存在的解决方案。
接下来,我们来看看最大乘积子数组问题。在那之前,祝您编码愉快。
理论要掌握,实操不能落!以上关于《LeetCode 冥想:硬币找零》的详细介绍,大家都掌握了吧!如果想要继续提升自己的能力,那么就来关注golang学习网公众号吧!
-
501 收藏
-
501 收藏
-
501 收藏
-
501 收藏
-
501 收藏
-
117 收藏
-
248 收藏
-
450 收藏
-
341 收藏
-
464 收藏
-
341 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 立即学习 541次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 立即学习 506次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 立即学习 497次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 立即学习 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 立即学习 484次学习