剑指Offer面试题（四）空格替换

题目：设计一种方法，将一个字符串中的所有空格替换成 %20 。你可以假设该字符串有足够的空间来加入新的字符，且你得到的是“真实的”字符长度。

你的程序还需要返回被替换后的字符串的长度。（挑战：在原字符串(字符数组)中完成替换，不适用额外空间）

样例：对于字符串"Mr John Smith", 长度为 13，替换空格之后，参数中的字符串需要变为"Mr%20John%20Smith"，并且把新长度 17 作为结果返回。

分析：

常规解法是，从头到尾遍历，遇到空格时，把空格后面的字符串依次后移。但该种方法会导致某些字符重复移动，时间复杂度较高约为O（n²）。
    推荐解法：先计算出原字符串中有多少空格，然后从尾到头遍历，因为一开始就知道被移动字符的最终位置，因此可以避免字符的重复移动。时间复杂度O(n)：

1.首先计算字符串中空格的个数。每个空格用三个字符替换，那么每多一个空格那么替换后的字符串将多出来两个字符。因此计算出替换后字符串的长度。

2.在字符串中设置两个索引，p1索引指向字符串的结尾即'\0'处，另外一个指向计算出的替换后字符串长度的位置。

3.当未遇到空格时候，将p1所指的字符赋值为p2所指的字符。同时索引p1,p2均向前移动一个位置

4，当索引p1遇到空格时候将p2,p2-1,p2-2,这三个位置分别替换为'%' '2' '0'，然后索引p1向前移动一个位置,p2向前移动三个位置。

5.替换的结束条件是，当p1和p2索引位置相同时，这时候替换空格结束。

int replaceBlank(char string[], int length) { 
    //先统计空格个数，然后替换
    //注意char类型用'''  
    //注意判空 
    if(string == NULL && length <= 0)
        return 0; 
    int spaceNum=0;
    int i=0;
    while(string[i] != '\0'){ 
        if(string[i]==' ') 
            spaceNum++; 
        i++;
    }
    //新字符串的长度
    int newlength=length+2*spaceNum;
    int j=newlength-1;//从最后一位开始判断，若出现空格，将替换为20%
    while(j>=0){ 
        if(string[length-1]==' '){ 
            string[j--]='0';
            string[j--]='2'; 
            string[j--]='%';
        }else{
            string[j--]=string[length-1];
        }
        length--;
    } 
    return newlength;
}