剑指offer面试题

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

看到题目后的思路

看到这个题目后，我们首相应该想到的是：原来的一个空格字符，经过替换后就成了三个字符，因此字符会变长，那么很有可能会覆盖原来的字符。如果是在一个新创建的字符串上做替换，就可以有足够的空间，显然题目上没有明显的提出，那就应该在原来的字符串上做替换

伪代码实现

1. 求出该字符串的长度和字符串中含有的空格数
2. 求出替换后的字符串的总长度
3. 准备两个指针pStr1，pStr2，pStr1指向原始字符串的末尾，pStr2指向替换后的字符串末尾
4. 向前移动pStr1和pStr2，逐个将pStr1指向的字符拷贝到Pr2指向的位置，知道遇到第一个空格为止
5. 遇到空格后，将pStr1向前移动一次，然后在pStr2之前插入“%20”，插入一个字符pStr2就要向前移动一次
6. 继续向前移动pStr1和pStr2，逐个将pStr1指向的字符拷贝到pStr2指向的位置，遇到空格继续做“5”操作，直到pStr2和pStr1相等，说明空格已经全部替换完毕

思维图

（图片来源《剑指offer》）

c++代码实现

class Solution {
public:
	void replaceSpace(char *str, int length) {
		if (str == NULL && length <= 0)
			return;
		//如果是空直接返回

		int factlength = 0;
		//实际字符数
		int spacenumber = 0;
		//字符串中空格的数量
		int i = 0;

		while (str[i] != '\0')
		{
			++factlength;
			if (str[i] == ' ')
			{
				++spacenumber;
			}
			++i;
		}

		//扩展第二个字符串,
		//空格的数量*2是因为“%20”一共三个字符，需要在原来每个空格的位置再加上两个字符的长度，才是第二个字符串的
		int newlength = factlength + spacenumber * 2;

		if (newlength > length)
		{
			return;
		}

		//从后向前替换，这样会减少替换的次数
		char *pStr1 = str + factlength;
		char *pStr2 = str + newlength;
		//如果pStr2 <= pStr1 了，说明剩下的pStr2和pStr1的字符串相同了，也就没有“ ”了，就不用替换了
		while (pStr2 > pStr1 && pStr1 >= 0)
		{
			if (*pStr1 == ' ')
			{
				*pStr2-- = '0';
				*pStr2-- = '2';
				*pStr2-- = '%';
			}
			else
			{
				*pStr2-- = *pStr1;
			}
			--pStr1;
		}
		return;
	}
};