May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3584|回复: 16
收起左侧

Google 跪经

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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). Waral 鍗氬鏈夋洿澶氭枃绔,

评分

1

查看全部评分

本帖被以下淘专辑推荐:

立华奏 发表于 2016-10-27 02:33:15 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
用Wiggle sort II的解法? LeetCode 324
回复 支持 反对

使用道具 举报

 楼主| anqboy 发表于 2016-10-27 02:50:25 | 显示全部楼层
关注一亩三分地微博:
Warald
刚翻了一下
是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? 如果是全字母,遍历一遍然后再循环输出就好了
. from: 1point3acres.com/bbs
显然不行吧,如果是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最 ...
. visit 1point3acres.com for more.
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. more info on 1point3acres.com
比如 字符串 abb,用hashmap的话,结果还是abb吧

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴我之前想的有点简单,不过还是做出来了。需要一个array做map,还需要一个priorityqueue来根据字母出现的次数排序。复杂度仍然是O(n). 鍥磋鎴戜滑@1point 3 acres
. From 1point 3acres bbs
补充内容 (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...这么循环
. 1point 3acres 璁哄潧
比如字符串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 | 显示全部楼层
木易wen 发表于 2016-10-27 22:55
.鐣欏璁哄潧-涓浜-涓夊垎鍦lc358低配版。。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
总感觉这低配版,有更简单的方法做。。。
回复 支持 反对

使用道具 举报

头像被屏蔽
gamesover 发表于 2016-10-30 12:16:33 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-29 02:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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