Longest Palindromic Substring

miss_snow 发表于 2015-3-26 10:27
所以我认为是leetcode的bug
5*10^8差不多是1s，理论上这个O(n^2)的复杂度是完全hold住的，而且应该是绰 ...

抱歉我有点没跟上，5*10^8是什么数字？

stellari 发表于 2015-3-26 10:40
抱歉我有点没跟上，5*10^8是什么数字？

500000000大概是单纯跑循环这个是1s吧
还是5000000有点记不太清了
但是1000000这个级别是能够hold住的

miss_snow 发表于 2015-3-26 10:47
500000000大概是单纯跑循环这个是1s吧
还是5000000有点记不太清了
但是1000000这个级别是能够hold住的

你的意思是进行5*10^8次空循环（我假设“单纯跑循环”的意思是“空循环”），无论在什么电脑上跑都需要1s？这逻辑不通啊。况且，楼主之所以TLE，主要原因不是在循环本身，而是耗在内存分配和回收上。不信的话，你可以在我的AC代码中加一句

Boolean[][] ref2 = new Boolean[len][len];

然后立刻会TLE。

这不能算OJ的bug，更多地应该说是Java的分配和垃圾回收效率比较低而已。

stellari 发表于 2015-3-26 11:41
你的意思是进行5*10^8次空循环（我假设“单纯跑循环”的意思是“空循环”），无论在什么电脑上跑都需要1s ...

这个只是用来粗略判断复杂度的
正常的复杂度判断完全没问题
像Boolean[][] ref2=new Boolean[len][len]如果每个最里层的循环都要用到，完全可以放到for循环的外面操作，当作全局变量，何必放到里面？如果非要放到最内层的循环都要用到，当作局部变量，也可以重置数值，而不必new，否则都mle了，所以这个举例没有意义。或者你直接拿具体的题目说也好，至少我没遇到过两层for循环，然后每个都要重新new Boolean[len][len]这种类似的。因为如果这样子举例，单层for循环，再调用一个new总可以找到mle或者tle的方法。
你可以看看正常逻辑的代码，两层for循环之内的都要进行什么操作，就知道5*10^8是基本符合条件的。至于java效率低的问题……1k的数据量，n^2，1s跑完是完全没问题的，其他oj这种题目我做过很多，1k是很标准的O（n^2）做法。

stellari 发表于 2015-3-26 11:41
你的意思是进行5*10^8次空循环（我假设“单纯跑循环”的意思是“空循环”），无论在什么电脑上跑都需要1s ...

还有一个比较“致命”的问题
如果是要考察O(n)的算法，1k的数据量太小了，至少10^6吧

miss_snow 发表于 2015-3-26 12:22
这个只是用来粗略判断复杂度的
正常的复杂度判断完全没问题
像Boolean[][] ref2=new Boolean[len][len] ...

抱歉我没有说清楚。

我的意思当然是保留楼主对2维数组的分配方式，也就是把：

Boolean[][] ref2 = new Boolean[len][len]

放到函数的最开头（所有循环之外）去。仅是这样做的话就足够引起这道题的TLE了。

stellari 发表于 2015-3-26 13:34
抱歉我没有说清楚。

我的意思当然是保留楼主对2维数组的分配方式，也就是把：

10^6都会t只能说leetcode有bug了，或者oj自身的问题
楼主如果面试的时候说了1k的数据量，就只管O(n^2)说吧，1k都要O(n)真的太任性

如果你想试试其他的oj，poj绝对有比这个还难的问题，比如括号匹配，同样的数据量，java过没问题
所以我还是认为这个是leetcode的问题

给了1k的数据量，还要O(n)来解决，实在多此一举

miss_snow 发表于 2015-3-26 13:49
10^6都会t只能说leetcode有bug了，或者oj自身的问题
楼主如果面试的时候说了1k的数据量，就只管O(n^2)说 ...

Interesting.