请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
题目链接：https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423?tpId=13&&tqId=11155&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题解：
最直观的解法是对字符串进行遍历，每次遍历到空格之后，将其替换为“%20”，这样，对于n个空格，需要把剩下的字符串移动n次，这样整个算法时间复杂度就是O(n^2)。为了节省时间，我们可以采用空间换取时间的方式，首先遍历一遍字符串，统计空格的数量，并由此创建辅助数组；接着第二次遍历字符串，将空格替换为“%20”存储在辅助数组中，这样需要的时间复杂度为O(n)，但需要的空间复杂度为O(n)。使用空间换取时间的方式还可以用队列实现，同样也需要O(n)的空间。
不过这样就是最优的解法了吗，我们是否可以找到不需要额外辅助数组的方法进行；首先从第二种解法中获得启发，我们先遍历一遍字符串数组，那么我们可以事先计算好替换后的字符串的总长度，然后，在遍历替换空格的时候，采用从后向前遍历，不是空格的直接移动到最后的位置，这样，我们就可以一次性移动整个数组而不需要额外的时间开销，时间复杂度为O(n)；
代码：
class Solution { public: void replaceSpace(char *str,int length) { if (str == NULL || length <= 0){ return; } int space_nb = 0; int replace_len = 0; int i; for(i = 0; i < length; i ++){ if (str[i] == ' '){ space_nb ++; } } if (str[i-1] != '\0') return; if (space_nb != 0){ replace_len = length + space_nb * 2 - 1; for (i=length-1; i >= 0; i--){ if (str[i] == ' '){ str[replace_len] = '0'; replace_len --; str[replace_len] = '2'; replace_len --; str[replace_len] = '%'; replace_len --; }else{ str[replace_len] = str[i]; replace_len --; } } } } };
