一题一算法2018-02-02（替换空格）

题目很简单，但是真正做起来，还是遇到一些问题。
那我们接下来看一下：

题目： 替换空格

题目描述：

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

思路分析：

首先我们看到这个问题想到的是so easy，我们于是脑洞大开，这还不简单，再创建一个字符串，挨个复制进去遇到空格的时候我们将空格替换，这应该是绝大多数人的思路，这个思路操作起来也不难，但是有些地方需要注意，我们在创建被被复制字符串数组的时候需要先设定被复制的数组的大小，复制过程中按位复制等问题，但是还存在的问题是，但是还存在的问题是，假如不让我们创建复制的字符串的时候，我们需要怎么操作。

进阶想法：

我们想到在源数组上操作，那么我们需要进行的就是从头开始查找空格，找到之后将数组中空格之后的数据全部向后推移2位，n个字符串的数组，对于每个空格，我们需要移动后面o(n)个字符，所以对于含有o(n)个空格字符串的字符串的时间复杂度就是O(n^2).

最终想法：

我们在不创建新字符数组的时候怎么样实现呢，我们在源字符数组上面进行操作，我们需要进行下面几步：

1、分别得到源字符数组的长度、空格的个数
2、源字符数组最终会变成的长度= 源字符数组的长度+空格的个数*2（因为一个空格变成了三个字符长度）
3、开始替换从后往前查找，按照字符从后往前写,我们定义两个指针，分别指向新和旧两个字符数组的最后面，然后碰到空格就改变

image.png

代码实现：

class Solution {
public:
    void replaceSpace(char *str,int length) {
        int blankNum = 0;
        int strLength = 0;
        int i = 0;
        while(str[i] != '\0'){
            strLength ++;
            if(str[i] == ' '){
                blankNum ++;
            }
            i++;
        }
        int desStrLength = strLength + blankNum*2;
        if(desStrLength > length)
            return;
        //从后往前替换
        //源字符串最后的位置
        int indexStr = strLength;
        //目的字符串最后的位置
        int indexDes = desStrLength;
        while(indexStr >= 0 && indexDes > indexStr){
            if(str[indexStr] == ' '){
                str[indexDes--] = '0';
                str[indexDes--] = '2';
                str[indexDes--] = '%';
            }else{
                str[indexDes--] = str[indexStr];
            }
            indexStr--;
        }
        
    }
};