剑指offer-4-替换空格

问题

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

方案

该问题如果采用暴力方法：从前往后遍历，如果遇到空格，开始整体数据向后移动2位，插入%20，一直到结束。采用这样的方法，时间复杂度为 O ( n 2 ) O(n^2) O(n2)，比较耗时间，也不是理想的方案。

上面的方案，可以看出有很大的改进空间，如果知道了空格的个数，直接从后往前遍历，这样每个元素都能放到最终位置，而不是向暴力方法那样移动很多步。即：从前往后进行遍历，找到字符串中空格的个数，然后从后往前遍历，放入最终位置。

代码：

#include <iostream>
#include <stdio.h>

using namespace std;

void replaceSpace(char *str, int length)
{
    if (str == NULL || length <= 0)
        return;

    int cnt = 0;
    int str_len = 0;

    //下面两种都是对str进行遍历，都可以

    //    char *p = str;
    //    while (*p != '\0') {
    //        ++str_len;
    //        if (*p == ' ')
    //            cnt++;
    //
    //        ++p;
    //    }

    for (int i = 0; str[i] != NULL; i++)
    {
        ++str_len;
        if (str[i] == ' ')
            cnt++;
    }

    if (str_len + cnt * 2 > length)
        return;

    //length += cnt;
    int new_len = str_len + cnt * 2;
    str[new_len + 1] = '\0';
    for (int i = new_len; i >= 0 && cnt > 0; --i)
    {
        if (str[str_len] != ' ')
        {
            str[i] = str[str_len];
        }
        else
        {
            str[i--] = '0';
            str[i--] = '2';
            str[i] = '%';
            cnt--;
        }

        --str_len;
    }
}

int main(int argc, char *argv[])
{
    char str[] = "we are happy";

    replaceSpace(str, 100);

    printf("%s\n", str);

    return 0;
}

其他：
本来很简单的题目，但自己没有设置好边界条件，加上写的过程中有几个小bug，调试了一会儿才发现问题，耗时1h才完全解决。太久不写代码的锅？

写作中遇到的几个bug：

1. str[new_len] = '\0'; 总长度是怎么回事没想清楚
2. for (int i = new_len -1; i >= 0 && cnt >= 0; --i) 这里还是对添加后的数组是怎样的情况不清晰，同时cnt这里的判断应该是cnt>0，不然设置这样的判断没任何效果。
3. str[i] = str[str_len -- ]; 这里只有在if中str_len才-1，导致程序崩了。。。

几个点：边界条件这些应该在开始之前就想清楚，而不是写好后再找bug。此时这些bug潜藏得比较深，不容易发现。