一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1610|回复: 16
收起左侧

Google 跪经

[复制链接] |试试Instant~ |关注本帖
anqboy 发表于 2016-10-27 02:09:18 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
re-order a string so that no adjecent characters are the same.e.g. caat --> cata or acat or acta....

跪在Follow up
Time limitation: O(n)

评分

1

查看全部评分

立华奏 发表于 2016-10-27 02:33:15 | 显示全部楼层
用Wiggle sort II的解法? LeetCode 324
回复 支持 反对

使用道具 举报

 楼主| anqboy 发表于 2016-10-27 02:50:25 | 显示全部楼层
刚翻了一下
是LC358的变种
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-10-27 03:00:23 | 显示全部楼层
再次确认是358
回复 支持 反对

使用道具 举报

33847682 发表于 2016-10-27 03:10:49 | 显示全部楼层
rearrange string k distance apart?用长度为26的数组计数 可以做到o(26n)不知道能不能满足要求?
回复 支持 反对

使用道具 举报

null_point_exc 发表于 2016-10-27 04:54:09 | 显示全部楼层
Count sort? 如果是全字母,遍历一遍然后再循环输出就好了
回复 支持 反对

使用道具 举报

1peter 发表于 2016-10-27 14:02:03 | 显示全部楼层
null_point_exc 发表于 2016-10-27 04:54
Count sort? 如果是全字母,遍历一遍然后再循环输出就好了

显然不行吧,如果是abb 呢 循环输出还是abb,结果要求bab,但是O(n)不能sort,所以不知道哪个character最多
回复 支持 反对

使用道具 举报

木易wen 发表于 2016-10-27 22:55:01 | 显示全部楼层
lc358低配版。。
回复 支持 反对

使用道具 举报

null_point_exc 发表于 2016-10-28 04:34:05 | 显示全部楼层
1peter 发表于 2016-10-27 14:02
显然不行吧,如果是abb 呢 循环输出还是abb,结果要求bab,但是O(n)不能sort,所以不知道哪个character最 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
count sort 就是o(n). sort 结果是几个a 几个b ..循环的意思是abcdef...这么循环
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2016-10-28 07:06:30 | 显示全部楼层
这个不难吧。全部收进hashmap,key是字母,value是出现次数。然后遍历hashmap组成新的字符串,直到全部字母用尽,肯定不会出现重复的。复杂度O(n)

补充内容 (2016-10-28 07:10):
其实不需要hashmap,一个数组足以,26个位置,代表26个字母
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2016-10-29 00:02:56 | 显示全部楼层
cgxy1991 发表于 2016-10-28 07:06
这个不难吧。全部收进hashmap,key是字母,value是出现次数。然后遍历hashmap组成新的字符串,直到全部字母 ...

比如 字符串 abb,用hashmap的话,结果还是abb吧
回复 支持 反对

使用道具 举报

null_point_exc 发表于 2016-10-29 00:12:03 | 显示全部楼层
sunnyroom 发表于 2016-10-29 00:02
比如 字符串 abb,用hashmap的话,结果还是abb吧

for(char c = 'a'; c <= 'z'; c++ )
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2016-10-29 03:43:39 | 显示全部楼层
sunnyroom 发表于 2016-10-29 00:02
比如 字符串 abb,用hashmap的话,结果还是abb吧

我之前想的有点简单,不过还是做出来了。需要一个array做map,还需要一个priorityqueue来根据字母出现的次数排序。复杂度仍然是O(n)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2016-10-29 03:44):
我做出了leetcode358
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2016-10-29 10:44:32 | 显示全部楼层
null_point_exc 发表于 2016-10-28 04:34
count sort 就是o(n). sort 结果是几个a 几个b ..循环的意思是abcdef...这么循环

比如字符串abb,count的结果是1个a, 2个b
你怎么循环得到结果?
回复 支持 反对

使用道具 举报

oily 发表于 2016-10-29 10:59:45 | 显示全部楼层
通过O(n)另外建一个次数为key,字母数组为value的map就好,这样的话就可以从高的value处理到低的value
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2016-10-29 11:43:43 | 显示全部楼层

总感觉这低配版,有更简单的方法做。。。
回复 支持 反对

使用道具 举报

gamesover 发表于 2016-10-30 12:16:33 | 显示全部楼层
sunnyroom 发表于 2016-10-29 11:43
总感觉这低配版,有更简单的方法做。。。
. 鍥磋鎴戜滑@1point 3 acres
我觉得最简单的就是这个了
https://discuss.leetcode.com/topic/48260/java-15ms-solution-with-two-auxiliary-array-o-n-time
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 01:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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