一亩三分地论坛

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

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

[Leetcode] 【求助】28 Implement strStr(): RUNTIME ERROR

[复制链接] |试试Instant~ |关注本帖
see_world 发表于 2015-4-11 16:59:10 | 显示全部楼层 |阅读模式

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

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

x
又遇到了毫无头绪的错误,自己电脑上跑一点问题都没有,放到网上就报错,不知道应该怎么调,求助,先谢谢各位了 TAT

题目:Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

思路:KMP算法,先计算next数组,再算答案。

报错: Runtime Error
Last executed input:        "mississippi", "issipi"

代码如下:
class Solution {
public:
    int strStr(char *haystack, char *needle) {
        int hL = strlen(haystack), nL = strlen(needle);
        if(nL>hL || hL==0)
            return -1;
        if(nL==0)
            return 0;
        int *next = new int[nL];
        buildNext(needle, next, nL);
/*
        for(int i=0; i<nL; i++){
            cout<<next[i]<<" ";
        }
        cout<<endl;
*/
        int p1=0, p2=0;
        while(p1<hL && p2<nL){
            //cout<<p1<<" "<<p2<<endl;
            if(p2==-1 || haystack[p1]==needle[p2]){
                p1++;
                p2++;
            }
            else{
                p2=next[p2];
            }
        }
        delete next;
        if(p2==nL)
            return p1-p2;
        return -1;
    }
    void buildNext(char * s, int * next, int n){
        int p1 = -1, p2 = 0;
        next[0]=-1;
        while(p2<n){
            if(p1==-1){
                p1++;
                p2++;
                next[p2]=0;
            }
            else if(s[p1]==s[p2]){
                p1++;
                p2++;
                next[p2]=next[p2-1]+1;
            }
            else{
                p1=next[p1];
            }
        }
    }
};
stellari 发表于 2015-4-14 20:01:59 | 显示全部楼层
我遇到这种情况时会这么调:

先看出错时的输入:"mississippi", "issipi"

那么好,现在往程序的第一行中插入这么一句:
if (strcmp(haystay, "mississippi")==0 && strcmp(needle, "issipi")==0) return what_ever_number;
那么此时一定不会(至少在这个测试用例下)报错了。

如果你将此句放到函数的最后一行,那么肯定还是报错。

因此,你可以试着将此句放入函数中不同的位置,那么肯定会找到一个位置:当你将这句放在该位置之前,没有报错;而放在该位置之后,有报错。这说明错误一定出在这个位置上。

如果错误是出在循环中的话,那么这个方法未必管用,但是这样最起码可以极大地缩小错误的范围,方便调试。
回复 支持 反对

使用道具 举报

 楼主| see_world 发表于 2015-4-15 19:26:19 | 显示全部楼层
stellari 发表于 2015-4-14 20:01
我遇到这种情况时会这么调:

先看出错时的输入:"mississippi", "issipi"

嗯嗯,谢谢。是个方法。

不过我很奇怪为什么本地跑没问题而放到网上就不行了,你知道大概原因不?。。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-4-16 14:30:11 | 显示全部楼层
see_world 发表于 2015-4-15 19:26
嗯嗯,谢谢。是个方法。

不过我很奇怪为什么本地跑没问题而放到网上就不行了,你知道大概原因不?。。

原因太多了,但是说到底都是因为你那里的环境和OJ上在某处出现了不同,包括但不仅限于:

1。代码不同:比如贴错了代码
2。测试用例不同:比如你机器上的测试用例和OJ上的不同。
3。测试环境不同:比如OJ中,要重复创建Solution类对象。如果某解法依赖于Solution类中的一个static变量,而又没有每次对这个static变量进行合理的初始化的话。那么这个static变量在上一次测试用例完成之后的残留值是可能会影响下一个测试用例的。

总之,我认为你还是真正地调试一下比较好,因为这种问题很多时候都是出在你认为绝对不可能出错的地方,光凭理论分析是很难找出问题所在的。
回复 支持 反对

使用道具 举报

 楼主| see_world 发表于 2015-4-17 11:20:25 | 显示全部楼层
stellari 发表于 2015-4-16 14:30
原因太多了,但是说到底都是因为你那里的环境和OJ上在某处出现了不同,包括但不仅限于:

1。代码不同 ...

可能使本地容错性比较好,所以本地跑没有错。实际上我的代码有个地方溢出了:给next[n]赋了值,到网上测编译不过。

谢谢你的帮助!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 23:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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