剑指 Offer 05. 替换空格（C++实现）

• 题目
• 实现思路
• 实现代码
• 题目疑点解答

剑指 Offer 05. 替换空格

1. 可以原地修改输入数组s的大小为输出数组的大小；即扩容；
2. 同时用一个指针i指向修改后最后一个元素位置，一个指针j指向输入数组最后一个元素的位置；
3. 当输入数组的位置不为空格时候就直接赋值：s[ i ] = s[ j ];
   当输入数组的位置为空格时候就替换空格;

注：此git来源于代码随想录它人；并不是作者制作的gif。

 string replaceSpace(string s) {
	//统计空格个数：为的是开辟输出数组的大小
	int count = 0;
	int oldSize = s.size(); //输入数组的大小
	
	for(int i = 0;i < s.size();i++){
		if(s[i] == ' ') ++count;
	}
	//统计完后：开始原地开辟输出数组的大小
	// newSize = oldsize + count*2;
	s.resize(s.size() + count *2);
	int newSize = s.size(); //输出数组的大小
	
	//双指针分别指向输入数组和输出数组的最后一个元素位置
	//开始从后往前开始赋值和替换空格；
	//结束循环条件是：i <= j时候；
	for(int i = newSize - 1,j = oldSize - 1; i  > j;i--,j--){
		if(s[j] != ' '){
			s[i] = s[j];
		}else{
			s[i] = '0';
			s[i -1] = '2';
			s[i-2] = '%';
            i -=2;
		}
	}
	return s;	
}

为什么要从后向前填充，从前向后填充不行么？

从前向后填充每每次添加元素都要将添加元素之后的所有元素向后移动，这个是数组的特性，时间是复杂度过高。

而对于很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作;这样添加元素时候就不必把添加元素后面的元素都往后移；同时还在原地修改数组大小，不用开辟多一个新空间；