优先级队列PriorityQueue在算法问题中的使用
文章目錄
- 優先級隊列介紹
- 與優先級隊列有關的習題
- [179. 最大數]
- [918. 環形子數組的最大和]
- [1094. 拼車]
- [264. 丑數 II]
- 前k個出現頻率最高的數字
- 用優先級隊列合并k個有序鏈表
- 滑動窗口的最大值
- 其他:對二維數組自定義排序
優先級隊列介紹
優先隊列一般基于二叉堆實現,二叉堆:
堆的根節點的優先級最大(即最大或最小)
父節點的優先級必定大于子節點,兄弟節點的優先級不確定誰大誰小
PriorityQueue:
PriorityQueue是基于二叉堆原理的優先隊列,隊列用動態數組實現。
它是非阻塞的、非線程安全的;
PriorityQueue內部維護了幾個重要屬性:
PriorityQueue的peek()和element()操作是常數時間,add()、offer()、 無參數的remove()以及poll()方法的時間復雜度都是log(N)。
PriorityBlockingQueue和PriorityQueue的實現基本一致區別就是在于加鎖了,并發出了非空信號喚醒阻塞的獲取線程。
1、jdk內置的優先隊列PriorityQueue內部使用一個堆維護數據,每當有數據add進來或者poll出去的時候會對堆做從下往上的調整和從上往下的調整。
2、PriorityQueue不是一個線程安全的類,如果要在多線程環境下使用,可以使用 PriorityBlockingQueue 這個優先阻塞隊列。其中add、poll、remove方法都使用 ReentrantLock 鎖來保持同步,take() 方法中如果元素為空,則會一直保持阻塞。
與優先級隊列有關的習題
[179. 最大數]
(https://leetcode-cn.com/problems/largest-number/)
給定一組非負整數 nums,重新排列每個數的順序(每個數不可拆分)使之組成一個最大的整數。
**注意:**輸出結果可能非常大,所以你需要返回一個字符串而不是整數。
示例 1:
輸入:nums = [10,2] 輸出:"210"示例 2:
輸入:nums = [3,30,34,5,9] 輸出:"9534330" public String largestNumber(int[] nums) { PriorityQueue<String>queue = new PriorityQueue<>((x,y)->(y+x).compareTo(x+y)); for(int i:nums) queue.offer(String.valueOf(i)); String ans=""; while(queue.size()>0) { ans+=queue.poll(); } if(ans.charAt(0)=='0') return"0"; return ans;}[918. 環形子數組的最大和]
(https://leetcode-cn.com/problems/maximum-sum-circular-subarray/)
首先關于一般數組的最大和:
然后環形數組最大和的關鍵是知道最大和是怎么產生的,其實有兩種情況,一個是最大和是數組中間的數字之和(從第0索引到第length-1個索引之間某幾個數之和),另一個是由兩端的產生,(即包含0和length-1索引,但中間有的元素不包含),第二種情況是有負數的情況,如[8,-1,-1,1],這樣需要用所有元素之和減去最小子數組來求,有一種特殊情況,如果全為負數這時候所有元素之和減去最小子數組為0,這個環形數組的最大和應該是元素中最大的那個數,概況:
對于環形數組,分兩種情況。
(1)答案在數組中間,就是最大子序和。例如[1,-2,3,-2];
(2)答案在數組兩邊,例如[5,-3,5]最大的子序和就等于數組的總和SUM-最小的子序和。(一種特殊情況是數組全為負數,也就是SUM-最小子序和==0,最大子序和等于數組中最大的那個)。
[1094. 拼車]
(https://leetcode-cn.com/problems/car-pooling/)
難度中等146
假設你是一位順風車司機,車上最初有 capacity 個空座位可以用來載客。由于道路的限制,車 只能 向一個方向行駛(也就是說,不允許掉頭或改變方向,你可以將其想象為一個向量)。
這兒有一份乘客行程計劃表 trips[][],其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 組乘客的行程信息:
- 必須接送的乘客數量;
- 乘客的上車地點;
- 以及乘客的下車地點。
這些給出的地點位置是從你的 初始 出發位置向前行駛到這些地點所需的距離(它們一定在你的行駛方向上)。
請你根據給出的行程計劃表和車子的座位數,來判斷你的車是否可以順利完成接送所有乘客的任務(當且僅當你可以在所有給定的行程中接送所有乘客時,返回 true,否則請返回 false)。
示例 1:
輸入:trips = [[2,1,5],[3,3,7]], capacity = 4
輸出:false
示例 2:
輸入:trips = [[2,1,5],[3,3,7]], capacity = 5
輸出:true
示例 3:
輸入:trips = [[2,1,5],[3,5,7]], capacity = 3
輸出:true
首先按分別按上車地點和下車地點維護兩個小頂堆。每次比較堆頂元素,并維護當前容量,若下車地點更小(或相等),先下車(當前容量增加),否則上車(當前容量減小),上車時要判斷當前容量是否變成負值,若變成負值應直接返回false。
注意,因為最后一個下車地點一定大于最后一個上車地點,因此按上車地點維護的小頂堆一定先變為空。
[264. 丑數 II]
(https://leetcode-cn.com/problems/ugly-number-ii/)
難度中等
給你一個整數 n ,請你找出并返回第 n 個 丑數 。
丑數 就是只包含質因數 2、3 和/或 5 的正整數。
示例 1:
輸入:n = 10 輸出:12 解釋:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 個丑數組成的序列。示例 2:
輸入:n = 1 輸出:1 解釋:1 通常被視為丑數。要得到從小到大的第 n個丑數,可以使用最小堆實現。
初始時堆為空。首先將最小的丑數 1加入堆。
每次取出堆頂元素 xx,則 xx 是堆中最小的丑數,由于 2x, 3x, 5x 也是丑數,因此將 2x, 3x, 5x 加入堆。
上述做法會導致堆中出現重復元素的情況。為了避免重復元素,可以使用哈希集合去重,避免相同元素多次加入堆。
在排除重復元素的情況下,第 n 次從最小堆中取出的元素即為第 n 個丑數。
public int nthUglyNumber(int n) { int[]ug=new int[]{2,3,5}; PriorityQueue<Long>queue = new PriorityQueue<>(); Set<Long>myset = new HashSet<>();//在添加元素的過程中可能出現非常大的數,因此要用long類型 queue.offer(1L);//1是丑數 myset.add(1L);int ans=1; for(int i = 0;i<n;i++) {long heap=queue.poll();ans = (int)heap;//強制轉化為int類型for(int j = 0;j < ug.length;j++){long temp = heap*ug[j];if(myset.add(temp))//用于去重,如果hashset可以添加成功則證明這個元素沒有出現過,可以添加到堆中queue.offer(temp);} } return ans;}前k個出現頻率最高的數字
public int[] topKFrequent(int[] nums, int k) {Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();for (int num : nums) {occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);}// int[] 的第一個元素代表數組的值,第二個元素代表了該值出現的次數PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {public int compare(int[] m, int[] n) {return m[1] - n[1];//這一步比較不能寫反,否則結果是錯的}});for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {int num = entry.getKey(), count = entry.getValue();if (queue.size() == k) {if (queue.peek()[1] < count) {queue.poll();queue.offer(new int[]{num, count});}} else {queue.offer(new int[]{num, count});}}int[] ret = new int[k];for (int i = 0; i < k; ++i) {ret[i] = queue.poll()[0];}return ret;} }用優先級隊列合并k個有序鏈表
class Status implements Comparable<Status> {int val;ListNode ptr;public Status(int val,ListNode ptr){this.val=val;this.ptr=ptr;}public int compareTo(Status s2){ return ptr.val-s2.val;}}PriorityQueue<Status>queue=new PriorityQueue<Status>();public ListNode mergeKLists(ListNode[] lists) { for(ListNode node:lists) if (node != null) { queue.offer(new Status(node.val,node)); } ListNode head=new ListNode(0); ListNode tail=head; while(!queue.isEmpty()) {Status f=queue.poll();tail.next=f.ptr;tail=f.ptr;if(f.ptr.next!=null)queue.offer(new Status(f.ptr.next.val,f.ptr.next));//這一步比較巧妙,沒有直接展開上面的所有鏈表結點,而是先將鏈表數組中的元素按照第一個結點的大小加入優先級隊列,后再對每一個結點中尋找下一個結點加入隊列 } return head.next;}滑動窗口的最大值
給你一個整數數組 nums,有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k 個數字。滑動窗口每次只向右移動一位。
返回 滑動窗口中的最大值 。
示例 1:
輸入:nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出:[3,3,5,5,6,7]
解釋:
滑動窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
由于出現了最大值,用優先級隊列可以維護每次窗口的最大值,其中用數組下標用來排除窗口之外的元素
public int[] maxSlidingWindow(int[] nums, int k) { int[]ans = new int[nums.length+1-k]; PriorityQueue<int[]>queue = new PriorityQueue<int[]>(new Comparator<int[]>(){@Overridepublic int compare(int[]a1,int[]a2){return a1[0]==a2[0]?a2[1]-a1[1]:a2[0]-a1[0];} }); for(int i = 0;i <k;i++) queue.offer(new int[]{nums[i],i}); int index = 0; ans[0]= queue.peek()[0]; for(int i = k;i<nums.length;i++) {queue.offer(new int[]{nums[i],i});while(queue.peek()[1] <= i-k)//注意這里是while循環不是if判斷queue.poll();ans[i-k+1] = queue.peek()[0];} return ans;}其他:對二維數組自定義排序
Arrays.sort(intervals,new Comparator<int[]>() { @Override public int compare(int[]a,int[]b) {return a[0]==b[0]?b[1]-a[1]:a[0]-b[0]; } });總結
以上是生活随笔為你收集整理的优先级队列PriorityQueue在算法问题中的使用的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: Java大数加法乘法减法、36进制加法
- 下一篇: mysql 共享锁和排他锁 意向锁 记录