原题
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
说明:
你可以认为每种硬币的数量是无限的。
解法
思想
这道题和leetcode279-完全平方数类似，可以使用BFS+剪枝的方法来做。
代码
class Solution {
boolean[] visited;
public int coinChange(int[] coins, int amount) {
if(amount == 0) return 0;
visited = new boolean[amount+1];
Queue<Integer> queue = new LinkedList<>();
queue.offer(amount);
queue.offer(null);
int depth = 0;
while(!queue.isEmpty()){
Integer num = queue.poll();
if(num == null) {
if(queue.isEmpty()) return -1;
depth++;
queue.offer(null);
continue;
}
for(int i = 0;i<coins.length;i++){
int left = num-coins[i];
if(left == 0) return depth + 1;
if(left < 0) continue;
if(visited[left] == true) continue;
visited[left] = true;
queue.offer(left);
}
}
return -1;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode322-%e9%9b%b6%e9%92%b1%e5%85%91%e6%8d%a2/
相关推荐
-
leetcode136-只出现一次的数字
原题 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗...
-
leetcode23-合并K个排序链表
原题 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入： [ 1->4->5, 1->3->4, 2->6 ] 输出： 1->1->2->3->...
-
leetcode1300-转变数组后最接近目标值的数组和
原题 给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 targe...
-
leetcode999-车的可用捕获量
原题 999. 车的可用捕获量 - 力扣（LeetCode） 解法 思想 这道题题目有点难理解，其实就是上下左右搜索，质量有点低了。 代码 class Solution { cha...
-
leetcode86-分隔链表
原题 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head...
-
leetcode380-常数时间插入、删除和获取随机元素
原题 设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。 insert(val)：当元素 val 不存在时，向集合中插入该项。 remove(val)：元素 v...
-
leetcode652-寻找重复的子树
原题 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。 两棵树重复是指它们具有相同的结构以及相同的结点值。 示例1: 1 / \ 2...
-
leetcode771-宝石与石头
原题 给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。 J 中的字母不重复，J ...
-
leetcode14-最长公共前缀
原题 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。 示例 1: 输入: [“flower”,”flow”,”flight”] 输出: “...
-
leetcode153-寻找旋转排序数组中的最小值
原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，...
