剑指offer-面试题4.替换空格

本文主要是介绍剑指offer-面试题4.替换空格，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目:请实现一个函数,把字符串中的每个空格都替换成"%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 <iostream>
 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         else
35         {
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 "<<string<<endl;
49 
50     return 0;
51 }