替换空格 合并数组字符串

把字符串中的每个空格换成“%20”。

注意：如果在原来的字符串上做替换，要保证字符串最后有足够的空余内存

直接的解法：时间复杂度为O(n^2)

从头到尾扫描字符串，每次碰到空格的时候做替换。由于是把一个字符换成三个字符，必须把空格

后面的所有字符都向后移动两个字节，否则就有两个字符被覆盖了。

效率不高的原因是很多字符都移动了很多次，所以应该减少移动次数。

从后向前替换：时间复杂度是O(n)

我们可以先遍历一次字符串，这样就能统计出字符串的总长度和空格的数目。每替换一次空格，

长度增加2.因此，我们替换以后的字符串长度等于原来的长度加上2*空格的数目。

我们从字符串的后面开始复制和替换。首先定义两个指针，P1和P2。P1指向原始字符串的尾部

P2指向替换后字符串的尾部，接下来向前移动指针P1，诸葛把它指向的字符复制到P2指向的位置，知道碰到第一个空格为止。碰到第一个空格以后，把P1向前移动一格，在P2之前插入“%20”。同时把P2向前移动3格。

从上面的分析可以看出，所有的字符串都只复制（移动一次），因此时间复杂度为O(n)。

#include<stdio.h>
#include<string>

void exchange(char str[])
{
	//if(str)
		//return;

	int strlength=0;
	int spacelength=0;
	int i=0;
	while(str[i]!='\0')
	{
		if(str[i]==' ')
			++spacelength;
		
			++strlength;

		
		i++;
		printf("%d\n",i);

		
	}
	printf("wo shi chang du\n");
	printf("%d\n",strlength);

	int afterlength;
	afterlength=strlength+spacelength*2;

	printf("\nwo shi xin chang du \n");
	printf("%d",afterlength);

	while(afterlength>strlength && strlength>=0)
	{
		if(str[strlength]==' ')
		{
			str[afterlength--]='0';
			str[afterlength--]='2';
			str[afterlength--]='%';
			
		}
		else
		{
			str[afterlength--]=str[strlength];
			
		}
		strlength--;
	}

}

void main()
{
	char str[]="we are happy";
	printf("%s\n",str);

	exchange(str);
	printf("%s\n",str);

	getchar();

}
           

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

例如：有两个排序的数组A1和A2，内存在A1的末尾有足够的空余空间容纳A2。要把A2中所有的数字插入到A1中并且所有的数字是排序的。更好的办法是从尾到头比较A1和A2中的数字，并把较大的数字复制到A1的合适位置。