一.概述：
面试题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 }
|
本文转自 ye小灰灰 51CTO博客，原文链接：http://blog.51cto.com/10704527/1783630，如需转载请自行联系原作者
