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

方法1： 重新申请一个数组，然后遍历原来的数组，遇到空格，就用%20填充新的数组，最后得到结果；缺点：要重新申请数组

方法2： 从前往后遍历，遇到空格就把后面的内容向后移动两位；缺点：有些内容会向后移动n次，如果有n个空格，算法时间复杂度为O(n^2)；

方法3： 因为把空格替换为”%20“，每次替换多2个字符，因此可以统计出字符串中空格的总个数，然后新数组大小为  “原数组大小 + 2*空格数 ”。从后往前处理：遇到非空格，直接搬到后面，遇到空格替换为”%20“. 直到待插入位置指针和原数组为指针重合位置

下面示意图：

代码思路：先遍历数组得到空格个数；由空格的个数得到新数组的长度： 原数组大小 + 2*空格数 ；从后往前遍历数组，如果不是空格，就直接移动到新的组；

如果是空格，就在新的数组当中插入%20；‘0‘,‘2‘,‘%‘;

void ReplaceBlank(char string[],int length){	if (string == NULL && length <= 0)	{		return;	}	int oldLength = 0;	int numOfBlank = 0;	int i = 0;	while (string[i] != '\0')	{		++oldLength;		if (string[i] == ' ')		{			++numOfBlank;		}		++i;	}	int newLength = oldLength+ numOfBlank*2;	if (newLength > length)	{		return;	}	while (oldLength >= 0 && newLength > oldLength)	{		if (string[oldLength] == ' ')		{			string[newLength--] = '0';			string[newLength--] = '2';			string[newLength--] = '%';		}		else		{			string[newLength--] = string[oldLength];		}		--oldLength;	}		/*	int indexOfOldLength = oldLength;	int indexOfNewLength = newLength;	while (indexOfOldLength >= 0 && indexOfNewLength > indexOfOldLength)	{		if (string[indexOfOldLength] == ' ')		{			string[indexOfNewLength--] = '0';			string[indexOfNewLength--] = '2';			string[indexOfNewLength--] = '%';		}		else		{			 string[indexOfNewLength--] = string[indexOfOldLength];		}		--indexOfOldLength;	}		*/}

完整测试代码：

// ReplaceBlank.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>using namespace std;void ReplaceBlank(char string[],int length){	if (string == NULL && length <= 0)	{		return;	}	int oldLength = 0;	int numOfBlank = 0;	int i = 0;	while (string[i] != '\0')	{		++oldLength;		if (string[i] == ' ')		{			++numOfBlank;		}		++i;	}	int newLength = oldLength+ numOfBlank*2;	if (newLength > length)	{		return;	}	while (oldLength >= 0 && newLength > oldLength)	{		if (string[oldLength] == ' ')		{			string[newLength--] = '0';			string[newLength--] = '2';			string[newLength--] = '%';		}		else		{			string[newLength--] = string[oldLength];		}		--oldLength;	}		/*	int indexOfOldLength = oldLength;	int indexOfNewLength = newLength;	while (indexOfOldLength >= 0 && indexOfNewLength > indexOfOldLength)	{		if (string[indexOfOldLength] == ' ')		{			string[indexOfNewLength--] = '0';			string[indexOfNewLength--] = '2';			string[indexOfNewLength--] = '%';		}		else		{			 string[indexOfNewLength--] = string[indexOfOldLength];		}		--indexOfOldLength;	}		*/}int _tmain(int argc, _TCHAR* argv[]){	char s[20] = "We are Happy.";	for (int i = 0; i < 20; i++)	{		cout<<s[i];	}	ReplaceBlank(s,20);	cout<<endl;	for (int i = 0; i < 20; i++)	{		cout<<s[i];	}	getchar();	return 0;}

主要思想:

合并两个数组（包括字符串）时，如果从前往后复制每个数字需要重复移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样能减少移动的次数，从而提高效率。

另外一个题目：合并两个排序的数组，用到的思想也是 从后往前遍历。

C++算法之 替换数组空格