题目:请实现一个函数,把字符串中的每个空格替换成“%20”。例如输入“We are happy.”,则输出“We%20are%20happy.”。
看到这个题目,我们首先应该想到的是原来一个空格字符,替换之后变成'%'、'2'和'0'这3个字符,因此字符串会变长。如果是在原来的字符串上做替换,那么就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上做替换,那么我们可以自己分配足够多的内存。
在这里介绍一种时间复杂度为O(n)的解法。
我们可以先遍历一次字符串,这样就能统计出字符串中空格的总数,并可以由此计算出替换之后的字符串的总长度。每替换一个空格,长度增加2,因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。我们以字符串"We are happy."为例,"We are happy."这个字符串的长度是14(包括结尾符号'\0'),里面有两个空格,因此替换之后字符串的长度是18。
我们从字符串的后面开始复制和替换。首先准备两个指针,P1和P2。P1指向原始字符串的末尾,而P2指向替换之后的字符串的末尾(如图(a)所示)。接下来我们向前移动指针P1,逐个把它指向的字符复制到P2指向的位置,直到碰到第一个空格为止。此时字符串包含如图(b)所示,灰色背景的区域是做了字符拷贝(移动)的区域。碰到第一个空格之后,把P1向前移动1格,在P2之前插入字符串"%20"。由于"%20"的长度为3,同时也要把P2向前移动3格如图(c)所示。
我们接着向前复制,直到碰到第二个空格(如图(d)所示)。和上一次一样,我们再把P1向前移动1格,并把P2向前移动3格插入"%20"(如图(e)所示)。此时P1和P2指向同一位置,表明所有空格都已经替换完毕。
注:图中带有阴影的区域表示被移动的字符。(a)把第一个指针指向字符串的末尾,把第二个指针指向替换之后的字符串的末尾。(b)依次复制字符串的内容,直至第一个指针碰到第一个空格。(c)把第一个空格替换成'%20',把第一个指针向前移动1格,把第二个指针向前移动3格。(d)依次向前复制字符串中的字符,直至碰到空格。(e)替换字符串中的倒数第二个空格,把第一个指针向前移动1格,把第二个指针向前移动3格。
参考代码:
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] != '\0')
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 #include<iostream>
2 #include<string.h>
3 using namespace std;
4
5 /*length 为字符数组string的总容量*/
6 void ReplaceBlank(char string[], int length)
7 {
8 if(string == NULL && length <= 0)
9 return;
10
11 /*originalLength 为字符串string的实际长度*/
12 int originalLength = 0;
13 int numberOfBlank = 0;
14 int i = 0;
15 while(string[i] != '\0')
16 {
17 ++ originalLength;
18
19 if(string[i] == ' ')
20 ++ numberOfBlank;
21
22 ++ i;
23 }
24
25 /*newLength 为把空格替换成'%20'之后的长度*/
26 int newLength = originalLength + numberOfBlank * 2;
27 if(newLength > length)
28 return;
29
30 int indexOfOriginal = originalLength;
31 int indexOfNew = newLength;
32 while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
33 {
34 if(string[indexOfOriginal] == ' ')
35 {
36 string[indexOfNew --] = '0';
37 string[indexOfNew --] = '2';
38 string[indexOfNew --] = '%';
39 }
40 else
41 {
42 string[indexOfNew --] = string[indexOfOriginal];
43 }
44
45 -- indexOfOriginal;
46 }
47 }
48
49 int main()
50 {
51 const int length = 100;
52
53 char string[length] = "hello world.";
54
55 ReplaceBlank(string, length);
56
57 int newLength = strlen(string);
58 /*
59 int newLength = 0;
60 int j = 0;
61 while(string[j] != '\0')
62 {
63 newLength++;
64 ++j;
65 }
66 */
67 for(int i = 0 ; i < newLength ; ++i)
68 cout<<string[i];
69 cout<<endl;
70
71 return 0;
72 }
测试代码:
#include <stdio.h>
#include <string>
/*length 为字符数组string的总容量*/
void ReplaceBlank(char string[], int length)
{
if(string == NULL && length <= 0)
return;
/*originalLength 为字符串string的实际长度*/
int originalLength = 0;
int numberOfBlank = 0;
int i = 0;
while(string[i] != '\0')
{
++ originalLength;
if(string[i] == ' ')
++ numberOfBlank;
++ i;
}
/*newLength 为把空格替换成'%20'之后的长度*/
int newLength = originalLength + numberOfBlank * 2;
if(newLength > length)
return;
int indexOfOriginal = originalLength;
int indexOfNew = newLength;
while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
{
if(string[indexOfOriginal] == ' ')
{
string[indexOfNew --] = '0';
string[indexOfNew --] = '2';
string[indexOfNew --] = '%';
}
else
{
string[indexOfNew --] = string[indexOfOriginal];
}
-- indexOfOriginal;
}
}
void Test(char* testName, char string[], int length, char expected[])
{
if(testName != NULL)
printf("%s begins: ", testName);
ReplaceBlank(string, length);
if(expected == NULL && string == NULL)
printf("passed.\n");
else if(expected == NULL && string != NULL)
printf("failed.\n");
else if(strcmp(string, expected) == 0)
printf("passed.\n");
else
printf("failed.\n");
}
// 空格在句子中间
void Test1()
{
const int length = 100;
char string[length] = "hello world";
Test("Test1", string, length, "hello%20world");
}
// 空格在句子开头
void Test2()
{
const int length = 100;
char string[length] = " helloworld";
Test("Test2", string, length, "%20helloworld");
}
// 空格在句子末尾
void Test3()
{
const int length = 100;
char string[length] = "helloworld ";
Test("Test3", string, length, "helloworld%20");
}
// 连续有两个空格
void Test4()
{
const int length = 100;
char string[length] = "hello world";
Test("Test4", string, length, "hello%20%20world");
}
// 传入NULL
void Test5()
{
Test("Test5", NULL, 0, NULL);
}
// 传入内容为空的字符串
void Test6()
{
const int length = 100;
char string[length] = "";
Test("Test6", string, length, "");
}
//传入内容为一个空格的字符串
void Test7()
{
const int length = 100;
char string[length] = " ";
Test("Test7", string, length, "%20");
}
// 传入的字符串没有空格
void Test8()
{
const int length = 100;
char string[length] = "helloworld";
Test("Test8", string, length, "helloworld");
}
// 传入的字符串全是空格
void Test9()
{
const int length = 100;
char string[length] = " ";
Test("Test9", string, length, "%20%20%20");
}
int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
Test7();
Test8();
Test9();
return 0;
}
延伸题目:归并两个已经排序的数组。
题目:有两个排序的数组A1和A2,内存在A1的末尾有足够多的空余空间容纳A2。请实现一个函数,把A2中所有的数字插入到A1中并且所有的数字是排序的。
void mergaMatrix(int* matrix1,int* matrix2,
int lenofmtrx1,int lenofmtrx2,int sizeofmatrix1)
{
if(sizeofmatrix1 != 0 && matrix1 != NULL && lenofmtrx1 !=0
&& matrix2 != NULL && lenofmtrx2 != 0 )
{
int* pNewMatrix1 = matrix1 + lenofmtrx1 + lenofmtrx2 -1;
int* pMatrix1 = matrix1 + lenofmtrx1 - 1;
int* pMatrix2 = matrix2 +lenofmtrx2 - 1;
while(pMatrix1 >= matrix1 && pMatrix2 >= matrix2)
{
if(*pMatrix1 >= *pMatrix2)
*pNewMatrix1-- = *pMatrix1--;
else
*pNewMatrix1-- = *pMatrix2--;
}
while(pMatrix1 >= matrix1)
{
*pNewMatrix1-- = *pMatrix1--;
}
while(pMatrix2 >= matrix2)
{
*pNewMatrix1-- = *pMatrix2--;
}
}
return;
}
测试代码:
//合并数组
#include <stdio.h>
void mergaMatrix(int* matrix1,int* matrix2,
int lenofmtrx1,int lenofmtrx2,int sizeofmatrix1)
{
if(sizeofmatrix1 != 0 && matrix1 != NULL && lenofmtrx1 !=0
&& matrix2 != NULL && lenofmtrx2 != 0 )
{
int* pNewMatrix1 = matrix1 + lenofmtrx1 + lenofmtrx2 -1;
int* pMatrix1 = matrix1 + lenofmtrx1 - 1;
int* pMatrix2 = matrix2 +lenofmtrx2 - 1;
while(pMatrix1 >= matrix1 && pMatrix2 >= matrix2)
{
if(*pMatrix1 >= *pMatrix2)
*pNewMatrix1-- = *pMatrix1--;
else
*pNewMatrix1-- = *pMatrix2--;
}
while(pMatrix1 >= matrix1)
{
*pNewMatrix1-- = *pMatrix1--;
}
while(pMatrix2 >= matrix2)
{
*pNewMatrix1-- = *pMatrix2--;
}
}
return;
}
//单元测试
void test(int* matrix1,int* matrix2,
int lenofmtrx1,int lenofmtrx2,int sizeofmatrix1)
{
if(matrix1 != NULL)
{
for( int i=0; i<lenofmtrx1;i++)
{
printf("%d ",*(matrix1+i));
}
}
printf("\n");
if(matrix2 != NULL){
for( int i=0; i<lenofmtrx2;i++)
{
printf("%d ",*(matrix2+i));
}
}
printf("\n");
mergaMatrix(matrix1,matrix2,lenofmtrx1,lenofmtrx2,sizeofmatrix1);
for( int i=0; i<lenofmtrx1+lenofmtrx2;i++)
{
printf("%d ",*(matrix1+i));
}
printf("\n");
}
//一般情况
void test1()
{
const int sizeofmatrix1 = 100;
int lenofmtrx1 = 3;
int matrix1[sizeofmatrix1] = {1,3,5};
int lenofmtrx2 = 4;
int matrix2[] = {2,4,6,8};
test(matrix1,matrix2,lenofmtrx1,lenofmtrx2,sizeofmatrix1);
}
//其中一个数组的书全部小于另外一个
void test2()
{
const int sizeofmatrix1 = 100;
int lenofmtrx1 = 3;
int matrix1[sizeofmatrix1] = {1,3,5};
int lenofmtrx2 = 4;
int matrix2[] = {6,7,8,9};
test(matrix1,matrix2,lenofmtrx1,lenofmtrx2,sizeofmatrix1);
}
//其中一个为空
void test3()
{
const int sizeofmatrix1 = 100;
int lenofmtrx1 = 3;
int matrix1[sizeofmatrix1] = {1,3,5};
test(matrix1,NULL,lenofmtrx1,0,sizeofmatrix1);
}
//两个都为空
void test4()
{
const int sizeofmatrix1 = 100;
test(NULL,NULL,0,0,sizeofmatrix1);
}
int main()
{
test1();
test2();
test3();
test4();
return 0;
}