题目：

请实现一个函数，把字符串中的每个空格替换成“%20”，例如输入“We are happy”,则输出“We%20are%20happy”。

思路：

背景：

在网络编程中，如果URL参数中含有特殊字符，如空格，#等，导致服务器端无法获得正确的参数值，我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则就是在‘%’后面跟上ASCII码的两位十六进制的表示，比如空格的ASCII码是32，即十六进制的）0x20，因此空格被替换为“%20”。

方法：

1、假设可以开辟新的空间。

　创建一新字符串，并在新字符串上面做空格替换。

　时间复杂度：O(n)，空间复杂度：O(n)

2、假设不能开辟新的空间，且原字符串长度足够。

• 从头到尾扫描字符串，每遇到空格字符时做替换，将1个字符替换为3个字符，因此空格后面的字符需要后移两个字符。

　　时间复杂度：O(n^2)，空间复杂度：O(0)

• 从尾向头扫描字符串，每遇到空格字符时做替换，无需后移字符。首先遍历一遍字符串，统计字符串中空格的个数，并计算替换后字符串的总长度，每替换一个空格，长度增加2.替换时，准备两个指针P1，P2分别指向原始字符串的末尾和替换后字符串的末尾，依次移动指针P1，遇到空格做替换，直至P1和P2相遇，即前面不再有空格出现。

　　时间复杂度：O(n)，空间复杂度：O(0)

代码：

#include 
     
      using namespace std;void ReplaceBlank(char string[],int length){    if(string==NULL || length<=0)        return;    int originalLength=0;    int numberOfBlank=0;    int i=0;    while(string[i]!='\0'){        ++originalLength;        if(string[i]==' ')            ++numberOfBlank;        ++i;    }    int newLength=originalLength+numberOfBlank*2;    if(newLength>length)        return;    int indexOfOriginal=originalLength;    int indexOfNew=newLength;    while(indexOfOriginal>=0 && indexOfNew>indexOfOriginal){        if(string[indexOfOriginal]==' '){            string[indexOfNew--]='0';            string[indexOfNew--]='2';            string[indexOfNew--]='%';        }        else            string[indexOfNew--]=string[indexOfOriginal];        --indexOfOriginal;    }}int main(){    char sentence[100]="We are happy!";    ReplaceBlank(sentence,100);    cout << sentence << endl;    return 0;}
     

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/4060ac7e3e404ad1a894ef3e17650423?rp=1

AC代码：

class Solution {public:	string replaceSpace(string str) {    	int originalLength=0;    	int numberOfBlank=0;    	int i=0;    	while(str[i]!='\0'){        	++originalLength;        	if(str[i]==' ')            	++numberOfBlank;        	++i;    	}    	int newLength=originalLength+numberOfBlank*2;    	//if(newLength>length)        //	return;    	int indexOfOriginal=originalLength;    	int indexOfNew=newLength;    	while(indexOfOriginal>=0 && indexOfNew>indexOfOriginal){        	if(str[indexOfOriginal]==' '){            	str[indexOfNew--]='0';            	str[indexOfNew--]='2';            	str[indexOfNew--]='%';        	}        	else            	str[indexOfNew--]=str[indexOfOriginal];        	--indexOfOriginal;    	}    	return str;	}};