快手算法岗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

相关推荐

10-07 20:48
门头沟学院 Java
听说改名就会有offer:可能是实习上着班想到后面还要回学校给导师做牛马,看着身边都是21-25的年纪,突然emo了了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 1 评论
分享
牛客网
牛客企业服务