ReplaceSpace to Strcpy fault

8月 2 2014

一道剑指Offer的简单题，越简单越容易忽视错误。很多带有非ASCII码的字符在互联网上传播的时候都会转化为ASCII嘛字符，
最常见的就是wikipedia有些中文的名词，那么把URL copy发给别人的时候都会转化为ASCII码，例如space->%20这类的。

这种字符串替换一类的特别注意空间会往后扩展不要覆盖原来的字符。思路主要有两个：

O(n), two-pass 就地操作，先计算出空格数，增加的长度是空格数2, 然后由于字符都向后移，因此避免覆盖还未处理的字符，从后向前遍历，每个
字符都向后移前面的空格数2个位置

2.O(n) one-pass, O(n) space 申请一个堆，one pass, 两个指针，算法比较清晰，就是要另外占空间，而且最后还要记得free掉这个空间

3.O(n^2) 从前向后，每次遇到空格后面就整体后移当前遇到空格数*2个位置

这里面有一个地方自己要特别当心，就是当copy %20这三个字符时，可能觉得一个字符copy麻烦，直接strcpy却殊不知strcpy会
多做一件事情就是尾部加\0, 所以要特别当心，用newheap的方法，由于后面会修改\0的位置，所以strcpy没问题，但是最好还是把这件事情前面
就做好，不要漏电什么，也就是用strncpy来copy，指定几个字符，这个是纯粹的copy字符，不拖泥带水的。

char* ReplaceSpace_newheap(char* cstr)
{
    int cstrlen=strlen(cstr);
    char* resultstr=new char[cstrlen*3+1];
    int i=0,j=0;
    while(i<cstrlen)
    {
        if(cstr[i]!=' ')
        {
            resultstr[j]=cstr[i];
            i++;j++;
        }
        else
        {
            strncpy(resultstr+j,"%20",3);
            j+=3;
            i++;
        }
    }
    resultstr[j]='\0';
    //strcpy(cstr,resultstr);
    //delete []resultstr;
    return resultstr;
}

char* ReplaceSpace_inplace_countspace(char* cstr)
{
    int i,totalcount=0;
    for(i=0;cstr[i];i++)
    {
        if(cstr[i]==' ')
            totalcount++;
    }
    int currentcount=0;
    int cstrlen=i;


    cstr[cstrlen+(totalcount-currentcount)*2]='\0';
    for(int j=cstrlen-1;j>=0;j--)
    {
        if(cstr[j]!=' ')
            cstr[j+(totalcount-currentcount)*2]=cstr[j];
        else
        {
            currentcount++;
            strncpy(cstr+j+((totalcount-currentcount)*2),"%20",3);
        }
    }
    return cstr;
}

Posted by richard爱闹 - 8月 2 2014
如需转载，请注明：本文来自 Richard

留言