优先队列 - wenzhoullq/leetcode GitHub Wiki
用一个treeSet维护点,用优先队列维护区间长度
- 题目
改一行代码即可,经典模板,适合单源并且是坐标(0,0)到(m-1,n-1)的最小权重路径和
int leny=grid.length,lenx=grid[0].length;
int[][] direct={{0,1},{0,-1},{1,0},{-1,0}},
dp=new int[leny][lenx];
for(int i=0;i<leny;i++) Arrays.fill(dp[i],Integer.MAX_VALUE);
dp[0][0]=0;
Queue<int[]> q=new PriorityQueue<>((a,b)->dp[a[0]][a[1]]-dp[b[0]][b[1]]);
q.add(new int[]{0,0});
while(!q.isEmpty()){
int[] temp=q.poll();
int y=temp[0],x=temp[1];
for(int[] dir:direct){
int yy=y+dir[0],xx=x+dir[1];
if(yy<0||yy==leny||xx<0||xx==lenx) continue;
int t=Math.max(dp[y][x],);//改这里即可
if(t>=dp[yy][xx]) continue;
dp[yy][xx]=t;
q.add(new int[]{yy,xx});
}
}
return dp[leny-1][lenx-1];
TreeSet维护空闲的节点,优先队列维护完成的节点
int[] room =new int[n];
TreeSet<Integer> free = new TreeSet<Integer>(); //按题目要求排序
Queue<pair> q= new priorityQueue<>();//按结束的时间排序,如果结束的时间相同,看具体要求排序
for(int i = 0 ; i < len ; i++ ){
while(!q.isEmpty()&&q.peek.endtime<=start) free.add(q.poll().index);
//按要求题意入队,如果不没有空闲节点,直接挑选最早出来的节点出队
}
先确定一维的顺序,然后从大到小(从小到大选择),不断剔除不需要的
Queue<int[]> q = new PriorityQueue<>((a,b)->();//具体要求具体处理
for(int i = 0 ; i < len ; i++ ){
int[] temp = new int[2];
temp[0] = efficiency[i];
temp[1] = speed[i];
q.add(temp);
}
Queue<Integer> q2 =new PriorityQueue<>();
long sum = 0 , ans = 0;
while(!q.isEmpty()){
int[] temp = q.poll();
sum+=temp[1];
q2.add(temp[1]);
if(q2.size()>k) sum-=q2.poll();
ans=Math.max(ans,sum*temp[0]);//具体要求具体处理
}
return (int)(ans%mod);