PriorityQueue

Reorganize String

• 给一个string, 需要重新生成一个新的string, 要求相邻两个char不能重复

• 可以把input转化成charToCnt dict, 然后存成node, key is char, val is cnt

• 建一个maxHeap, sort by cnt

• 每次从maxHeap中pop一个 candidate1， 如果candidate1.val == prevChar, 则需要再pop一个candidate2

class Solution {
    /*
    Node-> (char, cnt)
    maxHeap<Node> sort by cnt
    every time pop 2 elements from maxHeap, candidate1 and candidate2
    keep track of prevChar
    if both candidate1 and candidate1 are same as prevChar, then means cannot reorganzie to a new string
    
    improvement:
    we don't really need to pop 2 element every time, just when cur element is same as prev, then pop 2nd one.
    */
    public class Node {
        char val;
        int cnt;
        public Node(char val, int cnt) {
            this.val = val;
            this.cnt = cnt;
        }
    }
    
    public String reorganizeString(String S) {
        if (S== null || S.length() == 0) return "";
        Map<Character, Integer> charToCnt = new HashMap<>();
        for (char c : S.toCharArray()) {
            int cnt = charToCnt.getOrDefault(c, 0);
            charToCnt.put(c, cnt + 1);
        }
        PriorityQueue<Node> maxHeap = new PriorityQueue<>(new Comparator<Node>(){
            @Override
            public int compare(Node a, Node b) {
                return b.cnt - a.cnt;
            }
        });
        for (Character c : charToCnt.keySet()) {
            int cnt = charToCnt.get(c);
            maxHeap.offer(new Node(c, cnt));
        }
        StringBuilder sb = new StringBuilder();
        char prev = '#';
        while (!maxHeap.isEmpty()) {
            Node firstCandidate = maxHeap.poll();
            if (prev != '#') {
                if(firstCandidate.val != prev) {
                    sb.append(firstCandidate.val);
                    prev = firstCandidate.val;
                    firstCandidate.cnt--;
                    if (firstCandidate.cnt > 0) {
                        maxHeap.offer(firstCandidate);
                    }
                } else if (!maxHeap.isEmpty() && maxHeap.peek().val != prev) {
                    Node secondCandidate = maxHeap.poll();
                    sb.append(secondCandidate.val);
                    prev = secondCandidate.val;
                    secondCandidate.cnt--;
                    if (secondCandidate.cnt > 0) {
                        maxHeap.offer(secondCandidate);
                    }
                    maxHeap.offer(firstCandidate);
                } else {
                    return "";
                }
            } else {
                sb.append(firstCandidate.val);
                prev = firstCandidate.val;
                firstCandidate.cnt--;
                if (firstCandidate.cnt > 0) {
                    maxHeap.offer(firstCandidate);
                }
            }
        }
        return sb.toString();
    }
}

Task Scheduler

• 好题！

• 先用一个freqMap存charToCnt

• 然后再用一个maxHeap来存map.Entry

• 注意while循环里不能pop完就直接push, 要避免下一次pop出来是重复的task

• 所以要先pop出所有的task,存在list里

• 再update task.value(), 再push from list to heap

class Solution {
    /*
    map, charToCnt
    minHeap<Map.Entry>   sort by cnt, descending
    
    int counter = n;
    while(count-- > 0) {
        //pop from heap
        //不能pop完就直接push, 要避免下一次pop出来是重复的task
        //所以要先pop出所有的task,存在list里
        //再update task.value(), 再push from list to heap
    
    }
    
    
    */
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> charToCnt = new HashMap<>();
        for (char task : tasks) {
            charToCnt.put(task, charToCnt.getOrDefault(task, 0) + 1);
        }
        
        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a,b) ->(b.getValue() - a.getValue()));
        for (Map.Entry<Character, Integer> entry : charToCnt.entrySet()) {
            maxHeap.offer(entry);
        }
        int cnt = 0;
        while (!maxHeap.isEmpty()) {
            int interval = n + 1; //注意不是n
            //先pop出所有的task,存在list里
            List<Map.Entry<Character, Integer>> list = new ArrayList<>();
            while (interval > 0 && !maxHeap.isEmpty()) {
                Map.Entry<Character, Integer> entry = maxHeap.poll();
                list.add(entry);
                interval--;
                cnt++;
            }
            //update task.value(), 再push from list to heap
            for (Map.Entry<Character, Integer> entry : list) {
                entry.setValue(entry.getValue() - 1);
                if (entry.getValue() > 0) {
                    maxHeap.offer(entry);
                }
            }
            
            if (!maxHeap.isEmpty()) {
                cnt += interval;
            }
        }
        return cnt;
    }
}

High Five

• TreeMap + minHeap

public int[][] highFive(int[][] items) {
        //treeMap + minHeap
        Map<Integer, PriorityQueue<Integer>> map = new TreeMap<>();
        for (int i = 0; i < items.length; i++) {
            int id = items[i][0];
            if (!map.containsKey(id)) {
                map.put(id, new PriorityQueue<>());
            }
            PriorityQueue<Integer> scores = map.get(id);
            scores.offer(items[i][1]);
            while (scores.size() > 5) {
                scores.poll();
            }
        }
        int[][] res = new int[map.size()][2];
        int idx = 0;
        for (int key : map.keySet()) {
            PriorityQueue<Integer> scores = map.get(key);
            int sum = 0;
            while (!scores.isEmpty()) {
                sum += scores.poll();
            }
            res[idx][0] = key;
            res[idx][1] = sum / 5;
            idx++;
        }
        return res;
    }