Fork me on GitHub

算法(替换空格)

题目

请实现一个函数,把字符串中的每个空格替换成”%20”。例如输入“we are happy”,则输出“we%20are%20happy”,并且时间复杂度为O(n)

分析

第一种思路

首先看题目,替换的话很简单。从头开始遍历遇到空格就替换成”%20”,但是此时其他的字符串则要后移。如下图
WechatIMG35.jpeg

这样的话也能实现替换的功能,但是时间复杂度为O(n2),显然这点不符合我们的要求。

第二种思路

我们前边的思路是从前往后移动,时间复杂度为O(n2),但是如果我们从后往前移动呢?
image.png
相当于一前一后指针,指针p1和p2同时往前移动,并且将p1的内容复制到p2的位置上,遇到空格则p1停下,p2开始填充”%20”这三个字符,然后p2往前移动3个单位,此时p1、p2再次开始同时往前移动

代码

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
int findSpace(char string[]);
void replacewhiteSpace(char string[],int length){
int countSpace = findSpace(string);
int originLength = length;
int replacedLength = originLength-countSpace+countSpace*3;
int originIndex = originLength-1;
int replacedIndex = replacedLength-1;
string[replacedLength]='\0';
while (originIndex>0) {
if (string[originIndex]==' ') {
string[replacedIndex]='0';
string[replacedIndex-1]='2';
string[replacedIndex-2]='%';
replacedIndex = replacedIndex-3;
}else{
string[replacedIndex]=string[originIndex];
--replacedIndex;
}
--originIndex;
}
}
int findSpace(char string[]){
int i = 0;
int count = 0;
while (string[i]!='\0') {
if (string[i] == ' ') {
count++;
}
i++;
}
return count;
}
//******* 测试数据 *********
//char string[] = "we are happy";
//replacewhiteSpace(string,sizeof(string)/sizeof(string[0]));
0%