题目:请实现一个函数,把字符串中的每个空格都替换成"%20"。例如输入"We are happy."

则输出"We%20are%20happy."

 

这道题一看到就能想到直接从前到后遍历字符串,当遇到空格时候先将空格后面的字符串中每个

字符向后移动两个位置,然后再把空格及空格之后的两个字符替换为"%20"

 

剑指Offer书上这样说到:假设字符串长度为n，每遇到一个空格，需要移动后面的O(n)个字符，

那么对于n个空格来说算法时间复杂度为O(n*n)，显然，时间复杂度为平方的方法算不上好

方法，那么有没有更好的方法呢?

 

剑指offer上提供了一种时间复杂度为O(n)的算法:

1.首先计算字符串中空格的个数。每个空格用三个字符替换，那么每多一个空格那么替换后的

字符串将多出来两个字符。因此计算出替换后字符串的长度。

2.在字符串中设置两个索引，p1索引指向字符串的结尾即'\0'处，另外一个指向计算出的

替换后字符串长度的位置。

3.当未遇到空格时候，将p1所指的字符赋值为p2所指的字符。同时索引p1,p2均向前移动一个

位置

4，当索引p1遇到空格时候将p2,p2-1,p2-2,这三个位置分别替换为'%' '2' '0'，然后索引p1向前移动

一个位置,p2向前移动三个位置。

5.替换的结束条件是，当p1和p2索引位置相同时，这时候替换空格结束。

 

 

那么通过这么详尽的算法描述，这一题的解答为:

 

1 #include 
     
       2 using namespace std; 3  4 void ReplaceBlank(char string[],int length) 5 { 6     int blankcount=0; 7     int i=0; 8     int len; 9     len=strlen(string);10 11     while(string[i]!='\0')12     {13         if(string[i]==' ')14             blankcount++;15         string++;16     }17 18     int LenAfter;19     LenAfter=strlen(string)+blankcount*2;20 21     int p1,p2;22 23     p1=len;24     p2=len+LenAfter;25     while(p1!=p2)26     {27         if(string[p1]!=' ')28         {29             30             string[p2]=string[p1];31             p1--;32             p2--;33         }34         else35         {36             string[p2--]='0';37             string[p2--]='2';38             string[p2--]='%';39             p1--;40         }41     }42 }43 44 int main()45 {46     char string[50]="We are Happy.";47     ReplaceBlank(string,50);48     cout<<"The Replaced Blank string is "<
      
       <
      
     

 

截图: