Biegral Blog

题目：请实现一个函数，把字符串中的每个空格替换成”%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)  //这里不能为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;
}