📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3063| 回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

问一道google原题(贪心)

全局:

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

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

x
字符串重新排列,让里面不能有相同字母在一起。比如aaabbb非法的,要让它变成ababab。给一种即可

这一题我的想法是用hashmap存起来,比如上面这个例子就是(a,3),(b,3),然后在一遍遍的扫hashpmap,遇到不为0的就接上去。

我想问的是这道题贪心怎么做?以下是另一个帖子里的回复,新建一个priorityqueue<HashMap>??然后取到了次数最多的那个字符以后怎么取下一个字符?难道要把最大的pop出来?
就是把当前剩余数量最多的字符优先排。
先统计每个字符出现的次数,用一个最大堆维护着可以快速取得当前剩余最大字符

上一篇:有没有在 iPhone 上刷题的好方法?
下一篇:排序好的数组中找第一个重合点

本帖被以下淘专辑推荐:

推荐
caiqi8877 2016-5-15 07:01:45 | 只看该作者
全局:
Ulu2005 发表于 2016-3-5 00:14
这道题应该就是这道 http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-becom ...

aaabbcc d=2
这个算法就失效了
回复

使用道具 举报

🔗
Ulu2005 2016-3-5 00:14:34 | 只看该作者
全局:
这道题应该就是这道 http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distance-away/
在distance = 2时的特例,主楼那个想法是对的,具体可以看链接里。
回复

使用道具 举报

🔗
handsomecool 2016-5-19 12:45:52 | 只看该作者
全局:
我和楼主一样只想到了一遍遍不停扫hashmap的办法,链接里的heap做法有问题。请问有比不停扫更好的办法吗? 不停扫hashmap的复杂度是O(kN)  k是distinct char的数目, N是string长度。
回复

使用道具 举报

🔗
jefferyy 2016-5-21 00:16:20 | 只看该作者
全局:
Java code here: http://yuanhsh.iteye.com/blog/2231105
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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