题目描述:实现一个函数,把字符串中的每个空格替换成 “%20”


例如: 输入“We are happy.”  输出“We%20are%20happy.”



分析:每次遇到空格后,把空格后所有的字符都向后移动两个位置,于是会多出三个位置,此时将该三个位置替换成字符串“%20”,如下图:


wKioL1dTj82jRbFQAADSdERRUEs873.png


很显然,这种方法的时间复杂度为 O(n^2),因此不适合采用!


方法二:

wKiom1dTj3ax5UTxAACYZI3olEk429.pngwKiom1dTj-Tz0mHiAADPu9SeMgc772.png

wKiom1dTkCXiTTKIAABa6UFUCVM030.png

wKioL1dTkY7xESQmAACvIgmNAOs388.pngwKioL1dTkb7gwfOBAACsmMm2VVQ844.png


根据这种思路,代码应该很好写了:


/*length 为字符数组string的总容量*/void ReplaceBlank(char string[], int length){    if(string == NULL && length <= 0)        return;    /*originalLength 为字符串string的实际长度*/    int originalLength = 0;    int numberOfBlank = 0;    int i = 0;    while(string[i] != '\0')    {        ++ originalLength;        if(string[i] == ' ')            ++ numberOfBlank;        ++ i;    }    /*newLength 为把空格替换成'%20'之后的长度*/    int newLength = originalLength + numberOfBlank * 2;    if(newLength > length)        return;    int indexOfOriginal = originalLength;    int indexOfNew = newLength;    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)    {        if(string[indexOfOriginal] == ' ')        {            string[indexOfNew --] = '0';            string[indexOfNew --] = '2';            string[indexOfNew --] = '%';        }        else        {            string[indexOfNew --] = string[indexOfOriginal];        }        -- indexOfOriginal;    }}