替换空格
首先,拿到题目,我们可以遍历整个字符串,遇到空格用%20替换,只不过字符串的长度就会增加;我们也可以创建新的字符串在新的字符串上替换,那么我们就应该有足够多的空间。
第一种解法:(时间复杂度为O(n^2))
假设字符串的长度为n,对于每个空格字符,都需要将后边的往后移动,如果有n个空格,那么时间复杂度为O(n^2);
第二种解法:(时间复杂度为O(n))
就以题目中的“we are happy.”为例子,新的字符串的长度为空格数*2+原长度,创建两个指针,一个指向新的,一个指向原长度,在遇到‘ ’之前,让后一个指针的内容等于前一个指针的内容,如图:
参考代码:
void replace(char a[],int length)//注意边界值
{
if (a == NULL || length <= 0)
{
return;
}
int alllength = 0;
int spacenum = 0;
int i = 0;
for (i = 0; i < length; i++)
{
if (a[i] == ' ')
spacenum++;//空格数
}
alllength = length + spacenum * 2;//新的字符串长度
while (length >= 0 && length < alllength)
{
if (a[length] == ' ')
{
a[alllength--] = '0';
a[alllength--] = '2';
a[alllength--] = '%';
}
else
a[alllength--] = a[length];
length--;
}
}
int main()//替换空格
{
char a[64] = "we are happy.";
int i = 0;
int length1,length = strlen(a);
for (i = 0; i < length; i++)
{
printf("%c", a[i]);
}
printf("\n");
replace(a,length);
length1 = strlen(a);
for (i = 0; i < length1; i++)
{
printf("%c", a[i]);
}
system("pause");
return 0;
}
运行结果: