9月4号google电面【已挂】

edna 发表于 2015-9-13 01:37
首先判断有没有合法输出，只要比较最高频出现的次数t，要求的间隔k，和总长度n之间是否满足n > (t-1)*k就可 ...

觉得因该是n>=t*k-1 而不是n>(t-1)*k? LZ可以跑看看这个example
"A", "B", "C", "A", "B", "C", "A",
n=7
k = 3
t = 3

say543 发表于 2015-9-13 11:11
觉得因该是n>=t*k-1 而不是n>(t-1)*k? LZ可以跑看看这个example
"A", "B", "C", "A", "B", "C", "A",
n ...

首先，你这个例子是一个正确情况，所以按照我给出的，n>(t-1)*k, 7 > (3-1)*3，没问题啊。

mint0715 发表于 2015-9-13 06:37
http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distan ...

这个里面的解法是错的啊
aabbcc，2 就不对

zxy_snow 发表于 2015-9-13 13:41
这个里面的解法是错的啊
aabbcc，2 就不对

对你发现问题了，直接贪心从高频隔d挨个放进去是错的
所以请看里面下面的评论。

mint0715 发表于 2015-9-13 14:25
对你发现问题了，直接贪心从高频隔d挨个放进去是错的
所以请看里面下面的评论。

http://articles.leetcode.com/201 ... hone-interview.html

这里的解法貌似是对的。
我按照这个解法写了一遍，生成了几万个样例验证了下，没出错。。

mint0715 发表于 2015-9-13 14:25
对你发现问题了，直接贪心从高频隔d挨个放进去是错的
所以请看里面下面的评论。

就是复杂度很高，是n*m，m是不同值的个数，姑且认为复杂度是N*N吧

zxy_snow 发表于 2015-9-13 14:37
就是复杂度很高，是n*m，m是不同值的个数，姑且认为复杂度是N*N吧

这个做法等价于，每次把所有字符按频率排序，取出其中频率最高的d个，从高到低接在result后面。
假如每个位置可能的字符只有常数种，那么这个解法是O(n)。

gp89757 发表于 2015-9-12 00:03
应该是只要最高频的可以满足 就有解 否则无解 最高频的是否满足取决于 (k-1)*minDistance < size of list

赞！但是有个小问题，算的时候是不是要考虑最高频是否唯一呢，假设最高频出现次数为k,有m个字母的最高频都是k,那么是否应该是(k-1)*minDis+(m-1)<size of list呢？
举个栗子就是aaabbbc要求minDis=3,aaa能放但是bbb就不行了

夜行码农耗子 发表于 2015-9-14 02:22
赞！但是有个小问题，算的时候是不是要考虑最高频是否唯一呢，假设最高频出现次数为k,有m个字母的最高频 ...

你是对的
现在就是感觉如何输出valid的比较困难
考虑aaaabbbcc d=2 答案应该是 bababacac

edna 发表于 2015-9-13 11:03
第一个例子是错的啊，如果是aaa, bb, cc然后间距是3，那么abcabca是合法的，但是你这个返回了个fail？

你的对的我的有bug...看看有没有人能想出更好的solution...