【牛客网刷题】剑指Offer第二题——替换空格

题目描述

这个题目也没有测试用例，而且给出的C++定义的函数实现结构是这样的：

原来一直以为这个length参数是字符串的长度；后来一直通不过测试用例，看了原书才知道这个length是字符串指针str指定的最长数组长度！！ 而且这个题目也没说让原地置换，因为这个length就是为原地置换而给出的！ 所以感觉题目说的不清楚搞得很伤。

所以明白了这道题的真实用意之后：要求原地替换（就是不使用别的辅助数组空间），然后length是限定的一个最长数组长度，也就是str的最大容量。而且最好你的算法时间复杂度是O(N)，不然O(N*N)是很容易想的，测试用例估计会报超时。

思路：先统计str的空格数目spaceNum，同时计算原数组str的真实字符串长度originLen，那么替换之后变长的字符串长度就是oringinLen + spaceNum * 2 ； 跟length比较一下，如果没超过就可以往下面进行了。 接着咱从后往前替换，倒着遍历原字符串str，然后替换后的字符也倒着从后往前存起来。

代码如下：

class Solution {
public:
	void replaceSpace(char *str,int length) {
		int originalStrlen = 0, spaceNum = 0; //原字符串长度，空格数目
		int i = 0;
		while (str[i] != '\0')
		{
			++originalStrlen;
			if(str[i] == ' ')
				++spaceNum;
			++i;
		}
		int newLen = originalStrlen + 2 * spaceNum;//计算替换后的字符串的长度
		if(newLen > length) return;//看看计算的新长度是不是比函数给出的length大

		int indexOrigin = originalStrlen, indexNew = newLen;
		while (indexOrigin >= 0 && indexNew > indexOrigin)//从后往前替换
		{
			if(str[indexOrigin] == ' ')
			{
				str[indexNew--] = '0';
				str[indexNew--] = '2';
				str[indexNew--] = '%';
			}else{
				str[indexNew--] = str[indexOrigin];
			}
			--indexOrigin;
		}
	}
};