【18】替换空格

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

方案一：朴素做法是枚举字符串，每次找到一个字符串把当前空格后面的字符串往后移动2个，再把%20插入。这样每次枚举一个字符可能就要移动n个字符，总的n个字符，时间复杂度O(n^2)，效率低

方案二：1.先利用O(n)的时间求出字符串中所有的空格的个数，这样就可以求出替换后总的字符串长度

               2. 然后从后往前枚举字符，如果不是空格，则依次把字符存放在最终的位置上，遇到空格的时候就填上%20

               3. 例如字符串"we are happy."，总的空格数为2，则最后字符串长度为17

                   从后往前枚举字符串，第一个是y直接填入第17个位置，然后是p，依次.....

                   直到遇到空格的时候往前填入0、2、%，然后继续枚举字符串

               这个方法的时间复杂度O(n)，比起朴素算法效率高了很多

#include<iostream>
#include<algorithm>
using namespace std;

void ReplaceBlank(char *string){
	//如果是空串直接返回
	if(string == NULL){
	   return;
	}
	//求字符串的空格数
	int length = strlen(string);
	int blankCount = 0;
	for(int i = 0; i < length; i++){
		if(string[i] == ' '){
		   ++blankCount;
		}
	}
	//新的字符串的长度
	int newLength = length+2*blankCount;
	//新的字符串
	string[newLength] = '\0';
	int pos = newLength-1;
	for(int i = length-1; i >= 0; i--){
		if(string[i] != ' '){
		   string[pos] = string[i];
		   --pos;
		}
		else{
		   string[pos--] = '0';
		   string[pos--] = '2';
		   string[pos--] = '%';
		}
	}
}

int main(){
    //样例
	char string[] = "we are happy.";
	ReplaceBlank(string);
	cout<<string<<endl; //输出we%20are%20happy.

	return 0;
}