Algorithm: Leetcode Contest 393

Maximum Prime Difference

Solution

class Solution {
    public int maximumPrimeDifference(int[] nums) {
        int first = -1, last = -1;
        
        for(int i = 0 ; i < nums.length; i++) {
            if (isPrime(nums[i])) {
                if (first == -1) {
                    first = i;
                } 
                last = i;
            } 
        }
        
        return last - first;
    }
    
    private boolean isPrime(int number) {
        if(number == 0 || number == 1) {
            return false;
        }
        
        for(int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

Retro

1. how to determine a number is prime number
   1. to save time, use square root as upper boundary

Kth Smallest Amount With Single Denomination Combination

Solution

class Solution {
    public long findKthSmallest(int[] coins, int k) {
        // first should have a max heap - represent current combinations
        PriorityQueue<Integer> max = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        
        // second, should have a min heap - represent the unused combinations 
        PriorityQueue<Integer> min = new PriorityQueue<>();
        for(int coin: coins) {
            min.add(coin);
        }
        
        Arrays.sort(coins);
        
        int curComb = 0;
        while(max.size() < k) {
            curComb = min.poll();
            max.add(curComb);
            
            for(int coin: coins) {
                if (curComb % coin == 0) {
                    int newComb = curComb;
                    newComb += coin;
                    while(min.contains(newComb)) {
                        newComb += coin;
                    }
                    min.add(newComb);
                }
            }
        }
        
        return max.poll();
    }
}

Retro

1. the most important thing is to understand the problem, for example I misunderstand this statement:

   However, you are not allowed to combine coins of different denominations.

2. How to create a max heap or min heap