Java - BFS easy to understand


  • 2
    X
    public class Solution {
        public int coinChange(int[] coins, int amount) {
            Arrays.sort(coins);
            Set<Integer> set = new HashSet<>();
            int count = 1;
            if (amount == 0)
                return 0;
            
            for (Integer coin : coins)    
            {
                if (amount == coin)
                    return count;
                else if (amount > coin)
                    set.add(amount - coin);
            }
            
            
            while (true)
            {
                Set<Integer> newSet = new HashSet<>();
                count++;
                for (int newAmount : set)
                {
                    for (int coin : coins)
                    {
                        if (newAmount == coin)
                            return count;
                        else if (newAmount > coin)
                        {
                            if (newAmount - coin >= coins[0])
                                newSet.add(newAmount - coin);
                        }
                        else
                            break;
                    }
                }
                
                if (newSet.isEmpty())
                    break;
                else
                    set = newSet;
            }
            
            return -1;
        }
    }
    

    Updated to use array:

    public class Solution {
        public int coinChange(int[] coins, int amount) {
            int coinsLength = coins.length;
            Arrays.sort(coins);
            Queue<Integer> q = new LinkedList<>();
            int count = 1;
            if (amount == 0)
                return 0;
            boolean[] cache = new boolean[amount];
            //Set<Integer> cache = new HashSet<>();
            
            for (Integer coin : coins)    
            {
                if (amount == coin)
                    return count;
                else if (amount > coin)
                {
                    q.add(amount - coin);
                    cache[amount - coin] = true;
                }
            }
            
            while (true)
            {
                Queue<Integer> newQ = new LinkedList<>();
                count++;
                while (!q.isEmpty())
                {
                    int newAmount = q.poll();
                    for (int i = coinsLength - 1; i >= 0; i--)
                    {
                        if (newAmount == coins[i])
                            return count;
                        else if (newAmount > coins[i])
                        {
                            int value = newAmount - coins[i];
                            if (value >= coins[0] && !cache[value])
                            {
                                newQ.add(value);
                                cache[value] = true;
                            }
                        }
                    }
                }
                
                if (newQ.isEmpty())
                    break;
                else
                    q = newQ;
            }
            
            return -1;
        }
    }

  • 0
    E

    Try to store results into an int array, it would be much faster than using HashSet.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.