原题
给定不同面额的硬币 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/
相关推荐
-
leetcode1014-最佳观光组合
原题 给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。 一对景点（i < j）组成的观光组合的得分为（A[i]...
-
leetcode238-除自身以外数组的乘积
原题 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积...
-
leetcode84-柱状图中最大的矩形
原题 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 以上是柱状图的示例，其中每个柱子的宽...
-
leetcode365-水壶问题
原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？ 如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升...
-
leetcode209-长度最小的子数组
原题 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。 示例: 输入: s = ...
-
leetcode28-实现strStr()
原题 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从...
-
leetcode680-验证回文字符串II
原题 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。 示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出: True 解...
-
leetcode136-只出现一次的数字
原题 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗...
-
leetcode217-存在重复元素
原题 给定一个整数数组，判断是否存在重复元素。 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。 示例1： 输入： [1,2,3...
-
leetcode85-最大矩形
原题 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 示例： 输入: [ ["1","0","1","0","0"...
