1 题目

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

2 思路

先遍历一次字符串，统计字符串中空格的总数。然后计算出替换后字符串的长度。
从字符串的后面向前开始复制替换。首先准备两个指针：p1和p2，p1指向原始字符串的末尾，而p2指向替换之后的字符串的末尾，接下来我们向前移动指针p1，逐个把它指向的字符复制到p2指向的位置，直到碰到空格。然后把p1向前移动1格，再将p2向前插入字符串“%20”。由于“%20”的长度为3，p2要向前移动3格。重复以上过程直至指向同一位置，表明所有空格都已替换完毕。
所有的字符都只复制（移动）了一次，因此这个算法的时间效率是O（n）。

3 代码示例

void ReplaceBlank（char string[],int length）
{
	// 判断是否有效
	if(length<=0||string==nullptr)
		return;
	// 遍历字符串，求空格总数
	int numberOfBlank=0;
	int originalLength=0;
	int i=0;
	while(string[i]!=‘\0‘)
	{
		originalLength++;
		if(string[i]=‘‘)
			numberOfBlank++;
		i++;
	}
	int newLength = originalLength + 2*originalLength;
	if(newLength > length)
		return;
	// 开始替换
	int indexOfOriginal = originalLength;
	int indexOfNew = newLength;
	while(indexOfOriginal>0&&indexOfNew > indexOfOriginal)
	{
		if(string[indexOfOriginal]==‘‘)
		{
			string[indexOfNew--] = ‘0‘;
			string[indexOfNew--] = ‘20‘;
			string[indexOfNew--] = ‘%‘;
		}else
		{
			string[indexOfNew--] = string[indexOfOriginal]
		}
		indexOfOriginal--;
	}
}

4 拓展

题目：若有两个排序数组A1和A2，内存在A1的末尾有足够多的空余控件容纳A2，请实现一个函数，把A2中所有的数字插入A1中，并且所有的数字是排序的。
思路：从尾部开始标记A1和A2中的数字，并且把较大的数字复制到A1中合适的位置。如果从前往后复制每个数字，则需要重复移动数字多次，可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率。

参考：
《剑指offer》

面试题5：替换空格

原文：https://www.cnblogs.com/qtfy-ydxy/p/14529234.html