面试题 4 ：替换空格

2019-11-06 06:02:44

字体：大中小

来源：转载

供稿：网友

题目：请实现一个函数，把字符串中的每个空格替换成”%20”。例如：输入”we are happy.”，则输出”we%20are%20happy.”

思路分析：我们比较替换之前与替换之后的字符串长度，很明显，字符串长度增加了4，所以，第一点，将”we are happy.”用一个字符指针指向肯定不可行，那么就应该将其放入一个数组中。其次我们就应该考虑如何输出想要的结果。 1.题目没有给出要求，那么有一种笨的办法就是将字符串逐渐赋值到另外一个数组中，遇到空格就给新的数组插入”%20”，这样也可以输出结果。这样的时间复杂度和空间复杂度都是O(N)。但是想一想，这是一道面试题啊，怎么可能如此简单。 2.利用两个数组的做法显然被pass掉了，那只能在一个数组内操作了。既然数组长度扩大了，我们可以想成每个空格后边的字符都向后移动了一定的位置，空出来的位置刚好够插入”%20”。我们画张图来解释一下：这里写图片描述

上边这种方法的时间复杂度还不是让人最满意的，应该有一种最好的办法既能让时间复杂度降低还能达到预期目标。如果我们每次能将移动的字符一次性放好位置，那样就比较方便了。因此我么需要提前知道增加长度后数组的大小，那么我们就能给出两个下标，一个指向新字符串的末尾，一个指向旧字符串的末尾，从后向前遍历一边，就能实现每次都将字符一次性放好位置。这里写图片描述时间复杂度分析：由于从后往前只需要遍历一次数组，其时间复杂度为O(N) 代码：

#include <stdio.h>#include <stdlib.h>#include <assert.h>#include <string.h>//时间复杂度：O(N)void Replace(char* str,int old) { char* start = str; int blacknum = 0; int newlen = 0; int PRev = 0; int last = 0; if ((str == NULL) || (old < 0)) { return ; } while (*start != '/0') { start++; if (*start == ' ') { blacknum++; //统计空格的个数 } } newlen = old+blacknum*2; //替换后新的字符串长度 prev = old; last = newlen; while (prev >= 0) { str[last--] = str[prev--]; if (str[prev] == ' ') { str[last--] = '0'; str[last--] = '2'; str[last--] = '%'; prev--; } }}

底下为测试代码：

int main(){ char str[] = "we are happy"; int len = strlen(str); Replace(str,len); printf("%s/n",str); system("pause"); return 0;}

上一篇：第二次修改状态机源码

下一篇：CodeForces - 149D Coloring Brackets 详细题解（递归区间DP+dfs染色，好题）