替换空格
思路
方法一（暴力解法）：
- 由于题目给了我们字符串长度的最大值，那我们可以直接创建一个大小为原字符串大小三倍的字符数组（如果原字符串全为空格），接着遍历原字符串，如果不是空格就将字符存入新数组，如果是空格就将“%20”这三个字符存入新数组
方法二：
- 如果我们想将这道题做到极致：不额外消耗内存，不重新申请新的数组并且将时间复杂度控制在O(n)，那这题就值得我们思考了
- 不额外消耗内存，也就是说我们在填充空格之前就要直到填充后数组的大小，这个好办，我们可以先遍历原数组，记录空格的总个数count，那么填充后数组的大小就是： 原数组的大小 + count * 2。
- 要做到不申请新的数组，那我们就需要改变原数组的大小，这时就需要利用realloc函数来实现
int len = strlen(s); //s为原字符串 int newlen = len + count * 2; s = (char *)realloc(s,sizeof(char) * newlen + 1); //之所以要加一，因为最后要在字符数组s最后加上结束符'\0'
- 那么我们怎么确保时间复杂度为O(n)呢？
- 如果我们跟方法一一样从前往后遍历字符串，碰到空格就填入“%20”，那么我们就要不断移动后面的所有元素，可想而知，这样的时间复杂度为O(n2)。
- 因此我们应该从后往前填入字符
for(int i = len - 1, j = newlen - 1; i >= 0, j >= 0; i--, j--) { if(s[i] != ' ') s[j] = s[i]; else { //从后往前，逆序填入 s[j--] = '0'; s[j--] = '2'; s[j] = '%'; } }
实现代码
方法一
char* replaceSpace(char* s){ static char str[30000]; //注意加上static修饰符 int j = 0; for(int 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'; return str; }
方法二
char* replaceSpace(char* s){ int count = 0; int len = strlen(s); int newlen = 0; for(int i = 0; i < len - 1; i++) if(s[i] == ' ') count++; newlen = strlen(s) + 2 * count; s = (char *)realloc(s,sizeof(char) * newlen + 1); //之所以要加一，因为最后要在字符数组s最后加上结束符'\0' for(int i = len - 1, j = newlen - 1; i >= 0, j >= 0; i--, j--) { if(s[i] != ' ') s[j] = s[i]; else { //从后往前，逆序填入 s[j--] = '0'; s[j--] = '2'; s[j] = '%'; } } s[newlen] = '\0'; //在字符串末尾加上结束符'\0' return s; }
tips
在方法一中定义新字符串数组时，static修饰符必须加上，否则系统会提示错误，这涉及到栈帧的知识，笔者目前还在学习中，其中原理还未摸透，故以后再和大家分享。
