剑指offer面试题（4）—替换空格

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

方法1.

从头到尾扫描字符串，每一个碰到空格字符的时候做替换。由于是把一个字符替换成三个字符，我们必须要把空格后面所有的字符都向后移动两个字节，否则就有两个字符被覆盖了。

代码如下：

#include<iostream>
using namespace std;
#define MAX 80
void Sp_Replace(char *str)
{
	for(int  i=0;str[i]!='\0';i++)
	{
		if(str[i]==' ')
		{
			for(int j=strlen(str)+2;j>=i+3;j--)
			{
				str[j]=str[j-2];
			}
			str[i]='%';
			str[i+1]='2';
			str[i+2]='0';
		}
	}
}
int main(void)
{
	char *str=(char *)malloc(sizeof(char )*MAX);
	cout<<"enter the string str"<<endl;
	gets(str);
	Sp_Replace(str);
	puts(str);
	return 0;
}

时间复杂度为0(n^2),效率太低

方法2.从字符串的后面开始复制和替换，准备两个索引，indexofNew 指向替换之后的字符串的末尾，indexofOriginal指向原始字符串的末尾。接下来向前移动指针indexofOriginal,逐个把它指向的字符复制到indexofNew的位置，直到碰到第一个空格为止，碰到第一个空格之后，把indexofOriginal移动1个位置，在indexofNew之前插入字符串"%20",此时indexofNew需向前移动三个位置。

代码：

#include<iostream>
using namespace std;
void Sp_Replace(char str[],int length)
{
	int originalLength=0;
	int numberofBlank=0;
	int indexofNew;
	int indexofOriginal;
	if(str==NULL && length<=0)
	{
		return ;
	}
	int i=0;
	while(str[i]!='\0')
	{
		originalLength++;
		if(str[i]==' ')
		{
			numberofBlank++;
		}
		i++;
	}
	indexofNew=originalLength+2*numberofBlank;//一个索引指向新字符串的尾部
	indexofOriginal=originalLength;//一个索引指向旧字符串的尾部
	while(indexofOriginal>=0 && indexofNew>indexofOriginal)
	{
		if(str[indexofOriginal]==' ')
		{
			str[indexofNew--]='0';
			str[indexofNew--]='2';
			str[indexofNew--]='%';
		}
		else
		{
			str[indexofNew--]=str[indexofOriginal];
		}
		indexofOriginal--;
	}
}
int main(void)
{
	char str[80];
	cout<<"input the originak string:"<<endl;
	gets(str);
	Sp_Replace(str,80);
	cout<<"the new string is:"<<endl;
	puts(str);

}

时间复杂度为O(n)