leetcode322-零钱兑换

原题

给定不同面额的硬币 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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月8日 16:47
下一篇 2020年3月8日 21:34

相关推荐

  • leetcode26-删除排序数组中的重复项

    原题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空…

    算法 2019年11月23日
    0180
  • leetcode313-超级丑数

    原题 编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。 示例: 输入: n = 12, primes = [2…

    算法 2020年2月11日
    0100
  • leetcode39-组合总和

    原题 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates …

    2020年5月1日
    02720
  • leetcode210-课程表II

    原题 现在你总共有 n 门课需要选,记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0…

    算法 2020年5月17日
    0120
  • leetcode557-反转字符串中的单词III

    原题 给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 示例1: 输入: “Let’s take LeetCode contest” 输出: …

    算法 2019年11月23日
    0100
  • 力扣杯春季个人赛-剧情触发时间

    这次的个人赛真是让我认清了自己的实力。。两道困难题都没做出?,虽然大家的通过率也不咋地。。 最后排名 我记录一道做出来的题吧,这道题是一道中等题,通过率如下,虽然题目不难,但由于时…

    2020年4月18日
    0370
  • leetcode191-位1的个数

    原题 编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。 示例 1: 输入: 000000000000000000000000…

    算法 2020年4月15日
    0100
  • leetcode102-二叉树的层次遍历

    原题 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如:给定二叉树: [3,9,20,null,null,15,7],  &nbsp…

    算法 2020年1月11日
    0110
  • leetcode108-将有序数组转换为二叉搜索树

    原题 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数…

    算法 2020年1月18日
    080
  • leetcode15-三数之和

    原题 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。 注意:…

    算法 2020年5月4日
    0150

发表回复

登录后才能评论