剑指Offer第二版 面试题5 替换空格

预备知识：

字符串：

1.C/C++中每个字符串都以字符 '\0' 作为结尾。好处：方便找到尾部。缺点：额外字符开销，不留神会造成字符串越界，将'\0'遗忘。

2.char* str3="hello world"; char* str4=“hello world”；    str3与str4是两个字符指针，无需为它们分配内存以存储字符串的内容，“hello world”常量字符串在内存中只有一个拷贝，两个指针指向“hello world”在内存中的地址，故 str3==str4

char str1[] = “hello world”; char str2[] = "hello world"; 这里str1和str2是两个字符串数组，会分配长度为12字节的空间，并把“hello world”的内容分别复制到数组中，这是两个初始地址不同的数组，故str1和str2不想等

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

解题思路：

为了减小时间复杂度，先遍历一次此字符数组，计算出空格和所含字符数，比如“We are happy.” 数组长度为14，空格数为2，替换之后长度为18，即14+2*2=18。在遍历时，遇到‘\0’时停止，没有算上结束符，所以长度算17，正好与数组下标0-17对应。可以用长度来表示下标。两个下标p1在当前长度位置，p2在新长度位置，当p1不断向前遍历没有遇到‘ ’时，把此时p1下标对应的值赋给p2对应值，直到遇到' '插入“%20”,依次……

代码：

实现函数

首先要判断传参过来的数组是否存在，是否为空

其次判断新长度是否超过str数组本身所开辟的内存空间。

测试部分如下：

各种情况测试

类似题目注意：从尾到前遍历移动的话会提高效率。