js.零钱兑换
链接: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};