面试题 4 :替换空格

3/8/2017来源:ASP.NET技巧人气:1975

题目:请实现一个函数,把字符串中的每个空格替换成”%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; }