美国卖车经历分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 4849|回复: 45
收起左侧

g家电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
uha714 发表于 2016-9-13 12:22:12 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

2016(7-9月) 码农类General 硕士 全职@Google - Other - 技术电面  | Other | 在职跳槽

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

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

x
判断字符串是否存在重复次数>k的连续子串,讨论了下时间复杂度和优化技巧

上一篇:Amazon OA2
下一篇:coursera oa1 9/11 开始的新题
我的人缘0
hxtang 发表于 2016-10-4 04:25:17 | 显示全部楼层
  此人我要顶:
 
71% (5) 【我投】
  此人我要踩:
 
29% (2) 【我投】
liurudahai 发表于 2016-10-4 03:43
这个不对吧,应该还是O(n^3),因为他们没说对于输入字符串必须要从第一个字符开始就开始这个连续重复K次 ...

假设第n个字母跟第n-k相同就画一个x,那么
cdefababab
          xxxx
可以看到有4个连续的x,所以循环子串一共6个字母,循环3次. 一亩-三分-地,独家发布
回复 支持 0 反对 1

使用道具 举报

我的人缘0
fatalme 发表于 2016-9-14 06:18:10 来自手机 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Prefix tree可以 O(N^2)复杂度。
回复 支持 0 反对 1

使用道具 举报

我的人缘0
JeremyLi 发表于 2016-9-13 13:59:23 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
求问楼主这题有什么好做法吗?
回复 支持 反对

使用道具 举报

我的人缘0
william_gong 发表于 2016-9-13 21:52:33 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
请问这题lz怎么做的呢?
回复 支持 反对

使用道具 举报

我的人缘0
hyliu0000 发表于 2016-9-14 04:09:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
是不是就是LeetCode – Longest Substring Without Repeating Characters?

评分

参与人数 1大米 +3 收起 理由
hyliu0001 + 3 很有用的信息!

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
william_gong 发表于 2016-9-14 04:29:31 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
hyliu0000 发表于 2016-9-14 04:09 来源一亩.三分地论坛.
是不是就是LeetCode – Longest Substring Without Repeating Characters?

不一样的吧
回复 支持 反对

使用道具 举报

我的人缘0
hxtang 发表于 2016-9-14 06:24:57 | 显示全部楼层
  此人我要顶:
 
71% (5) 【我投】
  此人我要踩:
 
29% (2) 【我投】
这个是Leetcode 395吗?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
aangel 发表于 2016-9-14 06:53:35 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hxtang 发表于 2016-9-14 06:24
这个是Leetcode 395吗?

不一样的。。重复K次以上的子串
回复 支持 反对

使用道具 举报

我的人缘0
aangel 发表于 2016-9-14 06:55:39 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】


一个字符串总共有N^2的子串,用一个HashMap记录一下HashMap<String,Integer>. more info on 1point3acres
然后看哪个string超过K了?
回复 支持 反对

使用道具 举报

我的人缘0
hxtang 发表于 2016-9-14 09:05:09 | 显示全部楼层
  此人我要顶:
 
71% (5) 【我投】
  此人我要踩:
 
29% (2) 【我投】
brute-force的可以遍历所有可能的子串首字符s和循环节长度l,复杂度是O(n^3)-google 1point3acres

.留学论坛-一亩-三分地优化的时候对每个l,似乎可以利用类似KMP的idea把检查所有可能的s合并成一个O(n)时间的sliding window。这样总体复杂度可以改进到O(n2).
回复 支持 反对

使用道具 举报

我的人缘0
aangel 发表于 2016-9-14 11:56:16 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hxtang 发表于 2016-9-14 09:05
brute-force的可以遍历所有可能的子串首字符s和循环节长度l,复杂度是O(n^3) 来源一亩.三分地论坛.

优化的时候对每个l,似乎可 ...
. 一亩-三分-地,独家发布
你说的这个优化可以讲的更仔细一点吗?
回复 支持 反对

使用道具 举报

我的人缘0
aangel 发表于 2016-9-14 12:14:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
-google 1point3acres
感觉优化的的话要用trie树来做
回复 支持 反对

使用道具 举报

我的人缘0
aangel 发表于 2016-9-14 12:25:50 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hxtang 发表于 2016-9-14 09:05
brute-force的可以遍历所有可能的子串首字符s和循环节长度l,复杂度是O(n^3)
. 1point3acres
优化的时候对每个l,似乎可 ...

你这里说的brute-force的要O(N^4)吧
回复 支持 反对

使用道具 举报

我的人缘0
hxtang 发表于 2016-9-14 21:15:54 | 显示全部楼层
  此人我要顶:
 
71% (5) 【我投】
  此人我要踩:
 
29% (2) 【我投】
aangel 发表于 2016-9-14 12:25
你这里说的brute-force的要O(N^4)吧

我的理解是找重复>k次的循环串...

如果只是有没有找重复次数>k次的子串的话,只要找有没有重复次数>k次的字符就行了,这个扫一遍数据对每个字符的频率计数就能搞定.
回复 支持 反对

使用道具 举报

我的人缘0
nickmyself 发表于 2016-9-14 21:40:58 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hxtang 发表于 2016-9-14 21:15. From 1point 3acres bbs
我的理解是找重复>k次的循环串...

如果只是有没有找重复次数>k次的子串的话,只要找有没有重复次数>k ...

这个方法好机智!
回复 支持 反对

使用道具 举报

我的人缘0
hyliu0000 发表于 2016-9-14 23:47:33 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hxtang 发表于 2016-9-14 21:15
我的理解是找重复>k次的循环串.... 留学申请论坛-一亩三分地

如果只是有没有找重复次数>k次的子串的话,只要找有没有重复次数>k ...

那如果你找到了呢?

评分

参与人数 1大米 +5 收起 理由
krizalio001 + 5 很有用的信息!

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
hxtang 发表于 2016-9-14 23:53:49 | 显示全部楼层
  此人我要顶:
 
71% (5) 【我投】
  此人我要踩:
 
29% (2) 【我投】
hyliu0000 发表于 2016-9-14 23:47
那如果你找到了呢?

问题不就是判断能不能找到吗?找到了返回true,没找到返回false呀。。。
回复 支持 反对

使用道具 举报

我的人缘0
hyliu0000 发表于 2016-9-14 23:57:44 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hxtang 发表于 2016-9-14 23:53
问题不就是判断能不能找到吗?找到了返回true,没找到返回false呀。。。

a1a23a456a789
. 牛人云集,一亩三分地
这里面有重复次数大于k的连续子串吗?

评分

参与人数 1大米 +3 收起 理由
hyliu0001 + 3 很有用的信息!

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
hxtang 发表于 2016-9-15 00:00:51 | 显示全部楼层
  此人我要顶:
 
71% (5) 【我投】
  此人我要踩:
 
29% (2) 【我投】
hyliu0000 发表于 2016-9-14 23:57
a1a23a456a789

这里面有重复次数大于k的连续子串吗?

你没有specify k = ?
如果k=4的话,子串不就是a吗?
回复 支持 反对

使用道具 举报

我的人缘0
hyliu0000 发表于 2016-9-15 00:02:42 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hxtang 发表于 2016-9-15 00:00
你没有specify k = ?
如果k=4的话,子串不就是a吗?

你看到连续两个字了吗?
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-21 16:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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