美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册

点击进入授权页面

只需一步,快速开始

  • 帅爆!宝马X2量产版曝光:颜值无敌
  • 手动挡急刹车要不要踩离合?实测对比震惊
  • 最后一辆法拉利旗舰卖出:本世纪最贵的汽车!
  • 汽车购置税优惠要缩水:要买趁早
  • 喜欢大力关车门?看看这些...
  • 2017年北京市将实施“世界最严”锅炉排放标准
  • 国产“守望先锋”上线差评如潮:丢人丢到Steam
  • 收13万聘礼后失踪 游戏里的新娘竟是男保安
  • LOL女主播夏美酱一大波新照福利满满:发育得更好了
  • 《古墓丽影》手游移植PC:回合制游戏竟要求GTX 970!
  • 美国9月房价指数反弹,并升至历史纪录新高-美国房产信息
  • 有分析认为到美国留学的学生数目持续上升的趋势有可能在特朗普上台後终止-美国留学指 ...
  • 10个你永远不会有100万美元的原因
  • 2016年销售额近5000亿美元,2017年全球广告支出将放缓
  • 石油巨头正处于麻烦之中
  • 我在印度花了98分钟在ATM队列
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3012|回复: 8

内推面经 -问一道算法题max length of subsequence string matching subs- 唐人社区| ...

[复制链接]
TA在交友中心
0 0 23
  @ME:   

9

主题

365

帖子

388

积分

中级会员

Rank: 3Rank: 3

积分
388
QQ
发表于 2016-10-3 20:20:34 | 显示全部楼层 |阅读模式
分享到:
{$content}

唐人社区-北美华人论坛-内推面经版-问一道算法题max length of subsequence string matching subs


  JobHunting
标 题: 问一道算法题max length of subsequence string matching subs


昨天做了道challenge的题,输入两个String, a and b, 要求返回能够满足(
subsequence of a) == (substring of b)的最大length。a和b的characters都是a-z。
我的做法代码复杂而且时间
复杂度也感觉不好。为了不误导大家,大牛先试试有没有好的解法,我再抛砖。

--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?


回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

TA在交友中心
0 0 30
  @ME:   

12

主题

82

帖子

105

积分

注册会员

Rank: 2

积分
105
QQ
发表于 2016-10-3 21:09:06 | 显示全部楼层
JobHunting
标  题: Re: 问一道算法题max length of subsequence string matching


这样说来dp可以解决?但我遇到的是不是2 substring match, 是subsequence matches
substring。
2 substring match f(i,j)=f(i-1)(j-1)+1
subsequence matches substring, 难道要遍历row(i-1)?   f(i,j)=Max(f(i-1,0)...
.f(i-1,j-1))+1
这样一来就是O(m*n*n)了,与dfs没区别了。

不过好像每个row去掉所有0,都是递增序列,可能可以找最后的值 f(i,j) = f(i-1, x
) ( x=max(0, j-1) and f(i-1, x)>0).
如果用一个一维array来记录所有row最大值, 应该可以吧。我试试。

【 在 hardpack (hardpack) 的大作中提到: 】
: 这个?
: https://en.m.wikipedia.org/wiki/Longest_common_substring_problem
: 面试要问这个,多半是来找茬的。




--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?

TA在交友中心
0 0 55
  @ME:   

25

主题

82

帖子

136

积分

注册会员

Rank: 2

积分
136
QQ
发表于 2016-10-3 23:03:27 | 显示全部楼层
JobHunting
标  题: Re: 问一道算法题max length of subsequence string matching subs


subsequance 和substring有什么区别?
如果是longest common substring,好像是用二维dp来解?
--
TA在交友中心
0 0 48
  @ME:   

22

主题

82

帖子

127

积分

注册会员

Rank: 2

积分
127
QQ
发表于 2016-10-3 23:12:41 | 显示全部楼层
JobHunting
标  题: 问一道算法题max length of subsequence string matching subs


昨天做了道challenge的题,输入两个String, a and b, 要求返回能够满足(
subsequence of a) == (substring of b)的最大length。a和b的characters都是a-z。
我的做法代码复杂而且时间
复杂度也感觉不好。为了不误导大家,大牛先试试有没有好的解法,我再抛砖。

--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?

TA在交友中心
0 0 35
  @ME:   

15

主题

84

帖子

116

积分

注册会员

Rank: 2

积分
116
QQ
发表于 2016-10-3 23:47:57 | 显示全部楼层
JobHunting
标  题: Re: 问一道算法题max length of subsequence string matching


Subsequence 是指可以删除任意一些characters后的string (保持原顺序)

https://en.wikipedia.org/wiki/Subsequence


【 在 laoqiu (老Q) 的大作中提到: 】
: subsequance 和substring有什么区别?
: 如果是longest common substring,好像是用二维dp来解?



--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?

TA在交友中心
0 0 46
  @ME:   

18

主题

95

帖子

140

积分

注册会员

Rank: 2

积分
140
QQ
发表于 2016-10-4 00:10:27 | 显示全部楼层
JobHunting
标  题: Re: 问一道算法题max length of subsequence string matching


试了一下DP,一维array记录所有row最大值不行,必须找最后的值 f(i,j) = f(i-1, x
) ( x=max(0, j-1) and f(i-1, x)>0). 可以用存一个index list, 用binary search,
O(m*n*log(m)) 。 我觉得这个题还是直接用dfs好了,最坏情况是b里很多duplicate,
O(m*n*n)。

【 在 coldknight (冷骑士) 的大作中提到: 】
: 这样说来dp可以解决?但我遇到的是不是2 substring match, 是subsequence
matches
:  substring。
: 2 substring match f(i,j)=f(i-1)(j-1)+1
: subsequence matches substring, 难道要遍历row(i-1)?   f(i,j)=Max(f(i-1,0).
..
: .f(i-1,j-1))+1
: 这样一来就是O(m*n*n)了,与dfs没区别了。
: 不过好像每个row去掉所有0,都是递增序列,可能可以找最后的值 f(i,j) = f(i-1,
x
: ) ( x=max(0, j-1) and f(i-1, x)>0).
: 如果用一个一维array来记录所有row最大值, 应该可以吧。我试试。


--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?
TA在交友中心
0 0 48
  @ME:   

24

主题

90

帖子

137

积分

注册会员

Rank: 2

积分
137
QQ
发表于 2016-10-4 00:18:07 | 显示全部楼层
JobHunting
标  题: Re: 问一道算法题max length of subsequence string matching


今天返回来一看这题,马上O(m*n) dp写出了。状态太重要了。

【 在 coldknight (冷骑士) 的大作中提到: 】
: 试了一下DP,一维array记录所有row最大值不行,必须找最后的值 f(i,j) = f(i-1,
x
: ) ( x=max(0, j-1) and f(i-1, x)>0). 可以用存一个index list, 用binary
search,
:  O(m*n*log(m)) 。 我觉得这个题还是直接用dfs好了,最坏情况是b里很多
duplicate,
:  O(m*n*n)。
: matches
: ..
:  x



--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?
TA在交友中心
0 0 1074
  @ME:   

23

主题

1112

帖子

2186

积分

金牌会员

Rank: 6Rank: 6

积分
2186
QQ
发表于 2016-10-25 21:43:11 | 显示全部楼层
鼎力支持!!

0

主题

943

帖子

1887

积分

金牌会员

Rank: 6Rank: 6

积分
1887
发表于 2016-10-29 20:34:21 | 显示全部楼层
顶起顶起顶起
您需要登录后才可以回帖 登录 | 立即注册  

本版积分规则

玩美生活FunInUSA.net 华人娱乐论坛发布的内推面经 -问一道算法题max length of subsequence string matching subs- 唐人社区| ...帖子由网友提供或转载于网络,若发布的内推面经 -问一道算法题max length of subsequence string matching subs- 唐人社区| ...侵犯了您的权益,请联系我们.
1&1 Hosting

Copyright ©2011 FunInUSA.com All Right Reserved.  Powered by Discuz! X3.0 小黑屋

本站信息均由会员发表,不代表美国华人网FunInUSA立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA

安全联盟认证 安全联盟认证

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