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

我做到032 Longest Valid Parentheses这题的时候怎么输出的结果和OJ的不一样，我在电脑上用g++ 032.cpp -std=c++11 编译完了运行，结果是2
但是提交leetcode 的OJ上面的时候变成
Submission Result: Wrong Answer

Input:	"()"
Output:	3
Expected:	2

这个output=3太让我百思不得其解，在dynamic programming 过程中全程都对dp[]先初始化为0，再以2递增，而且在input="()"的这个例子中没有访问未初始化的数据，完全不可能出现3这个值

oj的地址：
https://oj.leetcode.com/problems/longest-valid-parentheses/

这题我的思路是用一维数组dp[]存结果，变量 l 用来记录'('的个数，变量 m 用来存dp数组中的最大值，最后和预期一样，过一遍string循环结束，时间复杂度O(n)

例1输入

1. "()(())()"

复制代码

时一轮循环中dp[]赋值的结果如下：

1. 0 0 0 0 0 0 0 0
   
2. 0 2 0 0 0 0 0 0
   
3. 2 2 0 0 0 0 0 0
   
4. 2 2 0 0 0 0 0 0
   
5. 2 2 0 0 0 0 0 0
   
6. 2 2 0 0 2 0 0 0
   
7. 2 2 0 2 2 0 0 0
   
8. 2 2 0 2 2 4 0 0
   
9. 6 2 4 2 2 6 0 0
   
10. 6 2 4 2 2 6 0 0
    
11. 6 2 4 2 2 6 0 2
    
12. 8 2 4 2 2 6 2 8

复制代码

最终dp[]= 8 2 4 2 2 6 2 8，然后函数longestValidParentheses返回最大值m=8


例2输入

1. "(()()()())"

复制代码

时一轮循环中dp[]赋值的结果如下：

1. 0 0 0 0 0 0 0 0 0 0
   
2. 0 0 0 0 0 0 0 0 0 0
   
3. 0 0 2 0 0 0 0 0 0 0
   
4. 0 2 2 0 0 0 0 0 0 0
   
5. 0 2 2 0 0 0 0 0 0 0
   
6. 0 2 2 0 2 0 0 0 0 0
   
7. 0 4 2 2 4 0 0 0 0 0
   
8. 0 4 2 2 4 0 0 0 0 0
   
9. 0 4 2 2 4 0 2 0 0 0
   
10. 0 6 2 2 4 2 6 0 0 0
    
11. 0 6 2 2 4 2 6 0 0 0
    
12. 0 6 2 2 4 2 6 0 2 0
    
13. 0 8 2 2 4 2 6 2 8 0
    
14. 0 8 2 2 4 2 6 2 8 10
    
15. 10 8 2 2 4 2 6 2 8 10

复制代码

最终dp[]=10 8 2 2 4 2 6 2 8 10，然后函数longestValidParentheses返回最大值m=10


例3输入

1. ")(()())))()())"

复制代码

时一轮循环中dp[]赋值的结果如下：

1. 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   
2. 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   
3. 0 0 2 0 0 0 0 0 0 0 0 0 0 0
   
4. 0 2 2 0 0 0 0 0 0 0 0 0 0 0
   
5. 0 2 2 0 0 0 0 0 0 0 0 0 0 0
   
6. 0 2 2 0 2 0 0 0 0 0 0 0 0 0
   
7. 0 4 2 2 4 0 0 0 0 0 0 0 0 0
   
8. 0 4 2 2 4 6 0 0 0 0 0 0 0 0
   
9. 6 4 2 2 4 6 0 0 0 0 0 0 0 0
   
10. 6 4 2 2 4 6 0 0 0 0 0 0 0 0
    
11. 6 4 2 2 4 6 0 0 0 0 0 0 0 0
    
12. 6 4 2 2 4 6 0 0 0 0 0 0 0 0
    
13. 6 4 2 2 4 6 0 0 0 0 0 0 0 0
    
14. 6 4 2 2 4 6 0 0 0 0 2 0 0 0
    
15. 6 4 2 2 4 6 0 0 0 2 2 0 0 0
    
16. 6 4 2 2 4 6 0 0 0 2 2 0 0 0
    
17. 6 4 2 2 4 6 0 0 0 2 2 0 2 0
    
18. 6 4 2 2 4 6 0 0 0 4 2 2 4 0
    
19. 6 4 2 2 4 6 0 0 0 4 2 2 4 0

复制代码

最终dp[]=6 4 2 2 4 6 0 0 0 4 2 2 4 0 ，然后函数longestValidParentheses返回最大值m=6

贴上我的solution：

1. class Solution {
   
2. public:
   
3.         int longestValidParentheses(string s) {
   
4.                 int i=0,m=0,l=0;
   
5.                 int dp[s.size()+1];
   
6.                 for(i=0;i<s.size();i++){
   
7.                         dp[i]=0;
   
8.                         if(s[i]=='(')l++;
   
9.                         else if(s[i]==')' &&l>0){
   
10.                                 l--;                                
    
11.                                 dp[i]=dp[i-1]+2;
    
12.                                 dp[i-dp[i]+1]=dp[i];
    
13.                                 if(dp[i-dp[i]]>0){
    
14.                                         dp[i]+=dp[i-dp[i]];
    
15.                                         dp[i-dp[i]+1]=dp[i];
    
16.                                 }
    
17.                                 if(m<dp[i])m=dp[i];
    
18.                         }               
    
19.                 }
    
20. 
    
21.                 return m;
    
22.         }
    
23. };

复制代码

在下从EE转CS很痛苦，在OJ上用C++刷题更痛苦，好不容易这学期在课上学到dynamic programming，结果OJ还不让过，大家用c++的时候有遇到OJ和本地结果不一样么？这是我第一次遇到这个情况，求前来围观的大神一起讨论分析









补充内容 (2015-1-3 12:13):
之前以为是内存分配错误，把int dp[s.size()+1];改成int dp[65535];过了
但其实代码其他地方有错误
if(dp[i-dp[i]]>0){
需要改成
if(i-dp[i]>0){
就能过，这题还是推荐用stack来解。
感谢大家给的启发，终身受用

先占个坑，明天起来看看。
这个过了。40ms。这题能用stack吗。
class Solution {
public:
    int longestValidParentheses(string s) {
        int dp[s.size()+1];
        int i;
        int maxCount = 0;
        for (i = 0; i <= s.size(); i++)    dp = 0;
        // occrurrence
        // dp[i] the longest valid parentheses with s[i] when s[i] == )
        // two situations
        // (....) ()
        //  ( (...) )
        for (i = 1; i < s.size(); i++) {
            if (s[i] == ')') {
                if (s[i-1] == '(') {
                    dp[i+1] = 2 + dp[i-1];
                }
                else if (s[i-1-dp[i]] == '('){
                    dp[i+1] = 2 + dp[i];
                    int pre = i - dp[i] - 1;
                    if (pre > 0)
                        dp[i+1] += dp[pre];
                }
                maxCount = max(dp[i+1], maxCount);
            }
        }
        return maxCount;
    }
};[/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i]别听他们一本正经的胡说八道。[/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i]这个错误太简单了。下次别忘了+1。[/i][/i][/i][/i][/i][/i][/i]
话说UWM的ECE不是那么好进吧，我当时好像申请的cs，悲剧了。你的也过了，20ms。
[i][i][i][i][i][i][i]class Solution {
public:
        int longestValidParentheses(string s) {
                int i=0,m=0,l=0;
                int dp[s.size()+1];
                dp[0] = 0;
                for(i=0;i<s.size();i++){
                        dp[i+1]=0;
                        if(s[i]=='(')l++;
                        else if(s[i]==')' &&l>0){
                                l--;                                
                                dp[i+1]=dp[i]+2;
                                dp[i-dp[i+1]+2]=dp[i][i];
                                if(dp[i-dp[i+1]+1]>0){
                                        dp[i+1]+=dp[i+1-dp[i+1]];
                                        dp[i+1-dp[i+1]+1]=dp[i+1];
                                }
                                if(m<dp[i+1])m=dp[i+1];
                        }               
                }

                return m;
        }
};[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][i][i][i][i][i][i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i]最后再吐个槽，贴代码，地里从来没人给加分。

[/i][/i][/i][/i][/i][/i][/i]
[/i][/i][/i][/i]

Myth_Legend 发表于 2014-12-29 08:13
That's the problem? I still don't get it.

这个地方想了好久了，但是还想不通s="()"的case为什么在O ...

楼主，用C++的话这里有个问题哈。
编译器会在编译期就给数组开好空间，这也就是说 int dp[s.size()+1]; 这句在编译期的时候是没办法按你的想法正确开辟空间的，因为在编译期的时候还取不到s.size()的值。
至于按你的写法dp这个数组的实际内存分配情况到底是怎样的要留给楼主自己去google啦~
在c++里面用动态数组一般有两个方法：
1. Type* arr = new Type[size_type] (用完之后及时delete)
2. vector<Type> arr(size_type, initial_value)
ps: 如果过不了oj百分之99.9是自己代码有问题

int dp[s.size()+1];

think for a while.....

monkerek 发表于 2014-12-28 17:43
int dp[s.size()+1];

think for a while.....

That's the problem? I still don't get it.

这个地方想了好久了，但是还想不通s="()"的case为什么在OJ上是3

如果input s="()"

那么循环 i 从0到1
在i=0时走的是 (s=='(')l++
这个时候l=1

在i=1时走的是 (s==')')m=2
这个时候m=2按理应该作为输出被return

也考虑过input 中含有不可见的ASCII码，但是不管加多少个字符进string s，本地输出都是正常的，没有像3之类的奇怪回传

刷题新人求大神详述思路指点迷津啊

這題我沒用Dynamic programmning..... Dynamic programming就是用memory save之前compute過的value.... 既然要用extra space... 我直接用個stack來存上一個"("的位子..

看到"("就push 看到 ")"就 pop 然後算他的長度...

For example:
1. "(()"
妳會push twice. push的value是 "("的index. 當妳看到")"時,妳的stack裡會是 [1, 0].
然後妳在pop出上一個value... 這時stack剩下 [0]. 那你的length 會是 2 - 0. 2 = index of ")".
2. ((())()()()()
stack的value會是:
[0,1, 2] ---> [0, 1] ---> length = 3 - 1 = 2
[0, 1] ---> [0] ---> length = 4 - 0 = 4
[0, 1, 5] ---> [0] ---> length = 6 - 0 = 6
etc. etc. etc.....

代碼如下:

1. public int longestValidParentheses(String s) {
   
2.       
   
3.     Stack<Integer> stack = new Stack<Integer>();

复制代码

time complexity = n
space complexity = n

1.   public int longestValidParentheses(String s) {
   
2.       
   
3.        Stack<Integer> stack = new Stack<Integer>();
   
4.       
   
5.        int last = -1;
   
6.        int i = 0;
   
7.        int max = 0;
   
8.       
   
9.        while(i < s.length()) {
   
10.            if(s.charAt(i) == '(') {
    
11.                stack.push(i);
    
12.            } else {
    
13.                if(stack.isEmpty()) {
    
14.                    // didn't find a matching
    
15.                    last = i;
    
16.                } else {
    
17.                    stack.pop();
    
18.                   
    
19.                    if(stack.isEmpty()) {
    
20.                        max = Math.max(max, i - last);
    
21.                    } else {
    
22.                        max = Math.max(max, i - stack.peek());
    
23.                    }
    
24.                }
    
25.            }
    
26.            ++i;
    
27.        }
    
28.       
    
29.        return max;
    
30.       
    
31.     }

复制代码

不知道為什麼上個post的code 被truncated了

l955382 发表于 2014-12-28 19:18
這題我沒用Dynamic programmning..... Dynamic programming就是用memory save之前compute過的value.... 既 ...

很感谢提供的思路，你写的代码很漂亮，空间复杂度和时间复杂度都控制的很好。

但我还是很纠结我那个代码，为什么明明本地输出符合要求，OJ却被判错，这种感觉就像有人在你毛衣里面放一只蚂蚁，让你痒痒却挠不到。

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

取不到s.size()的值！

原来是这样，又学到了，终于明白这里症结所在。所以本地g++的编译器和OJ的编译器的编译规则还是存在一些不同？而且我代码里那种不符合规范的数组声明方法OJ编译能通过，看来下学期得好好学习compiler了，前面的路真的好长

Myth_Legend 发表于 2014-12-29 10:26
取不到s.size()的值！

原来是这样，又学到了，终于明白这里症结所在。所以本地g++的编译器和OJ的编译 ...

我把你的代码第5行修改成了

1. int* dp = new int[s.size()+1];

复制代码

或者

1. vector<int> dp(s.size()+1, 0);

复制代码

还是不行，提示有一个case runtime error. 我觉得应该不是内存分配的问题