最后一块石头的重量及优先队列讲解

题目

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

最大堆方法解题：

class Solution {
   public int lastStoneWeight(int[] stones) {
       PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
       for (int stone : stones) {
           pq.offer(stone);
       }

       while (pq.size() > 1) {
           int a = pq.poll();
           int b = pq.poll();
           if (a > b) {
               pq.offer(a - b);
           }
       }
       return pq.isEmpty() ? 0 : pq.poll();
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

优先队列：

PriorityQueue<Integer> p = new PriorityQueue<>();
1

优先级队列从队头取元素，从队尾添加元素。默认情况下，队列中的数据是升序排序。

PriorityQueue<Integer> p = new PriorityQueue<>();
p.offer(5);
p.offer(1);
p.offer(3);

while(!p.isEmpty()) {
	System.out.println(p.poll());  //依次打印：1 3 5
}
1
2
3
4
5
6
7
8

方法

和队列的方法基本一样

自定义排序规则

以下代码改变排序规则，从大到小：

PriorityQueue<Integer> queue=new PriorityQueue<>((o1,o2)->o2-o1);
PriorityQueue<Integer> queue= new PriorityQueue<>(Comparator.reverseOrder());
1
2

根据HashMap的value值对HashMap的键值对排序

public static void main(String[] args) {
	HashMap<Integer, Integer> map = new HashMap<>();
	map.put(1, 2);
	map.put(3, 4);
	map.put(5, 6);
	
	Set<Map.Entry<Integer, Integer>> entries = map.entrySet();//获取键值对
	
	//自定义优先队列的排序规则，队列内存放的数据类型是键值对
	//o1，o2都是键值对这样的对象
	PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> {
		return o1.getValue() - o2.getValue();//根据值升序排序
	});
	
	for (Map.Entry<Integer, Integer> entry : entries) {
		queue.offer(entry);//将键值对放到优先队列中
    }
	while(!queue.isEmpty()) {
		System.out.println(queue.poll().getValue());
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21