剑指offer(c++)-03.替换空格
替换空格
1. 前景知识：
字符串是由若干字符组成的序列。由于字符串在编程时使用的频率非常高，为了优化，很多语言都对字符串做了特殊的规定。
C/C++ 中每个字符串都以字符’\0’作为结尾，这样我们就能很方便地找到字符串的最后尾部。但由于这个特点，每个字符串中都有一个额外字符的开销，稍不留神就会造成字符串的越界。
// 如下代码： char str[10]; strcpy(str,"0123456789")` //若复制到str中其实需要11个字节，因为字符有10个，但是末尾还有‘\0’ ```
为了节省内存，C/C++把常量字符串放到单独的一个内存区域。当几个指针赋值给相同的常量字符串时，它们实际上会指向相同的内存地址。
2. 出题缘由（摘自：剑指offer）:
在网络编程中，如果URL参数中含有特殊字符，如空格、’#‘等，可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在’%‘后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32，即十六进制的0x20，因此空格被替换成"%20"。再比如’#'的ASCII码为35，即十六进制的0x23，它在URL中被替换为"%23"。
3. 题目：
请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，则输出“We%20are%20happy.”。
解题思想：
- 遍历一遍字符串，统计出空格的个数num_Blank，( 遍历条件str[i] != ‘\0’ )
- 得到空格个数num_Blank，即可知替换为“%20”后的新字符串长度(不包含结束符‘\0’) = 空格个数*2 + length-1
- 准备双指针，P1、P2，P1指向原字符串长度最后一个字符即str[length -1]，P2指向扩充后字符串末尾即str[length-1 + num_Blank*2]
- 遍历原字符串，当不是空格时，将字符复制到后面。
- 当出现空格时，将’0’,‘2’,’%'依次复制到扩充后的字符串中
- 复制完毕后，空格数量-1，即num_Blank-1。
遍历过程如下图（图片来自于剑指offer）
算法复杂度（时间O(N) 空间O(1)）
解法：
class Solution {
public:
// str:输入字符串
// length:字符串总容量
void replaceSpace(char *str,int length) {
int num_Blank = 0;
for(int i = 0; str[i] != '\0'; i++){
if (str[i] == ' ') num_Blank++;
}
for(int i = length-1; i >= 0; i--){
if(str[i] != ' ') {
// 新字符串长 = 空字符串*2 + 原字符串-1 = num_Blank*2 + i
str[i + num_Blank*2] = str[i];
}
else{
str[i + num_Blank*2] = '0';
str[i + num_Blank*2 - 1] = '2';
str[i + num_Blank*2 - 2] = '%';
num_Blank--;
}
}
}
};