一.题目描述

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。例如"We are happy."替换为"We%20are%20happy.

算法一：

==算法1:从头到尾遍历,遇到空格把它替换为%20.时间O(n^2),空间O(1) ==

void replaceSpace(char* s)//假定str空间足够,注意力扣需要自己重新定义内存存放新s
{for (int i = 0; s[i] != '\0'; i++){if (s[i] == ' ')//空格{//把i后面的数据后移两个格子(' '变为%20,一个字符变三个字符)for (int j = strlen(s); j > i; j--)s[j + 2] = s[j];//填充%20s[i++] = '%';s[i++] = '2';s[i] = '0';}}
}int main()
{char s[100] = "We are happy.";replaceSpace(s);printf("%s\n", s);return 0;
}

算法二

算法2.重新创建一个新数据用于存放替换后的字符串,时间O(n),空间O(n)

void replaceSpace(char* s)//假定str空间足够,注意力扣需要自己重新定义内存存放新s
{int count = 0;//统计空格的数量int i;for (i = 0; s[i] != '\0'; i++){if (s[i] == ' ')count++;}char* str = (char*)malloc(sizeof(char) * (strlen(s) + 1 + 2 * count));int j = 0;//str下标for (i = 0; s[i] != '\0'; i++){if (s[i] != ' ')str[j++] = s[i];else//空格,需要替换{str[j++] = '%';str[j++] = '2';str[j++] = '0';}}str[j] = '\0';//str为字符串strcpy(s,str);//将str的内容拷贝到s中free(str);
}int main()
{char s[100] = "We are happy.";replaceSpace(s);printf("%s\n", s);return 0;
}

算法3

算法3.统计字符串中空格数量,计算需要后移的字符数,然后从后往前遍历字符串,直接替换.O(n),O(1)

void replaceSpace(char* s)
{int count = 0;int i;for (i = 0; s[i] != '\0'; i++)//统计空格的数量{if (s[i] == ' ')   count++;   }int j = i+count * 2;//移动后的下标   for (; i >= 0; i--)   {if(s[i]!=' ')//不是空格,直接后移   s[j--] = s[i];   else //空格   {s[j--] = '0';   s[j--] = '2';   s[j--] = '%';    }}
}int main()   
{char s[100] = "We are happy.";   replaceSpace(s);   printf("%s\n", s);   return 0;   
}

本篇完！