用广度优先搜索（BFS）解决零钱兑换问题

原创

来啦老弟

修改于 2020-06-08 14:42:33

6350

修改于 2020-06-08 14:42:33

文章被收录于专栏：Roger的Java路

1 题目描述

中等624给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11

输出: 3

解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3

输出: -1

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/coin-change

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2 题目分析

【题例】

输入: coins = [1, 2, 5], amount = 11

输出: 3

解释: 11 = 5 + 5 + 1

【思路图】

3 题解

3.1 最单纯的BFS——超时

 public static int coinChange(int[] coins, int amount) {
		 Integer result=0;
		 int size=0;
		 int depth=0;
		 
		 Queue queue = new LinkedList();
		 
		 
		 
		 if(amount ==0)
			 return 0;
		 
		 
			 for(int i=0;i<coins.length;i++)
			 {
				 queue.offer((Integer)coins[i]);
				 if(coins[i]==amount)
					 return 1;
			 }
		 
			 
		 
		while(!queue.isEmpty()){
			size = queue.size();
			depth++;
			
			System.out.println("the depth is" + depth);
			System.out.println("the size is" + size);
			
			for(int i=0;i<size;i++){
				result = (Integer) queue.poll();
				System.out.println("the result is"+result);
				for(int j =0; j<coins.length;j++){
					if(result+coins[j]==amount)
						return (depth+1);
					if(result+coins[j]<amount)
					queue.offer((Integer)(result+coins[j]));
				}
			}
		}
		 
		 return -1;
	 }

3.2 引入hashSet去重

初步分析超时是重复计算的内容太多了，所以引入hashSet把结果存储进去，这样就能去除每一层重复的内容，如下

 public int coinChange(int[] coins, int amount) {
        Integer result=0;
         int size=0;
         int depth=0;
         
         Queue queue = new LinkedList();         
         Set<Integer> hashSet = new HashSet<Integer>();
                        
         int resultSum=0;        
         if(amount ==0)
             return 0;
         
         for(int i=0;i<coins.length;i++)
         {
             queue.offer((Integer)coins[i]);            
             if(coins[i]==amount)
                 return 1;
         }
             
         while(!queue.isEmpty()){
            size = queue.size();
            depth++;
            hashSet.removeAll(hashSet);
            System.out.println(size);
            
            resultSum=0;
            for(int i=0;i<size;i++){
                result = (Integer) queue.poll();
                System.out.println("the result is : "+result);
                for(int j =0; j<coins.length;j++){
                    if(result+coins[j]==amount)
                        return (depth+1);
                    if(result+coins[j]<amount){
                        hashSet.add((Integer)(result+coins[j]));
                        resultSum++;
                        //hashSet
                    }                   
                }
            }
            for(Integer str:hashSet){
                queue.offer(str);
            }
        }    
         return -1;
    }
}

但是仍然超时

3.3 百思不得其解，转而看官方题解，柳暗花明获得去重方法，通过

【参考内容】https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/

【改进方法】对所有相加数据做一次记忆，resultStore，因为先出现的记忆内容一定是早于下一次的，所以记忆内容有效。

public static int coinChange(int[] coins, int amount) {
		Integer result=0;
		 int size=0;
		 int depth=0;
		 int []resultStore=new int[amount]; 
		 
		 Queue queue = new LinkedList();		 
		 Set<Integer> hashSet = new HashSet<Integer>();
						
		 int resultSum=0;		 
		 if(amount ==0)
			 return 0;
		 
		 for(int i=0;i<coins.length;i++)
		 {
			 queue.offer((Integer)coins[i]);			
			 if(coins[i]==amount)
				 return 1;
		 }
			 
		 while(!queue.isEmpty()){
			size = queue.size();
			depth++;
			hashSet.removeAll(hashSet);
			System.out.println(size);
			
			resultSum=0;
			for(int i=0;i<size;i++){
				result = (Integer) queue.poll();
				System.out.println("the result is : "+result);
				for(int j =0; j<coins.length;j++){
					if(result+coins[j]==amount)
						return (depth+1);
					
					if(result<0)
						continue;
					if(result+coins[j]<0)
						continue;
						
					if(result+coins[j]>amount)
						continue;
					
					if(resultStore[result+coins[j]-1]==1)
						continue;
					
					if(result+coins[j]<amount){
						resultStore[result+coins[j]-1]=1;
						hashSet.add((Integer)(result+coins[j]));
						resultSum++;
						//hashSet
					}					
				}
			}
			for(Integer str:hashSet){
				queue.offer(str);
	        }
		}	 
		 return -1;
	 }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法