剑指offer2_空格替换

tags:

• 字符数组
• 替换

题目描述

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

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M

题目链接：剑指offer2 空格替换

C++解题

思路1：从前向后替换

代码如下：

class Solution 
{
public:
    void replaceSpace1(char *str, int length)
    {
        int cnt_length = 0;
        int cnt_space = 0;
        for (int i = 0; str[i] != '\0'; ++i) // char* 类型的字符数组结束符为'\0'
        {
            cnt_length++;
            if (str[i] == ' ')
                cnt_space++;
        }
        // 此时cnt_length长度不包括'\0'这一位,但大小与总体长度相同
        int new_length = cnt_length + cnt_space * 2;
        if (new_length + 1 >= length)
            return;
        for (int i = 0; i < new_length + 1; ++i)
        {
            if (str[i] == ' ')
            {
                for (int j = length; j != i; --j)//注意这里j的范围，如果定义为
                {
                    if (str[j] != '\0')
                        str[j + 2] = str[j];
                }
                str[i] = '%';
                str[i + 1] = '2';
                str[i + 2] = '0';
                i = i + 2;
            }
        }
        str[new_length] = '\0';
        return;
    }
};

复杂度分析：从前向后遍历的同时需要从后向前挪，复杂度为

思路2：从后向前替换

代码如下：

class Solution 
{
public:
    void replaceSpace2(char *str, int length)
    {
        int cnt_space = 0;
        for (int i = 0; str[i] != '\0'; ++i) // char* 类型的字符数组结束符为'\0'
        {
            if (str[i] == ' ')
                cnt_space++;
        }
        for (int i = length - 1; i >= 0; i--)
        {
            if (str[i] != ' ')
            {
                str[i + cnt_space * 2] = str[i];
            }
            if (str[i] == ' ')
            {
                str[i + cnt_space * 2] = '0';
                str[i + cnt_space * 2 - 1] = '2';
                str[i + cnt_space * 2 - 2] = '%';
                cnt_space--;
            }
        }
        return;
    }
};

复杂度分析：从后向前查找，挪动时是前方空格个数的2倍距离，复杂度为

知识点总结

1. C++ 字符数组的创建，以及结构（末尾'\0'）
2. 数组替换是应从后向前，防止数据被污染