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倍距离，复杂度为
知识点总结
- C++ 字符数组的创建，以及结构（末尾'\0'）
- 数组替换是应从后向前，防止数据被污染
