将一个字符串中的空格替换成20%。

题目：实现一个函数，把一个字符串中的空格替换成20%，或是其他字符。

解析：对于常规解法，就是扫描字符串，每次碰到空格进行替换。由于是把一个空格替换成三个字符，所以必须把空格后面的字符都往后挪两个位置。假设字符串的长度是n，对于每个空格字符的替换，都要移动o(n)个字符，因此对于含有o(n)个字符的字符串来说，时间效率为o(n2)。

提供一种复杂度为o(n)的解法。

我们从后往前遍历，使用两个指针p1和p2，p1指向原始字符串的末尾，p2指向替换后的字符串的末尾，遇到空格进行替换，且每个字符的挪动只有一次，效率是o(n)。

#include<iostream>
using namespace std;

void show(char *string, int len)
{
	for (int i = 0; i < len; i++)
	{
		cout << string[i] << " ";
	}
	cout << endl;
}

void ReplaceBlack(char *string)
{
	if (string == NULL)
	{
		return;
	}
	int len = 0;
	int lenNull = 0;
	int i = 0;
	while (string[i] != '\0')
	{
		len++;
		if (string[i] == ' ')
		{
			lenNull++;
		}
		i++;
	}
	cout << "len=" << len << endl;
	cout << "lenNull=" << lenNull << endl;
	show(string, len);

	int len2 = len + lenNull * 2;
	cout << "len2=" << len2 << endl;
	int newpointer = len2;//指针指向新的空间的末尾
	int oldpointer = len;//指针指向旧的空间的末尾

	while (oldpointer >= 0 && newpointer > oldpointer)
	{

		if (string[oldpointer] == ' ')
		{
			string[newpointer--] = '0';
			string[newpointer--] = '2';
			string[newpointer--] = '%';
		}
		else{
			string[newpointer--] = string[oldpointer];
		}
		oldpointer--;
	}
	show(string, len2);
}


int main()
{
	char string[50] = { "we are happy and exected" };
	ReplaceBlack(string);
	return 0;
}