Algorithm: Leetcode Contest 381

Challenge 2

Count the Number of Houses at a Certain Distance I

my solution

public int[] countOfPairs(int n, int x, int y) {
    int dist; 
    int[] res = new int[n];

    for(int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            dist = Math.min(
                j - i, // direct distance
                Math.min(
                    Math.abs(i - x) + 1 + Math.abs(j - y),
                    Math.abs(i - y) + 1 + Math.abs(j - x)
                )
            );
            res[dist - 1] += 2;
        }
    }

    return res;
}

retro

• it’s important to have sensitivity to figure out the algorithm prototype

Challenge 3

Minimum Number of Pushes to Type Word II

my solution

class Solution {
    public int minimumPushes(String word) {
        // count the occurence of each character
        Map<Character, Integer> map = new HashMap<>();
        for(char c: word.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, 0);
            }
            
            map.put(c, map.get(c) + 1);
        }
        
        // sort char based on occurence, leverage PQ
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node node1, Node node2) {
                return node2.count - node1.count;
            }
        });
        
        for(Map.Entry<Character, Integer> entry: map.entrySet()) {
            pq.add(new Node(entry.getKey(), entry.getValue()));
        }
        
        // robin round on chars
        int count = 8;
        int round = 1;
        Node cur;
        int res = 0;
        while(!pq.isEmpty()) {
            cur = pq.poll();
            res += cur.count * round;
            count--;
            if (count < 1) {
                count = 8;
                round++;
            }
        }
        
        
        return res;
    }
    
    class Node {
        char c;
        int count;
        
        public Node(char c, int count) {
            this.c = c;
            this.count = count;
        }
    }
}

Retro

• how to write priority queue with customized comparator
• how to iterate on map, Map.Entry entry: map.entrySet()