发布时间:2023-04-04 10:30
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 大元素的类(class)。注意是排序后的第 k 大元素,不是第 k 个不同的元素。
请实现 KthLargest 类:
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后,返回当前数据流中第 k 大的元素。
题目分析: 每次加入一个新的数以后,都返回 第 K 大的元素, (例如:1,2,3 第1大就是返回3)
思路:
代码实现:
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();
}
}
⭐
题目: 给你一个整数数组 nums 和一个整数 k 。你需要找到 nums 中长度为 k 的 子序列 ,且这个子序列的 和最大 。返回 任意 一个长度为 k 的整数子序列。
子序列 定义为从一个数组里删除一些元素后,不改变剩下元素的顺序得到的数组。
输入:nums = [2,1,3,3], k = 2
输出:[3,3]
题目分析:和最大的子序列,最大的和就是数组中前k大的数字的和, 题目要求返回子序列,相当于返回这些前k大数字按数组的顺序排列的数组。
思路1:复制数组 + 数组排序 + hashMap ,数组排序前k大的数字, hashMap存前k大数字与出现次数,然后遍历原数组,等于hashMap中的就取出来。代码
思路2:
代码实现:
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;
}
}
题目:给你一个大小为 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;
}
}
题目 | 思路 | 难度 |
---|---|---|