《剑指offer》替换空格

问题：

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

思路：

1. 找到空格的个数
2. 创建一个新的字符串个数为空格＊2+原字符串长度
3. 进行复制，在空格处用％20取代

代码实现

// 第一种思路 从后往前填充字符串数组，效率较高
class Solution {
public:
    void replaceSpace(char *str,int length) {
        int count = 0;
        for (int i = 0; i < length; ++i) {
            if (str[i] == ' ') {
                ++count;
            }
        }
        count *= 2;
        int lastSeek = length+count;
        for (int i = length; i >= 0; --i) {
            if (i == lastSeek) break;
            if (str[i] == ' ') {
                str[lastSeek--] = '0';
                str[lastSeek--] = '2';
                str[lastSeek--] = '%';
                continue;
            }
            str[lastSeek--] = str[i];
        }
    }
};

// 第二种思路，从前往后填充字符串数组，效率最低
class Solution {
public:
    void replaceSpace(char *str,int length) {
        int j = 0;
        char dd[100];
        for (int i = 0; i < length; ++i,++j)
         {
            if (str[i] != ' ') {
                dd[j] = str[i];
            }
            else {
                dd[j] = '%';
                dd[++j] = '2';
                dd[++j] = '0';
            }
         }
         strcpy(str,dd);
    }
};

// 第三种思路，双指针思路
class Solution {
public:
    void replaceSpace(char *str,int length) {
        if(str==NULL||length<=0)
            return;
        int realLength=0;
        int blank=0;
        int i=0;
        while(str[i]!='\0')
        {
            ++realLength;
            if(str[i]==' ')
                ++blank;
            ++i;
        }
         
        int newLength=realLength+blank*2;
        if(newLength>length)
            return;
        int index=realLength;
        int newIndex=newLength;
        while(index>=0&&newIndex>index)
        {
            if(str[index]==' ')
            {
                str[newIndex--]='0';
                str[newIndex--]='2';
                str[newIndex--]='%';
            }
            else
                str[newIndex--]=str[index];
            --index;
        }
    }
};