[Java知识库]优先队列和双优先队列解题

一个优先队列解决

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

    /**
     * leetcode 358
     * 给一个非空字符串和一个整数k，要将这个字符串中的字母进行重新排列，使得重排后的字符串中
     * 相同字母的位置间隔至少为k。
     * 所有输入字符串都由小写字母组成，如果找不到距离至少为k的重排结果，请返回一个空字符串"".
     */
    public String rearrangeString(String s, int k) {
        /**
         * 1.先统计所有字符出现的次数，存入一个HashMap
         * 2.按照重复次数从大到小构建一个大顶堆，把map中的元素装进去
         * 3.创建一个StringBuilder， 创建一个普通队列变量queue同步记录已经加入到stringbuilder中的字符
         * 4.循环遍历大顶堆的字符：
         *                      a.取出一个字符char，把它加入到stringbuilder中
         *                      b.将char的重复次数-1，加入到普通queue中
         *                      c.判断queue中元素是否为k个，如果是，说明stringbuilder中距离上一个字符char已经插入了k个字符
         *                      char字符可以再出现一次，把queue队首元素放入大顶堆
         * 5.大顶堆没有元素时：
         *                  a.stringbuilder的长度和s一样，说明构建完成，返回
         *                  b.stringbuilder的长度和s不一样，说明还有字符在queue中，无法保证k个距离
         */
        if (k <= 1) {
            return s;
        }

        Map<Character, Integer> map = new HashMap<>();

        PriorityQueue<Map.Entry<Character, Integer>> 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<Map.Entry<Character, Integer>> queue = new LinkedList<>();
        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> currentEntry = maxHeap.poll();
            sb.append(currentEntry.getKey());
            currentEntry.setValue(currentEntry.getValue() - 1);
            queue.offer(currentEntry);
            if (queue.size() == k) {
                Map.Entry<Character, Integer> 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服务器中，具体什么时候用要看服务器的权限什么时候排到。

    /**
     * leetcode 1882 使用服务器处理任务
     *
     * 两个整数数组：servers[n] & tasks[m]
     * servers[i]是第i台服务器的权重
     * tasks[j]是第j个任务所需要的时间
     *
     * 你正在运行一个仿真系统，在处理完所有任务后，该系统将会关闭。
     * 每台服务器只能同时处理一项任务。第 0 项任务在第 0 秒可以开始处理，相应地，第 j 项任务在第 j秒可以开始处理。
     * 处理第 j 项任务时，你需要为它分配一台 权重最小 的空闲服务器。
     * 如果存在多台相同权重的空闲服务器，请选择 下标最小 的服务器。
     * 如果一台空闲服务器在第 t 秒分配到第 j 项任务，那么在 t + tasks[j] 时它将恢复空闲状态。
     *
     * 如果没有空闲服务器，则必须等待，直到出现一台空闲服务器，并 尽可能早地处理剩余任务。
     * 如果有多项任务等待分配，则按照 下标递增 的顺序完成分配。
     *
     * 如果同一时刻存在多台空闲服务器，可以同时将多项任务分别分配给它们。
     *
     * 构建长度为m 的答案数组 ans ，其中 ans[j] 是第 j 项任务分配的服务器的下标。
     *
     * 返回答案数组 ans 。
     */
    public int[] assignTasks(int[] servers, int[] tasks) {
        /**
         * 优先队列busy 存储工作中的服务器(t - 该服务器结束工作的时间, idx - 该服务器的编号)
         *      要满足队首t最小，t相等时则idx最小
         * 优先队列idle 存储空闲的服务器(w - 该服务器的权重, idx - 该服务器的编号)
         *      要满足队首w最小，w相等时则idx最小
         *
         * 算法流程：
         *        1.初始将所有服务器servers放入idle中，并用一个时间戳ts记录当前时间，初始化0
         *        2.遍历每个任务task：
         *                         a.因为第i个任务必须在时间i时开始，因此需要将ts置为ts与i的较大值
         *                         b.需要将优先队列busy中满足t <= ts的服务器依次取出并放入优先队列idle
         *                         c.如果此时idle中无服务器，说明需要等待一台服务器完成任务，因此可以将ts
         *                             置为busy中队首服务器完成任务的时间t，并再执行b步
         *                         d.此时可以给第i个任务安排服务器，即为idle的队首服务器，将其取出并放入busy
         */
        PriorityQueue<int[]> busy = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        PriorityQueue<int[]> 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 计算流的中位数

    /**
     * 计算得到一个流的中位数
     * 奇数个值：所有数值排序后位于中间的数值
     * 偶数个值：所有数值排序后中间两个数的平均值
     */

    /**
     * 大顶堆小顶堆排序算法
     */
    /**
     * 大顶堆保留较小的一半，一堆保留一半，
     * 且n为偶数的时候，长度为 n / 2, 为奇数的时候，长度为 (n - 1) / 2
     */
    PriorityQueue<Integer> smaller;
    /**
     * 小顶堆保留较大的一半
     * 且n为偶数的时候，长度为 n / 2, 为奇数的时候，长度为 (n + 1) / 2，也就是说小顶堆个数要大于大顶堆
     */
    PriorityQueue<Integer> 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;
    }