一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 966|回复: 10
收起左侧

[其他] 讨论一道简单的算法题最优解法

[复制链接] |只看干货 |刷题
我的人缘0

升级   7.5%


分享帖子到朋友圈
digitalmo | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (3)
 
 
0% (0)    👎

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
前几天面试,一道被标为简单的题,只写出了O(n^2)的解法,目测应该有更快的解法。题目很短:

“给定一个字符串,返回最长的,通过一次以上重复可以组成该字符串的子字符串。例如:给定 'abcabc' 返回 'abc'(重复两次),给定 'aaaa',返回aa(重复两次)。给定 'abcabcabc' 返回'abc'(重复三次)“

我的思路是既然要重复起码一次,那么就先从原字符串的中间 index 开始,慢慢减少到1,看看从头到index的子字符串能不能构成原字符串。不过这样的复杂度是 O(n^2)。找了下其他人的讨论,感觉使用哈希表记录每个字符出现的次数好像也没什么用。大家有什么好的思路吗?

评分

参与人数 1大米 +3 收起 理由
14417335 + 3

查看全部评分


上一篇:R 语言有没有非常好的刷题网站?
下一篇:分享一个学习算法的网站~
我的人缘0

升级   86.67%

yangff 2020-7-2 19:42:09 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   100% (15)
 
 
0% (0)    👎
本帖最后由 yangff 于 2020-7-2 19:53 编辑

一个KMP楼上说了,你KMP做完会有个next数组告诉你每个位置和前缀的最长匹配,然后你就要在每个位置试着找到一个最长的匹配使得去掉这部分之后的字符串的最长匹配也能这么长。

另外lz想到这步应该不难想到如果你枚举的长度不能整除字符串长度那它必然不能重复若干次后构成原串,把这部分剪掉的话就是O(n sqrtn).
你再往前想一步,把原串哈希一下,每个合法的长度比较n/l次哈希值,O(sigma(n)) 这玩意有个上界。。是e^0.57721 * n * loglogn. 四舍五入一下大概比O(n)慢一点点



回复

使用道具 举报

我的人缘0

升级   4.71%

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
https://en.m.wikipedia.org/wiki/...d_substring_problem

变种 你可以建trie的时候把index加上,就能判断边界了。 O(n)

回复

使用道具 举报

我的人缘0

升级   15.86%

mylarryshell 2020-6-30 04:28:01 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (35)
 
 
2% (1)    👎
kmp... 紫薯紫薯紫薯
回复

使用道具 举报

我的人缘0

升级   10%

david_smith 2020-7-3 04:11:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (733)
 
 
2% (18)    👎
KMP 算法, O(N)

但是,KMP 算法默认输入String,是由一个另String,重复几次得到的。
如果不是,KMP会给出错误结果,比如, abcxyzabc,  KMP会返回abc, 但是还要再验证一下
回复

使用道具 举报

我的人缘0

升级   7.5%

 楼主| digitalmo 2020-7-10 21:06:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (3)
 
 
0% (0)    👎
@yangff @david_smith,发现另外一个 O(n) 方法。比 KMP 要简单

假定所求字符串 K 为 abcabcabc,length 为 K 的长度,我们可以先将 K 复制一份得到 K`,

K = abcabcabc
K` = abcabcabc

然后从 K 中,在 [1: length] 区间中,找到一个 index 满足,K[index:] = K`[:length-index],在这个例子中,index 为 3。

abcabcabc
      abcabcabc

由于 K 的可重复性,我们可以推断出,K[:index] 一定能够重复组成 K,但是不一定是最长的那个。例如 abababab 需要返回的是 abab 而不是 ab。这时候就要找最长的长度 N ,N 为 index 的倍数并且小于等于 1/2 length。仅有当 N 能够被 length 整除的情况下,N 才是正确的答案。在第二个例子中,N 等于 4。优化的话我们不需要使用K`,只需要使用双指针即可。

评分

参与人数 1大米 +4 收起 理由
14417335 + 4

查看全部评分

回复

使用道具 举报

我的人缘0

升级   36%

striges1111 2020-7-11 02:22:00 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (795)
 
 
1% (9)    👎
本帖最后由 striges1111 于 2020-7-11 02:23 编辑
digitalmo 发表于 2020-7-10 21:06
@yangff @david_smith,发现另外一个 O(n) 方法。比 KMP 要简单

假定所求字符串 K 为 abcabcabc,length ...

恕我愚钝
strcmp是O(n),每个位置都要strcmp一下,不是O(n^2)么?当然可以考虑用rotational hash的方法,但是这种hash不是100%保险的,最差可能还是O(n^2)
回复

使用道具 举报

我的人缘0

升级   7.5%

 楼主| digitalmo 2020-7-11 10:36:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (3)
 
 
0% (0)    👎
@striges1111 代码如下:

[Python] 纯文本查看 复制代码
def StringPeriods(str):
  if len(str) <= 1:
    return -1
  length = len(str)
  up_pointer = 1
  down_pointer = 0
  while up_pointer < length:
    if str[down_pointer] == str[up_pointer]:
        down_pointer += 1
        up_pointer += 1
    else:
        up_pointer += 1
  down_length = length - down_pointer
  if down_length == length:
      return -1
  maximum = length // down_length
  for i in range(maximum-1, -1, -1):
    if length % (i*down_length) == 0:
        return str[:i*down_length]
  return -1

print(StringPeriods('aaaaaaabaaaaaaab'))
print(StringPeriods('abcabcabc'))
print(StringPeriods('abab'))
print(StringPeriods('abababab'))
print(StringPeriods(''))
print(StringPeriods('abcd'))
print(StringPeriods('ababab'))

# abc
# ab
# abab
# -1
# -1
# ab

评分

参与人数 1大米 +4 收起 理由
14417335 + 4

查看全部评分

回复

使用道具 举报

我的人缘0

升级   0%

baonudesifeizha 2020-7-12 02:51:33 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (8)
 
 
11% (1)    👎
肯定是要重复的嘛。。。二分这个重复的长度然后跟后面的check一下  比如ab这个碰上c就gg了     但是abc==abc 这个过程我们可以用hash搞也阔以纯瞎搞   
回复

使用道具 举报

我的人缘0

升级   0%

baonudesifeizha 2020-7-12 02:53:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (8)
 
 
11% (1)    👎
kmp倒是阔以用来求重复周期段   i-ne[i]就是   
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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