网站建设报价单站长工具手机综合查询

链接：322. 零钱兑换 - 力扣（LeetCode）

题目：

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

思路：

我使用的是广搜的方式，使用栈结构，这样其实是比较慢的，但是还是做出来了。

代码：

/*** @param {number[]} coins* @param {number} amount* @return {number}*/var coinChange = function(coins, amount) {if(amount == 0) return 0let num = [...coins] , set = new Set([...num]) , count = 1while(num.length!=0){let n = num.lengthfor(let i = 0 ; i < n ; i++ ){// 用count代表层数if(num[0]==amount) return count//将num[0]与coins中每个数相加，将不重复的入栈coins.forEach(function(value, index, array){let item = value + num[0]//用set解决去重问题//一定要加上item<=amount条件，不然会变成死循环if(!set.has(item)&&item<=amount){set.add(item)num.push(item)}})// 将第一个元素移除num.shift()}count++}return -1};