登录
  • #刷题
  • #leetcode

这算‌‌‌‌‍‍‌‍‌‌‍‍‌‍‌‌‍‍‍‌‍‍‍‌‍‌‌‌‍‍‌‌不算leetcode的OJ的一个bug?

Myth_Legend
7641
21
我做到032 Longest Valid Parentheses这题的时候怎么输出的结果和OJ的不一样,我在电脑上用g++ 032.cpp -std=c++11 编译完了运行,结果是2

但是提交leetcode 的OJ上面的时候变成

[float=left]Submission Result: Wrong Answer[/float]

[float=left][backcolor=rgb(242, 222, 222)]







Input:"()"
Output:3
Expected:2
[/backcolor]
[/float]



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

oj.leetcode.com

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

例1输入
"()(())()"
时一轮循环中dp[]赋值的结果如下:[code]0 0 0 0 0 0 0 0

0 2 0 0 0 0 0 0

2 2 0 0 0 0 0 0

2 2 0 0 0 0 0 0

2 2 0 0 0 0 0 0

2 2 0 0 2 0 0 0

2 2 0 2 2 0 0 0

2 2 0 2 2 4 0 0

6 2 4 2 2 6 0 0

6 2 4 2 2 6 0 0

6 2 4 2 2 6 0 2

8 2 4 2 2 6 2 8最终dp[]= 8 2 4 2 2 6 2 8,然后函数[backcolor=rgb(247, 247, 247)]longestValidParentheses返回最大值m=8[/backcolor]

例2输入
"(()()()())"
时一轮循环中dp[]赋值的结果如下:[code]0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 2 0 0 0 0 0 0 0

0 2 2 0 0 0 0 0 0 0

0 2 2 0 0 0 0 0 0 0

0 2 2 0 2 0 0 0 0 0

0 4 2 2 4 0 0 0 0 0

0 4 2 2 4 0 0 0 0 0

0 4 2 2 4 0 2 0 0 0

0 6 2 2 4 2 6 0 0 0

0 6 2 2 4 2 6 0 0 0

0 6 2 2 4 2 6 0 2 0

0 8 2 2 4 2 6 2 8 0

0 8 2 2 4 2 6 2 8 10

10 8 2 2 4 2 6 2 8 10最终dp[]=10 8 2 2 4 2 6 2 8 10,然后函数[backcolor=rgb(247, 247, 247)]longestValidParentheses返回最大值m=10[/backcolor]

例3输入
")(()())))()())"
时一轮循环中dp[]赋值的结果如下:[backcolor=rgb(247, 247, 247)]
0 0 0 0 0 0 0 0 0 0 0 0 0 0 [br][/br][br][/br]0 0 0 0 0 0 0 0 0 0 0 0 0 0 [br][/br][br][/br]0 0 2 0 0 0 0 0 0 0 0 0 0 0 [br][/br][br][/br]0 2 2 0 0 0 0 0 0 0 0 0 0 0 [br][/br][br][/br]0 2 2 0 0 0 0 0 0 0 0 0 0 0 [br][/br][br][/br]0 2 2 0 2 0 0 0 0 0 0 0 0 0 [br][/br][br][/br]0 4 2 2 4 0 0 0 0 0 0 0 0 0 [br][/br][br][/br]0 4 2 2 4 6 0 0 0 0 0 0 0 0 [br][/br][br][/br]6 4 2 2 4 6 0 0 0 0 0 0 0 0 [br][/br][br][/br]6 4 2 2 4 6 0 0 0 0 0 0 0 0 [br][/br][br][/br]6 4 2 2 4 6 0 0 0 0 0 0 0 0 [br][/br][br][/br]6 4 2 2 4 6 0 0 0 0 0 0 0 0 [br][/br][br][/br]6 4 2 2 4 6 0 0 0 0 0 0 0 0 [br][/br][br][/br]6 4 2 2 4 6 0 0 0 0 2 0 0 0 [br][/br][br][/br]6 4 2 2 4 6 0 0 0 2 2 0 0 0 [br][/br][br][/br]6 4 2 2 4 6 0 0 0 2 2 0 0 0 [br][/br][br][/br]6 4 2 2 4 6 0 0 0 2 2 0 2 0 [br][/br][br][/br]6 4 2 2 4 6 0 0 0 4 2 2 4 0 [br][/br][br][/br]6 4 2 2 4 6 0 0 0 4 2 2 4 0 
[/backcolor]

最终dp[]=6 4 2 2 4 6 0 0 0 4 2 2 4 0 ,然后函数[backcolor=rgb(247, 247, 247)]longestValidParentheses返回最大值m=6[/backcolor]

贴上我的solution:
class Solution {[br][/br][br][/br]public:[br][/br][br][/br]        int longestValidParentheses(string s) {[br][/br][br][/br]                int i=0,m=0,l=0;[br][/br][br][/br]                int dp[s.size()+1];[br][/br][br][/br]                for(i=0;i<s.size();i++){[br][/br][br][/br]                        dp[i]=0;[br][/br][br][/br]                        if(s[i]=='(')l++;[br][/br][br][/br]                        else if(s[i]==')' &&l>0){[br][/br][br][/br]                                l--;                                [br][/br][br][/br]                                dp[i]=dp[i-1]+2;[br][/br][br][/br]                                dp[i-dp[i]+1]=dp[i];[br][/br][br][/br]                                if(dp[i-dp[i]]>0){[br][/br][br][/br]                                        dp[i]+=dp[i-dp[i]];[br][/br][br][/br]                                        dp[i-dp[i]+1]=dp[i];[br][/br][br][/br]                                }[br][/br][br][/br]                                if(m<dp[i])m=dp[i];[br][/br][br][/br]                        }                [br][/br][br][/br]                }[br][/br][br][/br]                return m;[br][/br][br][/br]        }[br][/br][br][/br]};在下从EE转CS很痛苦,在OJ上用C++刷题更痛苦,好不容易这学期在课上学到dynamic programming,结果OJ还不让过{:9_296:}{:9_296:},大家用c++的时候有遇到OJ和本地结果不一样么?这是我第一次遇到这个情况,求前来围观的大神一起讨论分析[br][/br][br][/br][b]补充内容 (2015-1-3 12:13):[/b][br][/br][br][/br]之前以为是内存分配错误,把int dp[s.size()+1];改成int dp[65535];过了[br][/br][br][/br]但其实代码其他地方有错误[br][/br][br][/br]if(dp[i-dp[i]]>0){[br][/br][br][/br]需要改成[br][/br][br][/br]if(i-dp[i]>0){[br][/br][br][/br]就能过,这题还是推荐用stack来解。[br][/br][br][/br]感谢大家给的启发,终身受用[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
21条回复
热度排序

发表回复