【剑指Offer】 002 替换空格

【剑指Offer】 002 替换空格

题目链接： 剑指Offer 第二题 牛客网

题目描述：

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy

常规思路 时间复杂度为O(N^2)不足以拿到Offer！！

常规思路：

从头到尾扫描字符串，每一次碰到空格字符的时候做替换。由于是把1个字符替换称3个字符，我们必须把空格后面的所有的字符都后移两个字节，否则就有两个字符被覆盖了。（这种方法从前向后替换和从后向前替换是一样的）

如图，我们把“We Are Happy”中的每一个空格替换成%20。

W

e

a

r

e

h

a

a

p

y

\0

W

e

%

2

0

a

r

e

h

a

a

p

y

\0

W

e

%

2

0

a

r

e

%

2

0

h

a

a

p

y

\0

第一行为原字符串，当我们遇到了第一个空格，第二行深黄色字符即为需要向后移动的字符，当我们遇到了第二个空格，替换之后如图第三行所示，红色部分“happy”被移动了两次。

假设字符的长度是n。对每个空格字符，需要移动后面O(n)个字符，因此对含有O(n)个空格字符串而言总的时间效率是O(n^2).

进阶思路 时间复杂度为O(n)，轻松搞定Offer！！

进阶思路：

从字符串的后面开始复制和替换，首先准备两个指针，p1和p2，p1指向原始字符串的末尾，p2指向替换后字符串的末尾，接下来，向前移动指针p1，逐个把它指向的字符复制到p2，碰到一个空格之后，把p1向前移动1格，在p2处插入字符串“20%”，由于“20%”长度为3，同时也要把p2向前移动3格。直到p1=p2，表明所有空格都已经替换完毕。（从后向前好，因为后面有留出来的位置，而前面没有，是数据）

详细过程：

先遍历一遍字符串，计算出空格的数量和字符串长度，而替换后的字符串长度=原字符串长度+空格数*2。例如“We are happy”字符串长度length为12，而大小size为13（末尾有\0），里面有两个空格，所以替换后的字符串长度length为16，大小size为17。

我们从字符串的后面开始复制和替换。首先准备两个指针，P1和P2.   P1指向原始字符串的末尾，而P2指向替换之后的字符串的末尾。接下来我们向前移动指针P1,逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。此时字符串包含如下图b所示，灰色阴影的区域是做了字符拷贝的区域。碰到第一个空格之后，把P1向前移动一格，在P2之前插入字符串”%20“，由于”%20“的长度为3，同时也要把P2向前移动3格如图所示。

我们接着向前复制，直到碰到第二个空格（d)所示。和上一次一样，我们再把P1向前移动1格，并把P2向前移动3格插入”%20“（如图e)，此时P1，P2指向同一个位置，表明所有的空格都已经替换完毕。

从上面的分析我们可以看出，所有的字符都只复制一次，因此这个算法的时间效率是O(n)，比第一个思路要快。

C++代码：

class Solution {
public:
	void replaceSpace(char *str,int length) {//遍历一边字符串找出空格的数量
		if (str == NULL || length<0)

			return;
		int oldLength=0;//记录以前的长度
		int spaceNum=0;//记录空格的数量
		int i=0;
		while(str[i]!='\0')
		{
			if(str[i]==' ')
			{
				spaceNum++;
			}
			oldLength++;//最后一次+1后指向了'\0'
 			i++;
		}
		int newLength=oldLength+spaceNum*2;//插入后的长度（包括了'\0'）
		while(oldLength>=0&&newLength>oldLength)//放字符
		{
			if(str[oldLength]==' ')//碰到空格就替换
			{
				str[newLength--]='0';
				str[newLength--]='2';
				str[newLength--]='%';
			}
			else{//不是空格就把oldLength指向的字符装入newLength指向的位置
				str[newLength--]=str[oldLength];
			}
			oldLength--;//不管是if还是elsr都要把oldLength前移
		}
	}
};

日期：2018/2/11-0:14