剑指offer面试题5：替换空格

// 面试题5：替换空格
// 题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，
// 则输出“We%20are%20happy.”。

/*
思路一：新建一个足够的大小的字符串空间，然后依次将字符拷贝，遇到空格进行三个字符的填充，接着重复执行前面的操作将整个字符串替换完毕。
时间复杂度o(n),空间复杂度o(n).

思路二：从头到尾扫描字符串，每次遇到空格将后续字符向后移动两个位置，然后进行填充。时间复杂度o(n^2)

思路三：从尾部到头进行替换，首先遍历一次字符串的长度，统计其中的空格个数，然后一次性将最末尾的单词向后移动足够的位数。填充倒数第一个空格，穿插移动第二个单词，
接着进行空格的填充，直到所有的空格填充完毕。时间复杂度o(n),空间复杂度o(1).
*/

#include <cstdio>
#include <cstring>

void ReplaceBlank(char str[], int length)
{
	if (str==nullptr || length<=0)
	{
		return;
	}
	int originalLength = 0; 
	int numOfBlank = 0;
	int i = 0;
	//统计原始字符串的长度及其中的空格个数
	while (str[i]!='\0')
	{
		originalLength++;
		if (str[i]==' ')
		{
			numOfBlank++;
		}
		i++;
	}
	//依据空格的个数重新计算填充以后的字符串长度
	int newStringLength = originalLength + numOfBlank * 2;
	//遍历原来的字符串，并进行替换操作
	int indexOfOriginal = originalLength; //indexOfOriginal作为原始字符串的位移指针
	int indexOfNew = newStringLength; //indexOfNew作为新字符串的位移指针
	while (indexOfOriginal >=0 && indexOfNew > indexOfOriginal)
	{
		if (str[indexOfOriginal] == ' ')
		{
			str[indexOfNew--] = '0';
			str[indexOfNew--] = '2';
			str[indexOfNew--] = '%';
		}
		else
		{
			str[indexOfNew--] = str[indexOfOriginal];
		}
		indexOfOriginal--;
	}
	i = 0;
	while (str[i] != '\0')
	{
		printf("%c", str[i]);
		i++;
	}
	printf("\n");
}

// ====================测试代码====================
int main(int args, char* argv[])
{
	const int length = 100;

	char str[length] = "hello world ya";
	ReplaceBlank(str, length);
	return 0;
}