剑指Offer算法题之字符串替换字符--面试题4：替换空格

将字符串里面的空格，替换成相应的字符

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

题目背景：在网络编程中，如果URL参数中含有特殊字符，如空格，可能导致服务器端无法获得正常的参数值。因此我们需要将这些特殊符号转换成服务器可以识别的字符。一般转换规则是在‘%’后面跟上ASCII码的十六进制的表示。例如空格就被替换成“ ”。

题目思考：首先应该想到的是一个空格字符替换成3个字符“ ”，因此字符串的长度会增长。如果是直接在原字符串上替换，就可能覆盖修改在该字符串后面的内存。如果是创建一个新的字符串并在新的字符串上做替换，那么可以自己分配足够的空间作为替换，这样的就可以避免有用的字符串被覆盖的问题。

实现方法：本题可以只遍历一次就完成替换。所有的字符都只复制一次，因此时间复杂符为O（n）。

我们先遍历一次字符串，这样就能统计出字符串中空格的总数，并由此计算出替换过后字符串的长度。我们还是以“We are happy.”为例，这个字符串的长度是14（包括点号和结尾符号\0）,里面有两个空格，因此替换之后字符串的长度是18。 因为本题是实现方式是进行一次替换就完成，因此本题需要从字符串的后面开始复制和替换。首先准备两个指针，P1和P2。P1指向原始字符串的末尾，而P2指向替换后的字符串的末尾（如a）。接下来我们向前移动指针P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止(如b)。灰色背景的区域是做了字符拷贝的区域。碰到第一个空格后把P1向前移动一格，在P2之前插入字符串“ ”，也就是说把P2向前移动三格。 继续向前复制，直至碰到下一个空格。最终完成复制的时候，P1和P2指向同一位置，表明所有空格都已经替换完毕。

#### 代码部分： #include<iostream> #include <string> using namespace std; //这里的length是字符串的总长度 void ReplaceBlank(char string[],int length) { //考虑边界情况 if(string==NULL||length<=0) //由于返回值为空，因此返回空即可 return ; //计算空格数和实际字符个数 int blanknum=0; int origianlnum=0; int i=0; while(string[i]!='\0') { origianlnum++; if(string[i]==' ') blanknum++; i++; } //定义新的字符串长度 int newnum=origianlnum+2*blanknum; //定义两个指针，由于是字符串，可以直接采用下标调用的方式 if (newnum>length) return; int p1=origianlnum; int p2=newnum; //循环条件就是第一个下标不小于0且第二个下标大于第一个下标 while(p1>=0&&p2>p1) { if(string[p1]!=' ') { string[p2]=string[p1]; p1--; p2--; } else { string[p2]='0'; string[p2-1]='2'; string[p2-2]='%'; p1--; p2=p2-3; } } } int main() { //创建测试案例，定义字符串并调用函数 char string1[50]="We are happy."; ReplaceBlank(string1,50); char string2[50]="I have a dream."; ReplaceBlank(string2,50); char string3[50]="Basketball is my dream."; ReplaceBlank(string3,50); cout<<string1<<endl; cout<<string2<<endl; cout<<string3<<endl; system("pause"); return 0; }