《剑指offer》--005--替换字符串中的空格

男娘i 2022-06-01 03:57 172阅读 0赞

[《剑指offer》–目录索引][offer]

**题目：**

> 请实现一个函数，将一个字符串中的空格替换成“%20”。  
> 例如，当字符串为We Are Happy.  
> 则经过替换之后的字符串We%20Are%20Happy。  
> （要求时间复杂度为O(n)）

**思路：**

> 这道题的难点在于要求使用O(n)的算法，不然很简单直接使用暴力替换；  
> ①首先遍历一遍字符串，计算出字符串中的空格数count，则**新的字符串的长度len=原字符串长度length+2\*count**；（这里说新字符串和原字符串是为了方便解释，实际上都是同一个字符串或者说都在同一个数组上，只不过字符串末尾的下标不一样，原字符串的末尾下标是length-1，新字符串的末尾下标是len-1）  
> ②再从这两个字符串的末尾，**即两个下标i=length-1;j=len-1;处开始从后往前遍历一遍，在遍历的过程中遇到空格就连续替换成‘0’‘2’‘%’**，具体如下动图：  
> ![这里写图片描述][SouthEast]

**代码：**

void ReplaceSpace(char* str,int length)
    {
        assert(str && length > 0);
        char* ret=str;
        int i=0,j=0,len=0,count=0;
    
        while(i<length)//字符串中空格个数
        {
            if(ret[i] == ' ')
            {
                count++;
            }
            i++;
        }
        len=length+2*count;//实际所需字符串长度
    
        i=length-1;
        j=len-1;
        while(i >= 0 && j >= 0)
        {
            if(ret[i] == ' ')
            {
                ret[j--]='0';
                ret[j--]='2';
                ret[j--]='%';
                i--;
            }
            else
            {
                ret[j--]=ret[i--];
            }
        }
    }

**测试代码：**

void test()//测试代码
    {
        char str[20]="We are happy";
        int length=strlen(str);
        printf("%s\n",str);
        ReplaceSpace(str,length);
        printf("%s\n",str);
    }
    
    int main()
    {
        test();
        return 0;
    }

**运行结果：**  
![这里写图片描述][SouthEast 1]

[offer]: http://blog.csdn.net/w_y_x_y/article/details/79209805
[SouthEast]: /images/20220601/5d52b63e084e4fec81c075b03d29b7f3.png
[SouthEast 1]: /images/20220601/3038378d70044bacbea2b9f0076bd975.png