【Java数据结构与算法】优先队列用法及相关题目解题思路

发布时间:2023-04-04 10:30

Java优先队列API用法

        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2; //o1 - o2 为小顶堆,poll出来的是最小的,反之为大顶堆poll出来的是最大的
            }
        });
        // PriorityQueue queue = new PriorityQueue<>((o1, o2) -> o1 - o2);//简写
        queue.add(2);
        queue.add(1);
        queue.add(3);
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());

相关题目

一手顺子

题目:Alice 手中有一把牌,她想要重新排列这些牌,分成若干组,使每一组的牌数都是 groupSize ,并且由 groupSize 张连续的牌组成。能排成这样返回true,不能返回false

输入:hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
输出:true
解释:Alice 手中的牌可以被重新排列为 [1,2,3],[2,3,4],[6,7,8]。

思路:把牌全放入优先队列,每次取出最小的牌再移除和和这个最小的牌组成顺子的元素,发现移除失败说明找不到这组顺子,返回false
java代码 【模拟/优先队列力扣题解】

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if(hand.length % groupSize != 0) return false;
        //从最小的数开始找对子,找到就把牌丢出来,一直找
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i : hand) {
            queue.add(i);
        }
        while (!queue.isEmpty()) {
            int min  = queue.poll();
            for (int i = 1; i < groupSize; i++) {
                boolean remove = queue.remove(min + i);
                if(!remove) {
                    return false;
                }
            }
        }
        return true;
    }
}

数据流中第K大元素

题目: 设计一个找到数据流中第 k 大元素的类(class)。注意是排序后的第 k 大元素,不是第 k 个不同的元素。
请实现 KthLargest 类:
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后,返回当前数据流中第 k 大的元素。

题目分析: 每次加入一个新的数以后,都返回 第 K 大的元素, (例如:1,2,3 第1大就是返回3)
思路:

  1. 初始化维护一个小顶堆(队列头部是较小的数), 堆的容量控制为k,
  2. add()数据时,如果queue大小不足k ,先给queue内添加元素到k。
  3. 如果queue达到k则大于堆顶就加入堆,然后移除堆顶, 如果小于堆顶,舍弃。 这样堆顶一直都是第K大的数。

代码实现:

class KthLargest {
    PriorityQueue<Integer> queue = new PriorityQueue<>();
    final int k;
    public KthLargest(int k, int[] nums) {
        for(int i : nums) queue.add(i);
        this.k = k;
        //注意这里是while,执行完这句话,queue中有k 或 k-1个数字(题目数据保证,在查找第 k 大元素时,数组中至少有 k 个元素)
        while(queue.size() > k) queue.poll();
    }
    public int add(int val) {
        //当queue中只要k - 1 个元素时,需要将当前值加入queue
        if(queue.size() < k) queue.add(val);
        //否则就是替换元素,加进去一个,退出来一个
        else if(val > queue.peek()) {
            queue.add(val);
            queue.poll();
        }
        return queue.peek();
    }
}

找到和最大的长度为 K 的子序列

题目: 给你一个整数数组 nums 和一个整数 k 。你需要找到 nums 中长度为 k 的 子序列 ,且这个子序列的 和最大 。返回 任意 一个长度为 k 的整数子序列。
子序列 定义为从一个数组里删除一些元素后,不改变剩下元素的顺序得到的数组。


输入:nums = [2,1,3,3], k = 2
输出:[3,3]

题目分析:和最大的子序列,最大的和就是数组中前k大的数字的和, 题目要求返回子序列,相当于返回这些前k大数字按数组的顺序排列的数组。
思路1:复制数组 + 数组排序 + hashMap ,数组排序前k大的数字, hashMap存前k大数字与出现次数,然后遍历原数组,等于hashMap中的就取出来。代码
思路2:

  1. 维护一个大小为k的小顶堆,小顶堆存放数字与对应索引,按数字排序。
  2. 先把数字放入队列,使队列大小达到k, 然后小于堆顶的跳过,大于堆顶的放入队列,再弹出堆顶。
  3. 此时队列中即为前k大数字及其索引,我们取出索引排序后按索引对应的值放入返回数组中

代码实现:

class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        //维护大小为k 的优先队列,队列中存放索引与数值,队列按数值排序。
        for(int i = 0; i < nums.length; i++) {
            if(queue.size() < k) {
               queue.offer(new int[]{i, nums[i]});
           }else if(nums[i] > queue.peek()[1]) {
               queue.offer(new int[]{i, nums[i]});
               queue.poll();
           }
        }
        //取出索引
        int[] ret =new int[k];
        int index = 0;
        while(!queue.isEmpty()) {
            ret[index++] = queue.poll()[0];
        }
        //索引排序
        Arrays.sort(ret);
        //按顺序将数组放入返回数组
        for(int i = 0; i < k; i++) {
            ret[i] = nums[ret[i]];
        }
        return ret;
    }
}

矩阵中战斗力最弱的 K 行

题目:给你一个大小为 m * n 的矩阵 mat,矩阵由若干军人和平民组成,分别用 1 和 0 表示。返回矩阵中战斗力最弱的 k 行的索引,按从最弱到最强排序。
如果第 i 行的军人数量少于第 j 行,或者两行军人数量相同但 i 小于 j,那么我们认为第 i 行的战斗力比第 j 行弱。
军人 总是 排在一行中的靠前位置,也就是说 1 总是出现在 0 之前。

输入示例:

输入:mat =
[[1,1,0,0,0],
[1,1,1,1,0],
[1,0,0,0,0],
[1,1,0,0,0],
[1,1,1,1,1]],
k = 3
输出:[2,0,3]

题目分析: 战斗力最弱的前k个,即矩阵中和最小的前k行。
思路:维护一个大顶堆,按照每行的和排序,和大的排前面,如果和相同,i大的排前面

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        // queue 中保存 i 和 sum
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2)-> {
            if(o2[1] == o1[1]) return o2[0] - o1[0]; //如果sum相等就按i降序
            else return o2[1] - o1[1];
        });

        for(int i = 0; i < mat.length; i++) {
            int[] tem = mat[i];
            int sum = getSum(tem);
            if(queue.size() < k) {
                queue.add(new int[]{i,sum});
            }else {
                //由于 是 i 从小到大遍历的,所有如果栈顶和是相同的,那么栈里的i一定是较小的,满足要求。
                if(sum < queue.peek()[1]) {
                    queue.add(new int[]{i, sum});
                    queue.poll();
                }
            }
        }
        //栈中元素是从大到小的,前k小元素,所以要倒着放入返回数组
        int[] ret = new int[k];
        int index = k - 1;
        while(!queue.isEmpty()) {
            ret[index--] = queue.poll()[0];
        }
        return ret;
    }

    public int getSum(int[] a) {
        int sum = 0;
        for(int i = 0; i < a.length; i++) sum += a[i];
        return sum;
    }
}

吃苹果的最大数目

⭐⭐
精炼题目: apples[i]代表第i天长多少个苹果;days[i]代表第i天长的苹果多少天后腐烂,即腐烂日期为days[i] + i,每天最多吃一个苹果,求最多吃多少苹果。

思路: 用优先队列,存储苹果数量及腐烂日期,每天取最烂的苹果吃【腐烂日期最小,且腐烂日期 > 当前日期】

注意:
1.在小于n天【数组长度】那段时间,先去收果子,然后取果子看有没有果子吃,有就吃一个,没有就不吃。
2.在n天过后,直接计算出未来几天有果子吃。
\"在这里插入图片描述\"

class Solution {
public int eatenApples(int[] apples, int[] days) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        int n = apples.length;
        int ret = 0;
        int curDay = 0;
        while (curDay < n) {
            if(apples[curDay] !=0)
            queue.add(new int[]{apples[curDay], curDay + days[curDay]});
            while (queue.size() > 0) {
                if (queue.peek()[1] > curDay) {
                    ret++;
                    if(--queue.peek()[0] == 0) {
                        queue.poll();
                    }
                    break;
                }else {queue.poll();}
            }
            curDay++;
        }
        while (queue.size() > 0) {
            int[] poll = queue.poll();
            if (poll[1] > curDay){
                int tem = Math.min(poll[1] - curDay, poll[0]);
                ret += tem;
                curDay += tem;
            }
        }
        return ret;
    }
}

练习题

题目 思路 难度

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号