题:实现一个函数,把字符串中的每个空格替换成”%20”。例如:”We are family.”,则输出 “We%20are%20family.”。

扩展:

在网络编程中,如果URL参数中含有特殊字符,如空格、’#’等,则可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转成服务器可以识别的字符。转换的规则是在’%’后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32,即十六进制的0x20,因此空格被替换成’%20’;再比如’#’的ASCII码为35,即十六进制的0x23,它在URL中被替换为’%23’。

分析:

这题的规则很简单,将空格替换成’%20’,那么需要考虑的就是时间复杂度的问题。

思路:

方法一:

最简单的想法是:直接遍历字符串中的字符,遇到空格便将其替换成’%20’,但有一些问题,空格的长度和’%20’的长度是不等的,那么结果是需要将每个空格后面的字符向后移动。举个例子:如果字符串的长度为n,对每个空格字符,需要移动后面的O(n)个字符,因此对于含有O(n)个空格字符的字符串而言,总的时间复杂度为:O(n^2)。

方法二:

使用辅助空间,遍历字符串的每个字符,将其添加到辅助字符串中,添加的过程中将空格替换成’%20’。这种方法是牺牲空复杂度间换取时间复杂度。时间复杂度为:O(n)。

方法三:

先遍历一遍字符串,找出其中的空格,确定替换后的字符转的长度。然后从字符串的后面开始复制和替换。首先准备两个指针:P1和P2。P1指向原始字符串的末尾,P2则指向替换之后的字符串的末尾。实现步骤:做好之前的准备后,向前移动指针P1,诸葛把它指向的字符复制到P2指向的位置,直到碰到第一个空格为止。时间复杂度为:O(n)。

代码实践:

方法一实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
char string[1000] = "We are family.";
int stringlen = strlen(string);
int indexNum = 0;

for(int i = 0; i < stringlen; i++){
char charStr = string[i];
if (charStr == ' ') {
int count = 0;
//将空格之后的字符向后移动
for (int j = stringlen;j > i; j--) {
string[j+2] = string[j];
count++;
}
string[++indexNum] = '%';
string[++indexNum] = '2';
string[++indexNum] = '0';

i = i+2;
}else {
indexNum = i;
}

}

printf("\n-----one3 %s\n",string);

方法二实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
char str[] = "We are family.";
int strLen = strlen(str);

//这段代码是用来计算辅助字符串的长度的;
char replaceStr[] = "%20";
//统计空格的数目
int bankNumber = 0;

for(int i = 0; i < strLen; i++){
char charStr = str[i];
if (charStr == ' ') {
bankNumber++;
}
}

int replacelen = bankNumber * (strlen(replaceStr)-1);
int repStrNewlen = strLen + replacelen;

//根据计算的字符串长度,创建辅助字符串
char newStr[repStrNewlen] ;

//将str中的字符复制到辅助字符串中,并将空格替换为'%20'
int index = 0;
int num = 0;
while (strLen > 0 && num <= strLen) {
char charS = str[num];
if (charS == ' ') {
newStr[index++] = '%';
newStr[index++] = '2';
newStr[index++] = '0';

}else {
newStr[index++] = charS;
}
++num;
}

printf("--------one2Result == %s",newStr);

方法三实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
char string[] = "We are family.";

//统计空格的数目
int bankNumber = 0;
char replaceStr[] = "%20";
int stringlen = strlen(string);
for(int i = 0; i < stringlen; i++){
char charStr = string[i];
if (charStr == ' ') {
bankNumber++;
}
}
//替换字符增加的长度
int replacelen = bankNumber * (strlen(replaceStr)-1);
//替换后的字符串长度
int repStrNewlen = stringlen + replacelen;

while (stringlen >= 0 && stringlen < repStrNewlen) {
char char1 = string[stringlen];
if (char1 == ' ') {
string[repStrNewlen--] = '0';
string[repStrNewlen--] = '2';
string[repStrNewlen--] = '%';
bankNumber--;
}else {
string[repStrNewlen--] = char1;
}

--stringlen;
}

printf("result==%s \n",string);