一道google的题目，至今没看到正确答案。

duduhaha

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

x

rearrange-a-string-so-that-all-same-characters-become-at-least-d-distance-away

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

uot;.

这就意味着贪心先放频率最多的字符是错误的，大家有什么好解法吗？这是google面经的常见题目。

hanabeast

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

heroic

直接用256大小数组表示string啊每次找最大值也是O(1)的时间，其实对于所有有限的字母字符串直接开数组用下标计数会比hashmap或heap快很多。

hanabeast

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

leolyq

用hashtable统计每个字符出现的次数，并按次数从大到小排序；然后分桶存放每个字符，具体做法是，分n个桶，每个桶长度为distance，按照第一步的顺序，按序将每个字符插入到每个桶里，注意最后一个桶大小可能小于distance的处理，应该就可以。

duduhaha

hanabeast 发表于 2016-4-3 13:42
public String reArrangeChar(String str, int k) {
if (str == null || str.length() == 0) {
retu ...

你这个答案应该是对的，厉害啊！

牛仔很忙

hanabeast 发表于 2016-4-3 13:42
public String reArrangeChar(String str, int k) { if (str == null || str.length() == 0) { return ...

正解，真是厉害👍

raindreamer

这代码是正解？
这不就是错误的贪心吗。。。能过LZ说的sample吗

adiggo

是不是得backtracking ……… try所有情况……

yalyka

hanabeast 发表于 2016-4-3 00:42
public String reArrangeChar(String str, int k) {
if (str == null || str.length() == 0) {
retu ...

仿佛看到了群里的小伙伴！

caiqi8877

hanabeast 发表于 2016-4-3 13:42
public String reArrangeChar(String str, int k) {
if (str == null || str.length() == 0) {
retu ...

这个代码并没有解决楼主所说的情况啊。。。