替換空格 合并數組字元串

把字元串中的每個空格換成“%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的合适位置。