一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 469|回复: 7
收起左侧

[Leetcode] Shortest Palindrome O(N)复杂度在OJ上超时了,求解答

[复制链接] |试试Instant~ |关注本帖
biktop 发表于 2015-9-24 23:03:23 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
我在leetcode的论坛提问了,但是估计不会有什么人看

这里是链接,里面包含代码:https://leetcode.com/discuss/60128/o-n-time-in-best-case-aaaa-aaaaa-dont-pass-time-limit

希望有人可以解决一下我的疑惑,谢谢!
hanrui_542 发表于 2015-9-25 00:41:36 | 显示全部楼层
就我的经验来看leetcode给出的error不像你想象的那么准确。超时说的是你的算法,是statistically, 不是对某一个test case的。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-25 00:49:09 | 显示全部楼层
那个test case不是"aaaaa....aaaaa",而是"aaaaa....cd......aaaaa",cd分别在20000,20001位置上,只是用肉眼看的话根本找不到。

在OJ上可以用输出语句调试,在主函数的循环里加一句println,就能发现这个循环实际上是被执行了好多次。说明原字符串并不是回文,也就是说原字符串一定不全是a。然后只要遍历一下就发现原字符串中的异类了。
回复 支持 反对

使用道具 举报

 楼主| biktop 发表于 2015-9-25 00:59:41 | 显示全部楼层
stellari 发表于 2015-9-25 00:49
那个test case不是"aaaaa....aaaaa",而是"aaaaa....cd......aaaaa",cd分别在20000,20001位置上,只是用 ...

真是太感谢了,看来O(N^2)的算法是不够的,难怪是属于hard级别的题目,有什么好的算法可以降低复杂度吗
回复 支持 反对

使用道具 举报

 楼主| biktop 发表于 2015-9-25 01:00:33 | 显示全部楼层
hanrui_542 发表于 2015-9-25 00:41
就我的经验来看leetcode给出的error不像你想象的那么准确。超时说的是你的算法,是statistically, 不是对 ...

已经找出问题了,还是要进一步降低时间复杂度,谢谢!
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-25 01:07:01 | 显示全部楼层
biktop 发表于 2015-9-25 00:59
真是太感谢了,看来O(N^2)的算法是不够的,难怪是属于hard级别的题目,有什么好的算法可以降低复杂度吗

要实现O(N)时间复杂度的话,恐怕只能上Manacher/KMP之类的算法了吧。不过我用C++写O(N^2)是能过的。
回复 支持 反对

使用道具 举报

面假空虚 发表于 2015-9-25 10:37:03 | 显示全部楼层
OJ上给你报超时然后说最后一个test case是啥啥啥,并不是说你在这个case上超时了,而是说执行到这个case的时候加上前面case的总时间超时了。这个要O(n)解的话就用kmp算法就可以,然后还有一个很不错的递归解法我给你个链接,底下有我替楼主写的思路注释https://leetcode.com/discuss/512 ... rsive-java-solution
回复 支持 反对

使用道具 举报

 楼主| biktop 发表于 2015-9-25 23:14:37 | 显示全部楼层
面假空虚 发表于 2015-9-25 10:37
OJ上给你报超时然后说最后一个test case是啥啥啥,并不是说你在这个case上超时了,而是说执行到这个case的 ...

太感谢了 :)
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 01:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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