一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 430|回复: 2
收起左侧

[Leetcode] PriorityQueue 顺序?

[复制链接] |只看干货 |leetcode, 刷题
我的人缘0

升级   55%


分享帖子到朋友圈
Musclekai | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (310)
 
 
1% (6)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
本帖最后由 Musclekai 于 2020-9-18 14:53 编辑

按道理pq只能保证peek是最大/最小,其他都是无序。而且poll()完queue顺序会发生变化。
可是为什么下面这个解法的pq能一直保持poll的都是最大/最小值啊?lc621
[Java] 纯文本查看 复制代码
class Solution {
    public int leastInterval(char[] tasks, int n) {
int intervalCount = 0;
    Map<Character, Integer> taskFrequencyMap = new HashMap<>();
    for (char chr : tasks)
      taskFrequencyMap.put(chr, taskFrequencyMap.getOrDefault(chr, 0) + 1);

    PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<Map.Entry<Character, Integer>>(
        (e1, e2) -> e2.getValue() - e1.getValue());

    // add all tasks to the max heap
    maxHeap.addAll(taskFrequencyMap.entrySet());

    while (!maxHeap.isEmpty()) {
      List<Map.Entry<Character, Integer>> waitList = new ArrayList<>();
      int k = n + 1; // try to execute as many as 'k+1' tasks from the max-heap
      for (; k > 0 && !maxHeap.isEmpty(); k--) {
        intervalCount++;
        Map.Entry<Character, Integer> currentEntry = maxHeap.poll();
        if (currentEntry.getValue() > 1) {
          currentEntry.setValue(currentEntry.getValue() - 1);
          waitList.add(currentEntry);
        }
      }
      maxHeap.addAll(waitList); // put all the waiting list back on the heap
      if (!maxHeap.isEmpty())
        intervalCount += k; // we'll be having 'n' idle intervals for the next iteration
    }

    return intervalCount;
    }
}


评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分


上一篇:上完61b和cs170之后并不能帮助多少leetcode...
下一篇:分享一下5月份面试国内几家大公司的面试题,有找国内工作的同学可以参考下
我的人缘0

升级   11%

本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   97% (41)
 
 
2% (1)    👎
pq其实就是heap,poll了一个出来之后,会调整heap让下一个依旧是最大/最小的啊

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分

回复

使用道具 举报

我的人缘0

升级   52.57%

Mr.Brain 2020-9-18 22:12:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   89% (612)
 
 
10% (69)    👎
PQ是每次poll完之后的peak都还是最值,不是只有第一次

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表