快手算法岗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-19 16:15
已编辑
中南大学 Java
点赞 评论 收藏
分享
11-21 15:22
淘天集团_HR
点赞 评论 收藏
分享
11-17 12:23
已编辑
四川音乐学院 营销
点赞 评论 收藏
分享
11-07 13:23
Nanyang Technological University 自然语言处理
想找个大厂日常实习，半年以上
这个bg能找到吗
爱看电影的杨桃allin春招：我感觉你在炫耀
点赞 评论 收藏
分享
11-20 17:40
西安邮电大学 有线传输工程师
点赞 评论 收藏
分享
点赞 1 评论
分享

招聘动态

查看更多

快手

销售类投递专区

字节跳动

2025校园招聘

快手Star

2025届招聘

全站热榜

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