分享程序员开发的那些事...
更新时间：2022-10-04 15:18:35
一.概述：
面试题4：替换空格
题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，则输出“We%20are%20happy.”。
在网络编程中，如果URL参数中含有特殊字符，如空格、'#'等，可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在'%'后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32，即十六进制的0x20，因此空格被替换成"%20"。再比如'#'的ASCII码为35，即十六进制的0x23，它在URL中被替换为"%23"。
看到这个题目，我们首先应该想到的是原来一个空格字符，替换之后变成'%'、'2'和'0'这3个字符，因此字符串会变长。如果是在原来的字符串上做替换，那么就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上做替换，那么我们可以自己分配足够多的内存。由于有两种不同的解决方案，我们应该向面试官问清楚，让他明确告诉我们他的需求。假设面试官让我们在原来的字符串上做替换，并且保证输入的字符串后面有足够多的空余内存。
二.解法一：时间复杂度为O（n^2）
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
1 /****************************************
2 > File Name:test.c
3 > Author:xiaoxiaohui
4 > mail:1924224891@qq.com
5 > Created Time:2016年05月13日 星期五 11时44分28秒
6 ****************************************/
7
8 #include<stdio.h>
9
10 void ReplaceBlank(char* src)
11 {
12 if(src == NULL)
13 {
14 return;
15 }
16 int length = 0; //src的长度
17 int newLength = 0; //改变空格之后的长度
18 int count = 0; //空格的个数
19 char* left = src;
20 char* right = NULL;
21
22 while(*left != '\0')
23 {
24 length++;
25 if(*left == ' ')
26 {
27 count++;
28 }
29 left++;
30 }
31
32 newLength = length + 2*count + 1;
33 right = src + (newLength - 1);
34 left = src + length - 2;
35
36 while(left != right)
37 {
38 while(*left != ' ')
39 {
40 *right = *left;
41 // left--;
42 // right--;
43 }
44
45 left--;
46
47 *right = '0';
48 right--;
49 *right = '2';
50 right--;
51 *right = '%';
52 right--;
53 }
54
55 printf("%s", src);
56 }
57
58
|
三.解法二：时间复杂度为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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
1 /****************************************
2 > File Name:test1.c
3 > Author:xiaoxiaohui
4 > mail:1924224891@qq.com
5 > Created Time:2016年05月13日 星期五 10时49分14秒
6 ****************************************/
7
8 #include<stdio.h>
9 #include<string.h>
10
11 void change(char* src)
12 {
13 char* start = src;
14 char* end = src;
15 int count = 0;
16 while(*start != '\0')
17 {
18 while(*start != ' ' && *start != '\0')
19 {
20 start++;
21 }
22
23 end = start;
24 while(*end == ' ' && *end != '\0')
25 {
26 count++;
27 end++;
28 }
29
30 while(count--)
31 {
32 strncat(start, "%20", 3);
33 start += 3;
34 }
35
36 strcat(start,end);
37 }
38 printf("%s", src);
39 }
40
41 int main()
42 {
43 char* str = "we are happy";
44 change(str);
45 }
|