一亩三分地论坛

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

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

[Leetcode] 这算不算leetcode的OJ的一个bug?

[复制链接] |试试Instant~ |关注本帖
Myth_Legend 发表于 2014-12-29 04:33:15 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 Myth_Legend 于 2014-12-28 19:53 编辑

我做到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.                 return m;
  21.         }
  22. };
复制代码
在下从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]>0){
需要改成
if(i-dp>0){
就能过,这题还是推荐用stack来解。
感谢大家给的启发,终身受用
王可雪 发表于 2015-1-3 14:58:06 | 显示全部楼层
本帖最后由 王可雪 于 2015-1-3 18:02 编辑

先占个坑,明天起来看看。
这个过了。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 the longest valid parentheses with s when s == )
        // two situations
        // (....) ()
        //  ( (...) )
        for (i = 1; i < s.size(); i++) {
            if (s == ')') {
                if (s[i-1] == '(') {
                    dp[i+1] = 2 + dp[i-1];
                }
                else if (s[i-1-dp] == '('){
                    dp[i+1] = 2 + dp;
                    int pre = i - dp - 1;
                    if (pre > 0)
                        dp[i+1] += dp[pre];
                }
                maxCount = max(dp[i+1], maxCount);
            }
        }
        return maxCount;
    }
};

别听他们一本正经的胡说八道。
这个错误太简单了。下次别忘了+1。
话说UWM的ECE不是那么好进吧,我当时好像申请的cs,悲剧了。你的也过了,20ms。
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=='(')l++;
                        else if(s==')' &&l>0){
                                l--;                                
                                dp[i+1]=dp+2;
                                dp[i-dp[i+1]+2]=dp;
                                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;
        }
};

最后再吐个槽,贴代码,地里从来没人给加分。






评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

monkerek 发表于 2014-12-29 10:04:20 | 显示全部楼层
本帖最后由 monkerek 于 2014-12-29 10:05 编辑
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是自己代码有问题

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

monkerek 发表于 2014-12-29 07:43:24 | 显示全部楼层
int dp[s.size()+1];

think for a while.....

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| Myth_Legend 发表于 2014-12-29 08:13:24 | 显示全部楼层
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之类的奇怪回传

刷题新人求大神详述思路指点迷津啊
回复 支持 反对

使用道具 举报

l955382 发表于 2014-12-29 09:18:42 | 显示全部楼层
這題我沒用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
回复 支持 反对

使用道具 举报

l955382 发表于 2014-12-29 09:21:16 | 显示全部楼层
  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了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| Myth_Legend 发表于 2014-12-29 09:34:30 | 显示全部楼层
l955382 发表于 2014-12-28 19:18
這題我沒用Dynamic programmning..... Dynamic programming就是用memory save之前compute過的value.... 既 ...

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

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

使用道具 举报

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

取不到s.size()的值!

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

回复 支持 反对

使用道具 举报

xytan123 发表于 2015-1-3 14:32:43 | 显示全部楼层
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. 我觉得应该不是内存分配的问题

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| Myth_Legend 发表于 2015-1-4 02:44:45 | 显示全部楼层
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){
回复 支持 反对

使用道具 举报

王可雪 发表于 2015-1-4 04:10:44 | 显示全部楼层
本帖最后由 王可雪 于 2015-1-4 04:20 编辑
Myth_Legend 发表于 2015-1-4 02:44
被你发现了,我也才刚刚意识到问题没这么简单

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

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

使用道具 举报

xytan123 发表于 2015-1-4 09:17:04 | 显示全部楼层
王可雪 发表于 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]?)
回复 支持 反对

使用道具 举报

王可雪 发表于 2015-1-4 09:38:09 | 显示全部楼层

那是题主的code,我觉着对于得到结果没用,也许能用于back tracking。
回复 支持 反对

使用道具 举报

xytan123 发表于 2015-1-4 10:13:39 | 显示全部楼层
王可雪 发表于 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 - 1 小于0的情况?这样else if里面就执行不了了
回复 支持 反对

使用道具 举报

王可雪 发表于 2015-1-4 10:22:43 | 显示全部楼层
xytan123 发表于 2015-1-4 10:13
你的code里面这部分用不用考虑 i - dp - 1 小于0的情况?这样else if里面就执行不了了

我已经设计好了,应该不会出现小于0的。
回复 支持 反对

使用道具 举报

 楼主| Myth_Legend 发表于 2015-1-4 12:08:51 | 显示全部楼层
王可雪 发表于 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的原理,不过凭直觉,我觉得你的想法是对的。
回复 支持 反对

使用道具 举报

王可雪 发表于 2015-1-4 12:12:17 | 显示全部楼层
Myth_Legend 发表于 2015-1-4 12:08
对的,如果把改成的话只用给dp[]分配s.size()空间就可以。对了,你指的是哪两行代码可以删掉?我试着注释 ...

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

applepie11 发表于 2015-1-6 07:10:33 | 显示全部楼层
有时候我在eclipse上运行的结果也是跟oj上的结果不一样,然后我就想方设法给AC, 唉!
回复 支持 反对

使用道具 举报

xingrunzhi 发表于 2015-1-31 09:55:05 | 显示全部楼层
monkerek 发表于 2014-12-29 10:04
楼主,用C++的话这里有个问题哈。
编译器会在编译期就给数组开好空间,这也就是说 int dp[s.size()+1];  ...

兄弟。你这头像哪里找的灵感???我dota2用了一年这个头像,哈哈哈
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 06:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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