题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

解题思路

首先看到这个题目, 第一感觉就是要自己另外开辟一个数组, 然后在遍历str的过程中, 将str中的非空格字符copy到新数组中, 而当碰到空格字符时, 就对应地在新数组中添加%, 2, 0三个元素. 在结束遍历之后, 将新数组作为函数返回值返回.

但是注意到题目给出的C++函数声明如下:

class Solution {
public:
    void replaceSpace(char *str,int length) {

    }
};

因此上面的解决办法存在两个问题:

这个repaceSpace函数是没有返回值的. 替换空格的操作结果是要直接体现中str中;
另外, 其实考虑到如果要新开辟数组, 然后将修改后的数组作为函数返回值返回的话, 貌似也是行不通, 因为在函数内部声明的char数组或char *指针, 在作为函数返回之后就变成一个野指针了, 因为这个在函数内部申明的指针(在栈中分配内存)在函数结束时会被释放.

遵照题目的意思, 我在最初的解题思路上进行了改进. 在函数内部分配一个临时的数组tmp, 将str的内容复制给它. 然后, 在计算一遍修改后的数组应有的长度之后(新长度 = 旧长度 + 2*字符串中的空格数), 使用realloc重新分配str的内存(给其分配新长度).

下面是按照上述思路提交的一份代码, 在本地测试得到的结果是正确的, 但提交到牛客网上之后得到的结果是运行错误, 说是有内存访问溢出. 想来想去, 实在想不到出问题的根源所在.

class Solution {
public:
    void replaceSpace(char *str,int length) {
        // printf("%s %d", str, length);
        if(str == NULL || length == 0) return;
        // 先确定字符串中的空格数量
        int nSpaceCount = 0;

        for(int i=0; i<length; i++)
        {
            if(str[i] == ' '){
                nSpaceCount++;
            }
        }

        if(nSpaceCount == 0) return;
        char tmp[length + 1];
        strcpy(tmp, str);
        // printf("%s\n", tmp); //@!
        str = (char*)realloc(str, length+1+2*nSpaceCount);

        int i, j;
        for(i=0, j=0; i<length; i++, j++)
        {
            if(tmp[i] != ' ')
            {
                str[j] = tmp[i];
            }
            else
            {
                str[j] = '%';
                str[j+1] = '2';
                str[j+2] = '0';
                j += 2;
            }
        }
        str[j] = '\0';
        // printf("%s\n", str);
    }
};

通过搜索之前人的回答, 发现有可能是我对函数的第二个参数的认识与实际不符, 我以为length是str所指字符串的长度, 但实际上length是牛客网的OJ所限定的一个字符串的最大长度值. 下图是对这一猜测的证明.
leschus

因此, 上一份代码虽然解题思路没有错, 但是由于调用realloc分配的内存超过了系统的限定, 导致会出现运行时错误.

其它的题解有用到一种从右向左遍历的策略, 不需要额外分配内存. 也就不会有我上面碰到的问题. 但我还是想顺着我最初的思路走完, 善始善终.

改进方法是, 不使用length作为str长度(因为这本身就是错的), 而是自己计算一下str所指字符串的长度. 后面的操作则沿袭上一份代码的做法.

提交代码如下, 通过.

class Solution {
public:
    void replaceSpace(char *str,int length) {
                if(str==NULL || length<=0) return;

        // 获取字符串长度和空格数量
        int len = 0, spaceNum = 0;
        for(int i=0; str[i]!='\0'; i++, len++){
            if(str[i] == ' ') spaceNum++;
        }
        if(spaceNum==0) return;

        char tmp[len + 1];
        strcpy(tmp, str);

        str = (char*)realloc(str, len + 1 + 2*spaceNum);

        int i, j;
        for(i=0, j=0; i<len; i++, j++)
        {
            if(tmp[i] == ' '){
                str[j] = '%';
                str[j+1] = '2';
                str[j+2] = '0';
                j+=2;
            }
            else{
                str[j] = tmp[i];
            }
        }
        str[j] = '\0';
    }
};

附: 不需要额外分配内存的解法(双索引从右向左遍历str)

其实要是事先理解了本题中length的含义, 也不会出那么多岔子. 考虑到从右向左的遍历策略确实要比从左到右效率高, 还是动手实现了一遍, 下面是代码:

class Solution {
public:
    void replaceSpace(char *str,int length) {
        if(str == NULL || length <= 0) return;

        // 获得字符串长度和空格数目
        int spaceNum=0, len=0;
        for(int i=0; str[i] != '\0'; i++){
            if(str[i] == ' ') spaceNum++;
            len++;
        }

        int pos, pos_new; //两个索引
        pos = len;
        pos_new = len + spaceNum * 2;
        while(pos>=0){
            if(str[pos] == ' '){
                str[pos_new--] = '0';
                str[pos_new--] = '2';
                str[pos_new--] = '%';
                pos--;
            }
            else{
                str[pos_new--] = str[pos--];
            }
        }
    }
};

[剑指OFFER] JZ2 替换空格

题目描述

解题思路

附: 不需要额外分配内存的解法(双索引从右向左遍历str)