优先队列和双优先队列解题

leetcode 358 重新安排字符串相同字符间隔k

    
    public String rearrangeString(String s, int k) {
        
        if (k <= 1) {
            return s;
        }

        Map map = new HashMap<>();

        PriorityQueue> maxHeap =
                new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        for (Character c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        maxHeap.addAll(map.entrySet());
        StringBuilder sb = new StringBuilder();
        Queue> queue = new linkedList<>();
        while (!maxHeap.isEmpty()) {
            Map.Entry currentEntry = maxHeap.poll();
            sb.append(currentEntry.getKey());
            currentEntry.setValue(currentEntry.getValue() - 1);
            queue.offer(currentEntry);
            if (queue.size() == k) {
                Map.Entry entry = queue.poll();
                if (entry.getValue() > 0) {
                    maxHeap.add(entry);
                }
            }
        }
        return sb.length() == s.length() ? sb.toString() : "";
    }

leetcode 1882 使用服务器处理任务

这道题更重要的借鉴意义在于如何从题目中抽象过程：

使用两个优先队列的考虑是要对【servers的权重】和【tasks需要的时间】排序，

busy服务器队列需要对【任务执行的时间】从小到大排序，

idle服务器队列需要对【空闲服务器权重】从小到大排序。

因此使用两个优先队列，且队列中保存的是不同的int[]数组：

busy优先队列中保存的数组【int[]{任务执行时间，机器编号}】；

idle优先队列中保存的数组【int[]{服务器权重，机器编号}】。

如果busy队首服务器的时间<=当前时间戳ts，则代表在当前时间ts时，busy队首服务器已经完成任务，可以出队。

从busy队中出来的服务器要重新组数组，行式为 int[]{服务器权重，机器编号}，并加入到idle服务器中，具体什么时候用要看服务器的权限什么时候排到。

    
    public int[] assignTasks(int[] servers, int[] tasks) {
        
        PriorityQueue busy = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        PriorityQueue idle = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

        for (int i = 0; i < servers.length; i++) {
            idle.add(new int[]{servers[i], i});
        }

        int ts = 0;
        int[] ans = new int[tasks.length];
        for (int i = 0; i < tasks.length; i++) {
            ts = Math.max(ts, i);
            while ((!busy.isEmpty() && busy.peek()[0] <= ts) || idle.isEmpty()) {
                int[] busyServer = busy.poll();
                idle.add(new int[]{servers[busyServer[1]], busyServer[1]});
                ts = busyServer[0];
            }
            int[] server = idle.poll();
            ans[i] = server[1];
            int end = tasks[i] + ts;
            busy.add(new int[]{end, server[1]});
        }
        return ans;
    }

leetcode 计算流的中位数

    

    
    
    PriorityQueue smaller;
    
    PriorityQueue larger;
    public MedianFinder() {
        smaller = new PriorityQueue<>(Comparator.reverseOrder());
        larger = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // 保持两端的平衡
        if (smaller.size() != larger.size()) {
            larger.add(num);
            smaller.add(larger.poll());
        } else {
            // 当两个堆个数相同时，先添加到大顶堆，再从大顶堆出队添加到小顶堆
            // 是为了保证小顶堆个数大于大顶堆
            smaller.add(num);
            larger.add(smaller.poll());
        }
    }

    public double findMedian() {
        return smaller.size() != larger.size() ? larger.peek() : (larger.peek() + smaller.peek()) / 2.0;
    }