一亩三分地论坛

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

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

g家电面

[复制链接] |试试Instant~ |关注本帖
uha714 发表于 2016-9-13 12:22:12 | 显示全部楼层 |阅读模式

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

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

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

x
判断字符串是否存在重复次数>k的连续子串,讨论了下时间复杂度和优化技巧. Waral 鍗氬鏈夋洿澶氭枃绔,
hxtang 发表于 2016-10-4 04:25:17 | 显示全部楼层
liurudahai 发表于 2016-10-4 03:43
这个不对吧,应该还是O(n^3),因为他们没说对于输入字符串必须要从第一个字符开始就开始这个连续重复K次 ...

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

使用道具 举报

fatalme 发表于 2016-9-14 06:18:10 来自手机 | 显示全部楼层
Prefix tree可以 O(N^2)复杂度。
回复 支持 0 反对 1

使用道具 举报

JeremyLi 发表于 2016-9-13 13:59:23 | 显示全部楼层
求问楼主这题有什么好做法吗?
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-13 21:52:33 | 显示全部楼层
请问这题lz怎么做的呢?
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2016-9-14 04:09:57 | 显示全部楼层
是不是就是LeetCode – Longest Substring Without Repeating Characters?
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-14 04:29:31 | 显示全部楼层
hyliu0000 发表于 2016-9-14 04:09
是不是就是LeetCode – Longest Substring Without Repeating Characters?

不一样的吧
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-14 06:24:57 | 显示全部楼层
这个是Leetcode 395吗?
回复 支持 反对

使用道具 举报

aangel 发表于 2016-9-14 06:53:35 | 显示全部楼层
hxtang 发表于 2016-9-14 06:24
这个是Leetcode 395吗?

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

使用道具 举报

aangel 发表于 2016-9-14 06:55:39 | 显示全部楼层


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

使用道具 举报

hxtang 发表于 2016-9-14 09:05:09 | 显示全部楼层
brute-force的可以遍历所有可能的子串首字符s和循环节长度l,复杂度是O(n^3)
.鐣欏璁哄潧-涓浜-涓夊垎鍦
优化的时候对每个l,似乎可以利用类似KMP的idea把检查所有可能的s合并成一个O(n)时间的sliding window。这样总体复杂度可以改进到O(n2).
回复 支持 反对

使用道具 举报

aangel 发表于 2016-9-14 11:56:16 | 显示全部楼层
hxtang 发表于 2016-9-14 09:05
brute-force的可以遍历所有可能的子串首字符s和循环节长度l,复杂度是O(n^3)

优化的时候对每个l,似乎可 ...

你说的这个优化可以讲的更仔细一点吗?
回复 支持 反对

使用道具 举报

aangel 发表于 2016-9-14 12:14:28 | 显示全部楼层

感觉优化的的话要用trie树来做
回复 支持 反对

使用道具 举报

aangel 发表于 2016-9-14 12:25:50 | 显示全部楼层
hxtang 发表于 2016-9-14 09:05
brute-force的可以遍历所有可能的子串首字符s和循环节长度l,复杂度是O(n^3)
. visit 1point3acres.com for more.
优化的时候对每个l,似乎可 ...
. 鍥磋鎴戜滑@1point 3 acres
你这里说的brute-force的要O(N^4)吧
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-14 21:15:54 | 显示全部楼层
aangel 发表于 2016-9-14 12:25. 鍥磋鎴戜滑@1point 3 acres
你这里说的brute-force的要O(N^4)吧
. 1point3acres.com/bbs
我的理解是找重复>k次的循环串...

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

使用道具 举报

nickmyself 发表于 2016-9-14 21:40:58 | 显示全部楼层
hxtang 发表于 2016-9-14 21:15
我的理解是找重复>k次的循环串...

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

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

使用道具 举报

hyliu0000 发表于 2016-9-14 23:47:33 | 显示全部楼层
hxtang 发表于 2016-9-14 21:15. 鍥磋鎴戜滑@1point 3 acres
我的理解是找重复>k次的循环串...

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

那如果你找到了呢?
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-14 23:53:49 | 显示全部楼层
hyliu0000 发表于 2016-9-14 23:47
那如果你找到了呢?

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

使用道具 举报

hyliu0000 发表于 2016-9-14 23:57:44 | 显示全部楼层
hxtang 发表于 2016-9-14 23:53
问题不就是判断能不能找到吗?找到了返回true,没找到返回false呀。。。

a1a23a456a789

这里面有重复次数大于k的连续子串吗?
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-15 00:00:51 | 显示全部楼层
hyliu0000 发表于 2016-9-14 23:57. 1point 3acres 璁哄潧
a1a23a456a789-google 1point3acres

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

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

使用道具 举报

hyliu0000 发表于 2016-9-15 00:02:42 | 显示全部楼层
hxtang 发表于 2016-9-15 00:00
你没有specify k = ?
如果k=4的话,子串不就是a吗?

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 20:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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