这算不算leetcode的OJ的一个bug？

xytan123 发表于 2015-1-3 00:32
我把你的代码第5行修改成了或者还是不行，提示有一个case runtime error. 我觉得应该不是内存分配的问题

被你发现了，我也才刚刚意识到问题没这么简单

之前以为是内存分配错误，把int dp[s.size()+1];改成int dp[65535];过了
但其实代码其他地方有错误
if(dp[i-dp[ i ]]>0){
需要改成
if(i-dp[ i ]>0){

Myth_Legend 发表于 2015-1-4 02:44
被你发现了，我也才刚刚意识到问题没这么简单

之前以为是内存分配错误，把int dp[s.size()+1];改成int ...

你如果这样改了就只用分配s.size()个空间就行了。而且还有两行可以注释掉也能过。65536那个改法，我没太想明白。我猜测是不是跟OJ上复用class，也复用了内存，所以你初始化一个大数组，后面那个反例的dp[-1]恰好=0了。

王可雪 发表于 2015-1-4 04:10
你如果这样改了就只用分配s.size()个空间就行了。而且还有两行可以注释掉也能过。65536那个改法，我没太 ...

dp[i-dp[i+1]+2]=dp;

dp[i+1-dp[i+1]+1]=dp[i+1];
这两句是干嘛的啊？我注释掉了也能过。

          i    i+1
         ↑
    ( ... )
   ↓
    i-dp[i+1]+2
    (把这个的表值设成dp 有啥用啊？如果他前面还有括号组，为啥要把它赋成dp[i+1]？)

xytan123 发表于 2015-1-4 09:17
dp+2]=dp;

dp+1]=dp;

那是题主的code，我觉着对于得到结果没用，也许能用于back tracking。

王可雪 发表于 2015-1-4 09:38
那是题主的code，我觉着对于得到结果没用，也许能用于back tracking。

你的code里面

1. else if (s[i-1-dp[i]] == '('){
   
2.                     dp[i+1] = 2 + dp[i];
   
3.                     int pre = i - dp[i] - 1;
   
4.                     if (pre > 0)
   
5.                         dp[i+1] += dp[pre];
   
6.                 }

复制代码

这部分用不用考虑 i - dp[i] - 1 小于0的情况？这样else if里面就执行不了了

xytan123 发表于 2015-1-4 10:13
你的code里面这部分用不用考虑 i - dp - 1 小于0的情况？这样else if里面就执行不了了

我已经设计好了，应该不会出现小于0的。

王可雪 发表于 2015-1-3 14:10
你如果这样改了就只用分配s.size()个空间就行了。而且还有两行可以注释掉也能过。65536那个改法，我没太 ...

对的，如果把

1. if(dp[i-dp[i]]>0){

复制代码

改成

1. if(i-dp[i]>0){

复制代码

的话只用给dp[]分配s.size()空间就可以。对了，你指的是哪两行代码可以删掉？我试着注释了下可惜没有找到。

还有那个65535，其实真相是当时运气太好试了一下居然就过了，就跟为啥当时能来UWM一样，所以也不知道为啥65535可以过。现在我还是不理解leetcode oj的原理，不过凭直觉，我觉得你的想法是对的。

Myth_Legend 发表于 2015-1-4 12:08
对的，如果把改成的话只用给dp[]分配s.size()空间就可以。对了，你指的是哪两行代码可以删掉？我试着注释 ...

就是@xytan123说的那两行，你dp赋值有两次共四行，每次的下面那一行对之前值的修改其实没必要，因为跟计算的新值没关系了。

有时候我在eclipse上运行的结果也是跟oj上的结果不一样，然后我就想方设法给AC, 唉！

monkerek 发表于 2014-12-29 10:04
楼主，用C++的话这里有个问题哈。
编译器会在编译期就给数组开好空间，这也就是说 int dp[s.size()+1];  ...

兄弟。你这头像哪里找的灵感？？？我dota2用了一年这个头像，哈哈哈