快手算法岗A卷笔试第三题

最长公共子串，用dp数组，但是当生成的数组长度很长的时候，内存溢出了。虽然代码写出来了，但是因为溢出，最后ac了0%。请教一下，解决方法是什么？#快手笔试##快手##笔试题目#
全部评论
同。蹲个答案
点赞 回复 分享
发布于 2020-03-22 21:06
应该不会溢出啊……生成的序列最长399998个元素
点赞 回复 分享
发布于 2020-03-22 21:12
同，求大神解答😂
点赞 回复 分享
发布于 2020-03-22 21:14
我还是感觉应该有啥数学规律😂
点赞 回复 分享
发布于 2020-03-22 21:15
俺觉得不是溢出的问题，就算溢出小的case也可能通过啊，0%的那种一般我都怀疑是输入输出问题
点赞 回复 分享
发布于 2020-03-22 21:19
用树状数组或者线段树做dp, O(nlgn)
点赞 回复 分享
发布于 2020-03-22 21:21
这个题目不可能有数学规律吧，题目中的序列生成算法不就是伪随机数生成算法么。
点赞 回复 分享
发布于 2020-03-22 22:05
可以把LCS转化成LIS做，具体可以参考https://www.nowcoder.com/discuss/388827?toCommentIpt=1，代码最后一行改成 int ans = -1; for(int i = 0; i < na; i++) ans = max(ans, max(dp[i][0], dp[i][1])); 应该就没有问题了…… 当然现在没法提交我也没办法保证没有细节上的错误就是……上面大佬说的树状数组应该就是类似于这个方法
点赞 回复 分享
发布于 2020-03-22 23:12
可以考虑转化成最长上升子序列问题 B序列遍历的过程中 每个位置的权值就是A序列相同元素的位置 以这个权值做最长上升子列 有2个的话转移两次即可 可以用线段树维护dp数组达到nlogn
点赞 回复 分享
发布于 2020-03-22 23:28
我尝试过转换成LIS问题，复杂度O(nlogn) ，但是在python下也还是时间超过@BiteTheDust
点赞 回复 分享
发布于 2020-03-23 20:15

相关推荐

11-22 16:39
已编辑
华中科技大学 光通信工程师
秋招就到这儿吧。
秋招真的是一场持久战，每一天都有不同的心情。。。&nbsp;随着华为的审批保温，差不多整个秋招也就结束了。&nbsp;BG：双九，保研，本硕都是电子信息类（光电方向），研究方向是光通信这一块。&nbsp;秋招一共投递了17家公司，我的想法很明确，最后的最后的最后是希望能够做解决方案一类，也就是技术+销售结合的事儿。但这样的岗要求很高，基本很少校招，都是社招或内部研发输出一线这样的模式。所以我投递的岗包括技术岗和非技术岗。&nbsp;收到面试邀请9家，获得offer（含保温）9家，已拿到8offer，预计9offer。面试通过率100%。所有的面经都在主页了，欢迎各位大佬指正批评。🙇&nbsp;5月准备华为客经实习开始陆...
zachsun：华科硕士给13级？有点逆天了吧
25届秋招总结
点赞 评论 收藏
分享
昨天 11:40
北京城市学院 项目经理
点赞 评论 收藏
分享
头像
11-07 01:12
重庆大学 Java
朋友问我这几天干嘛呢
精致的小松鼠人狠话不多：签哪了哥
点赞 评论 收藏
分享
11-18 11:13
已编辑
Columbia University 算法工程师
秋招终于到此结束
秋招，是一场大型持久战，我真的累了。。。在美留子一枚，上周四接到腾讯音乐的开奖电话了，50+W，应该是SSP，没有一丝犹豫的接了，很知足！更重要的原因是真的一点都面不动了，太内耗了，一开始还是我要干翻这个世界的状态，到后来，有个班上就行了。Timeline如下：8.19网申-8.23笔试-8.27初试-8.30复试-9.6面委-9.18hr面试-10.15意向-11.14开奖。没错，老娘已经订好了去冰岛的机票，要疯，要浪，要happy！&nbsp;BG：9本QS50美硕，本硕都是学人工智能相关的，研究方向主要是推荐算法。其实想想，我也是挺卷的。人在美国，没有国内同学的实习便利，但又特别怕秋招简历上没有实...
拿到ssp可以么：有钱真好啊，有钱还拿到50w+真好啊，50w+还能wlb更好了，我要嫉妒到发疯了
你最想要的公司福利是？
点赞 评论 收藏
分享
点赞 1 评论
分享

招聘动态

查看更多

快手

销售类投递专区

字节跳动

2025校园招聘

快手Star

2025届招聘

全站热榜

正在热议
# 25届秋招总结 #
278680次浏览 2410人参与
# 如果实习可以转正，你会不会放弃秋招 #
206044次浏览 2807人参与
# 北方华创开奖 #
24511次浏览 263人参与
# 地方国企笔面经互助 #
3253次浏览 7人参与
# 学历or实习经历，哪个更重要 #
47386次浏览 368人参与
# 选完offer后，你后悔学本专业吗 #
16616次浏览 120人参与
# 如何一边实习一边秋招 #
989079次浏览 12623人参与
# 软开人，秋招你打算投哪些公司呢 #
41623次浏览 534人参与
# 数据人的面试交流地 #
436247次浏览 7812人参与
# 0offer是寒冬太冷还是我太菜 #
892709次浏览 7964人参与
# 得物求职进展汇总 #
64840次浏览 674人参与
# 求职遇到的搞笑事件 #
68987次浏览 571人参与
# 你觉得专业和学校哪个对薪资影响最大 #
28920次浏览 215人参与
# 查收我的offer竞争力报告 #
21223次浏览 263人参与
# 你最想要的公司福利是？ #
43457次浏览 161人参与
# 没有实习经历，还有机会进大厂吗 #
808917次浏览 13885人参与
# 来聊聊机械薪资天花板是哪家 #
67465次浏览 460人参与
# 当你面对裁员会如何？ #
26519次浏览 156人参与
# 一觉醒来，我觉醒了超级打工人系统 #
3626次浏览 38人参与
# 应届生被毁约被毁意向了怎么办 #
28833次浏览 247人参与
# 面试体验感最好的是哪家？ #
84177次浏览 822人参与
牛客网
牛客企业服务