面试题4：字符串

解法1：从前往后扫描，碰到空格就替换，空格后面的元素向后移2。显然这种方式中有很多冗余的移动操作，其复杂度为O（n²)
解法2：先遍历一遍获得空格的总个数。
  1 #include<iostream>
  2 
  3 using std::cout;
  4 using std::cin;
  5 using std::endl;
  6 
  7 void ReplaceBlank(char str[],int length)
  8 {
  9     if (str==NULL||length<=0)
 10     {
 11         std::cerr << "string is empty OR null" << endl;
 12         return;
 13     }
 14 
 15     int originlength = 0;
 16     int numberOfblank = 0;
 17     int i = 0;
 18     while (str[i]!='')
 19     {
 20         originlength++;
 21         
 22         if (str[i++] = ' ')
 23         {
 24             numberOfblank++;
 25         }
 26     }
 27 
 28     int newlength = originlength + 2 * numberOfblank;
 29     if (newlength>length)
 30     {
 31         return;
 32     }
 33 
 34     int newpos = newlength;
 35     int oripos = originlength;
 36     while (oripos>=0&&newpos>oripos)
 37     {
 38         if (str[oripos]==' ')
 39         {
 40             str[newpos--] = '0';
 41             str[newpos--] = '2';
 42             str[newpos--] = '%';
 43         }
 44         else
 45         {
 46             str[newpos--] = str[oripos];
 47         }
 48 
 49         --oripos;
 50     }
 51 }
 52 
 53 void Test(char* testName,char *str,int length,char *expected)
 54 {
 55     if (testName!=NULL)
 56     {
 57         cout << testName << endl;
 58     }
 59 
 60     ReplaceBlank(str, length);
 61 
 62     if (str==NULL&&expected==NULL)
 63     {
 64         cout << "passed" << endl;
 65     }
 66     else if (strcmp(str,expected)==0)
 67     {
 68         cout << "passed" << endl;
 69     }
 70     else if (str!=NULL&&expected==NULL)
 71     {
 72         cout << "failed" << endl;
 73     }
 74     else
 75     {
 76         cout << "failed" << endl;
 77     }
 78 }
 79 
 80 //空格位于字符串最前面
 81 void Test1()
 82 {
 83     const int length = 100;
 84 
 85     char str[length] = " hello world";
 86     char *expected = "%20hello%20world";
 87     Test("test1", str, length, expected);
 88 }
 89 
 90 //空格位于字符串最后面
 91 void Test2()
 92 {
 93     const int length = 100;
 94 
 95     char str[length] = "hello world ";
 96     char *expected = "hello%20world%20";
 97     Test("test2", str, length, expected);
 98 }
 99 
100 //有连续多个空格
101 void Test3()
102 {
103     const int length = 100;
104 
105     char str[length] = "hello  world";
106     char *expected = "hello%20%20world";
107     Test("test3", str, length, expected);
108 }
109 
110 //没有空格
111 void Test4()
112 {
113     const int length = 100;
114 
115     char str[length] = "helloworld";
116     char *expected = "helloworld";
117     Test("test4", str, length, expected);
118 }
119 
120 //字符串为NULL
121 void Test5()
122 {
123     Test("test5", NULL, 0, NULL);
124 }
125 
126 //空字符串
127 void Test6()
128 {
129     const int length = 100;
130 
131     char str[length] = "";
132     char *expected = "";
133     Test("test6", str, length, expected);
134 }
135 
136 //全是空格
137 void Test7()
138 {
139     const int length = 100;
140 
141     char str[length] = "   ";
142     char *expected = "%20%20%20";
143     Test("test7", str, length, expected);
144 }
145 int main()
146 {
147     Test1();
148     Test2();
149     Test3();
150     Test4();
151     Test5();
152     Test6();
153     Test7();
154 
155     return 0;
156 }
View Code