《剑指offer面试题4》替换空格——实现函数把字符串中每个空格替换成“%20”

思路：

例如把we are happy这个字符串中所有空格替换成"%20"，最直接的做法是从头开始扫苗，遇到空格就替换，并且把空格后面的字符都顺序后移。复杂度O(n^2)。

重要思想（这个从后往前的思想特别重要，举一反三的例子也是）：先扫描一遍字符串统计出空格数量blanknum，由于每个空格被替换成3个字符"%20"，即每替换一个空格总长度增加2，因此最后总的长度应该是原长+blanknum*2。然后对字符串从后往前扫描，不是空格的直接移动到新位置，如果是空格替换成%20。

 1 #include <iostream>
 2 #include <string>
 3 #define maxlen 100
 4 using namespace std;
 5 
 6 void ReplaceBlank(char strarr[], int length) //length是string总容量
 7 {
 8     int oldlength,newlength,blanknum;
 9     if(strarr == NULL && length <= 0) return; //先检查参数合法
10     int i=0;
11     blanknum=0;
12     oldlength = strlen(strarr)+1;
13  /*   while(strarr[i] != '')       
14     {
15        // cout<<"b";
16         if(strarr[i] == ' ')
17         {
18          blanknum++;
19          i++;
20         }
21     }*/
22     for(int i=0; i<oldlength; i++)
23     {
24         if(strarr[i] == ' ')
25         {
26             blanknum++;
27         }
28     }
29     newlength = oldlength + blanknum*2;
30     if(newlength > length) return; //随时注意检查合法性
31     int indexOfOld = oldlength;
32     int indexOfNew = newlength;
33     while(indexOfOld >= 0)
34     {
35         if(strarr[indexOfOld] != ' ')
36         {
37             strarr[indexOfNew] = strarr[indexOfOld];
38             indexOfNew--;
39             indexOfOld--;
40         }
41         else
42         {
43             strarr[indexOfNew] = '0';
44             strarr[--indexOfNew] = '2';
45             strarr[--indexOfNew] = '%';
46             indexOfNew--;
47             indexOfOld--;
48         }
49     }
50 }
51 
52 
53 int main()
54 {
55     char strarr[maxlen];
56     cout<<"Input a string:";
57     gets(strarr);
58     puts(strarr);
59     ReplaceBlank(strarr,maxlen);
60     puts(strarr);
61     return 0;
62 }

View Code

代码里从13行开始的while循环很bug，一直死循环，看起来像是没有''，但是前一行已经用了strlen可以通过说明应该有''啊。

举一反三：

有两个已排序数组A，B，A的末尾有足够的空间放A和B。现要求将B所有元素插入A中并仍是有序的，要求O(n)。

类似的：用两个index标记从后往前把大的移动到后面。

 1 #include <iostream>
 2 #define maxn 100
 3 using namespace std;
 4 int arrA[maxn*2],arrB[maxn];
 5 
 6 void Merge(int alen, int blen)
 7 {
 8     int newlen = alen + blen;
 9     int indexOfA = alen - 1;
10     int indexOfB = blen - 1;
11     int indexOfNew = newlen - 1;
12     while(indexOfA >= 0 && indexOfB >= 0)
13     {
14         if(arrA[indexOfA] > arrB[indexOfB])
15         {
16             arrA[indexOfNew] = arrA[indexOfA];
17             indexOfA--;
18             indexOfNew--;
19         }
20         else if(arrA[indexOfA] < arrB[indexOfB])
21         {
22             arrA[indexOfNew] = arrB[indexOfB];
23             indexOfB--;
24             indexOfNew--;
25         }
26         else
27         {
28             arrA[indexOfNew] = arrA[indexOfA];
29             indexOfA--;
30             indexOfNew--;
31             arrA[indexOfNew] = arrB[indexOfB];
32             indexOfB--;
33             indexOfNew--;
34         }
35     }
36     while(indexOfB >= 0)
37        arrA[indexOfNew--] = arrB[indexOfB--];
38 }
39 
40 int main()
41 {
42     int alen,blen;
43     cout<<"Input A B length:";
44     cin>>alen>>blen;
45     cout<<"Input arrA:";
46     for(int i=0;i<alen;i++)
47         cin >> arrA[i];
48     cout<<"Input arrB:";
49     for(int i=0;i<blen;i++)
50         cin>>arrB[i];
51     Merge(alen,blen);
52     cout<<"After Merge arrA:";
53     for(int i=0; i<alen+blen; i++)
54         cout<<arrA[i]<<' ';
55     return 0;
56 }

View Code