前言

说到字符串，其实在 C/C++ 中字符串都是以'\0'作为结尾标志。这样做的优点是容易找到字符串尾部，而缺点则是每个字符串额外多了一个字符的内存开销(1 字节),最后计算字符串的实际长度时会比原来多1。

另外，为了节省内存，C/C++ 把常量字符串存储到单独的内存区域，因此，当多个指针赋值给相同的常量字符串时，这些指针所指向的内存地址是相同的。

最后，注意字符数组容量的长度以及字符串实际长度的区别。

题目描述(替换空格)

请实现一个函数，把字符串中的每个空格替换成”%20”。例如，输入 “We are happy.”，则输出 “We%20are%20happy.”。

解题思路

常规思路

我们可以从左往右扫描字符串中的每个字符，但遇到空格的时候，先把空格之后的所有字符统一向后移动两个字符，这样一来刚好空出三个位置，然后再依次填入三个字符’%’,’2’,’0’,接下来，继续查找空格字符，继续执行相同操作。

此方法的缺点是时间复杂度较高,还不是最优的情况，达到了O(n^2)。其实，这种情况有点类似直接插入排序法的操作。对于每个空格的字符，需要移动后面O(n)个字符，那么对于含有O(n)个空字符的字符串而言，总的时间复杂度为O(n^2)。

终极思路

常规思路中的缺点在于，当我们遇到一次空格，然后移动一次后面的所有字符，此时我们无法保证这些字符在之后不会被再次移动。而我们要寻找的就是能不能让移动的这些字符一次就能确定其最终的位置？

常规思路中，是从前往后扫描字符，那么从后往前扫描字符呢。
首先，我们应该统计非空字符的个数，以及空格的个数，那么将一个空格替换为三个字符，原数组长度将增加 2，最后我们得到了字符串中空格都替换成 “%20”所需的长度。

那么，当我们从后往前扫描时，我们先确定替换之后字符串的最终长度。然后利用两个指针 P1和P2 在数组后面复制和替换。当 p1遇到非空字符，则将 p1 所指的元素复制到 p2所指的位置，然后p1、p2继续向前更新指针；当p1 遇到空字符时，将”%20”倒序依次从 p2 处往前插入,接下来，p1、p2 继续向前更新指针，重复上述过程，直至完成替换。具体形象的操作见下图。

算法实现

复杂度分析

我们先用第一个 while 遍历了字符串，耗时约 O(n),第二个 while 中我们主要是移动和插入元素，由于每个元素最多仅移动一次，因此耗时也约 O(n),那么总的时间复杂度为 O(n)=O(n)+O(n)。空间复杂度为 O(1)。

参考

<<剑指offer2>>