剑指offer2：C++实现的替换空格(字符中的空格替换为“%20”)

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

1. 题目描述

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

2. 思路和方法：

2.1 建议使用的方法：

中心思想：统计字符串中空格的个数，计算扩容字符串后的长度，然后执行复制和替换。我们从后往前开始替换，首先遍历一遍字符串，统计出空格的个数，并由此能够计算出替换之后的字符串的长度。接着再次从后往前遍历字符串，同时设置两个指针P1和P2，P1指向原始字符串末尾，P2指向替换之后的字符串末尾。我们向前移动P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。然后把P1向前移动一格，在P2之前插入字符串“%20”，同时P2向前移动3格。重复此过程，直到所有的空格都已替换完。这种做法的时间复杂度为O(n)。

2.2 不建议的方法：

简单暴力解法，从头到尾遍历字符串，碰到空格，首先将后面的所有字符串往后移动2个字符，才能空出3个字符位子插入字符“%20”，对于一个长度为n的字符串，对每个空格，需要移动后面O(n)个字符，因此包含n个空格的字符串，总的时间复杂度为O(n*n)。

3. C++实现

#include<iostream>
/*
将字符串中的空格替换成%20
*/
class Solution {
public:
void replaceSpace(char *str, int length) {
if (str == NULL && length <= ){
return;
}
/*original_length为字符串str的实际长度*/
int original_length = ; //原始长度
int number_blank = ; //空格数
int i=;
while (str[i++] != '\0'){ //遍历字符串
++original_length; //长度+1
if (str[i] == ' '){
++number_blank; //遇到空格+1
}
}
/*new_length为把空格替换成'%20'之后的长度*/
int new_length = original_length + * number_blank; int index_original = original_length; //原始字符串末尾索引值
int index_new = new_length; //计算长度后的字符串末尾索引值 /*index_original指针开始向前移动，如果遇到空格，替换成'%20'，否则进行复制操作*/
while (index_original >= && index_new > index_original){
if (str[index_original] == ' '){
str[index_new--] = '';
str[index_new--] = '';
str[index_new--] = '%';
}
else{
str[index_new--] = str[index_original];
}
--index_original;
}
}
};int main(){
Solution a;
char s[] = "hello world! ";
printf("%s\n", s);
a.replaceSpace(s, );
printf("?%s? ", s);
getchar();
return ;
}