面试题4：替换空格

知识点

C/C++中的每个字符串都以字符''作为结尾

为了节省内存，C/C++把常量字符串放到单独的一个内存区域，当几个指针赋值给相同的常量字符串，它们实际会指向相同的地址

    char str1[] = "hello";
    char str2[] = "hello";
    char *str3 = "hello";
    char *str4 = "hello";

char *指向的地址是相同的

数组是分配空间后再将内容拷贝到数组中的，指针直接指向常量字符串

面试题4

本题心得是从尾到头复制可以提高效率，其他字符串问题也可以考虑从尾到头复制

自己开始写的实现写成string[i] = ' '，一定要注意==，另外本题是在原字符串上做替换

书中示例：

 1 /*length 为字符数组string的总容量*/
 2 void ReplaceBlank(char string[], int length)
 3 {
 4     if(string == NULL && length <= 0)
 5         return;
 6 
 7     /*originalLength 为字符串string的实际长度*/
 8     int originalLength = 0;
 9     int numberOfBlank = 0;
10     int i = 0;
11     while(string[i] != '')
12     {
13         ++ originalLength;
14 
15         if(string[i] == ' ')
16             ++ numberOfBlank;
17 
18         ++ i;
19     }
20 
21     /*newLength 为把空格替换成'%20'之后的长度*/
22     int newLength = originalLength + numberOfBlank * 2;
23     if(newLength > length)
24         return;
25 
26     int indexOfOriginal = originalLength;
27     int indexOfNew = newLength;
28     while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
29     {
30         if(string[indexOfOriginal] == ' ')
31         {
32             string[indexOfNew --] = '0';
33             string[indexOfNew --] = '2';
34             string[indexOfNew --] = '%';
35         }
36         else
37         {
38             string[indexOfNew --] = string[indexOfOriginal];
39         }
40 
41         -- indexOfOriginal;
42     }
43 }

完整代码：

  1 // ReplaceBlank.cpp : Defines the entry point for the console application.
  2 //
  3 
  4 // 《剑指Offer——名企面试官精讲典型编程题》代码
  5 // 著作权所有者：何海涛
  6 
  7 #include "stdafx.h"
  8 #include <string>
  9 
 10 /*length 为字符数组string的总容量*/
 11 void ReplaceBlank(char string[], int length)
 12 {
 13     if(string == NULL && length <= 0)
 14         return;
 15 
 16     /*originalLength 为字符串string的实际长度*/
 17     int originalLength = 0;
 18     int numberOfBlank = 0;
 19     int i = 0;
 20     while(string[i] != '')
 21     {
 22         ++ originalLength;
 23 
 24         if(string[i] == ' ')
 25             ++ numberOfBlank;
 26 
 27         ++ i;
 28     }
 29 
 30     /*newLength 为把空格替换成'%20'之后的长度*/
 31     int newLength = originalLength + numberOfBlank * 2;
 32     if(newLength > length)
 33         return;
 34 
 35     int indexOfOriginal = originalLength;
 36     int indexOfNew = newLength;
 37     while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
 38     {
 39         if(string[indexOfOriginal] == ' ')
 40         {
 41             string[indexOfNew --] = '0';
 42             string[indexOfNew --] = '2';
 43             string[indexOfNew --] = '%';
 44         }
 45         else
 46         {
 47             string[indexOfNew --] = string[indexOfOriginal];
 48         }
 49 
 50         -- indexOfOriginal;
 51     }
 52 }
 53 
 54 void Test(char* testName, char string[], int length, char expected[])
 55 {
 56     if(testName != NULL)
 57         printf("%s begins: ", testName);
 58 
 59     ReplaceBlank(string, length);
 60 
 61     if(expected == NULL && string == NULL)
 62         printf("passed.
");
 63     else if(expected == NULL && string != NULL)
 64         printf("failed.
");
 65     else if(strcmp(string, expected) == 0)
 66         printf("passed.
");
 67     else
 68         printf("failed.
");
 69 }
 70 
 71 // 空格在句子中间
 72 void Test1()
 73 {
 74     const int length = 100;
 75 
 76     char string[length] = "hello world";
 77     Test("Test1", string, length, "hello%20world");
 78 }
 79 
 80 // 空格在句子开头
 81 void Test2()
 82 {
 83     const int length = 100;
 84 
 85     char string[length] = " helloworld";
 86     Test("Test2", string, length, "%20helloworld");
 87 }
 88 
 89 // 空格在句子末尾
 90 void Test3()
 91 {
 92     const int length = 100;
 93 
 94     char string[length] = "helloworld ";
 95     Test("Test3", string, length, "helloworld%20");
 96 }
 97 
 98 // 连续有两个空格
 99 void Test4()
100 {
101     const int length = 100;
102 
103     char string[length] = "hello  world";
104     Test("Test4", string, length, "hello%20%20world");
105 }
106 
107 // 传入NULL
108 void Test5()
109 {
110     Test("Test5", NULL, 0, NULL);
111 }
112 
113 // 传入内容为空的字符串
114 void Test6()
115 {
116     const int length = 100;
117 
118     char string[length] = "";
119     Test("Test6", string, length, "");
120 }
121 
122 //传入内容为一个空格的字符串
123 void Test7()
124 {
125     const int length = 100;
126 
127     char string[length] = " ";
128     Test("Test7", string, length, "%20");
129 }
130 
131 // 传入的字符串没有空格
132 void Test8()
133 {
134     const int length = 100;
135 
136     char string[length] = "helloworld";
137     Test("Test8", string, length, "helloworld");
138 }
139 
140 // 传入的字符串全是空格
141 void Test9()
142 {
143     const int length = 100;
144 
145     char string[length] = "   ";
146     Test("Test9", string, length, "%20%20%20");
147 }
148 
149 int _tmain(int argc, _TCHAR* argv[])
150 {
151     Test1();
152     Test2();
153     Test3();
154     Test4();
155     Test5();
156     Test6();
157     Test7();
158     Test8();
159     Test9();
160 
161     return 0;
162 }

View Code