博客

题目：将字符串中的每个空格都替换成”space”，但不能申请新的buffer，同时要保证O(n)级的时间复杂度。

对与这道题，首先我们先分析的是题目中所给出的要求：

(1)不能申请新的buffer，也就是说我们不可以申请新的空间用来装新的字符串；

(2)保证O(n)级的时间复杂度，也就是说，我们不能使用双层循环去解决问题；

这样的两个条件，使得这道题的复杂度稍微增加，我们一步一步来解决：

如果我们获取了字符串长度后再用malloc()申请一个动态空间装字符串是最节省空间的方法，但是我们不能申请新的字符串，所以，我们在一开始定义装字符串用的字符数组必须是足够长的，我们首先先定义一个长度为40的字符串，并且获键盘输入，将输入赋值在我们定义的字符串中

char input[40];
gets(input);

既然我们不能申请新的字符数组空间，这就意味着我们只能在该字符串的基础上进行字符替换，那就涉及到一个问题，那就是替换次序。

如果是常规的思维下，我们选择从头到尾的次序进行替换，那么根据这种方法，我们首先需要对原字符串进行检测，循环遍历检测对应的字符，如果是空格的话需要停下来将包括空格所在的位置和之后的4个位置替换为space（“space”中有5个字母除去空格所在位置本身还有四个位置需要替换）

此时，我们可以看到在没遇到空格之前字符串的替换是正常的但是在遇到空格之后，我们会发现一些问题，首先，当我们检测到空格后，我们需要将该位置替换为“space”中的“s”，接着我们要将空格后的第二个位替换成“p”，但是别忘了，我们所使用的仍旧是原来的字符串空间，也就是说，原本这个位置应该是“w”但是被替换成了“p”，因此如果我们选择正向替换的话会出现字符串覆盖的问题，因此，正向替换是不可行的，故我们进行反向替换。

如果想要反向替换，首先我们就需要确定我们最后生成的字符串的长度，以“hello world”作为输入字符串为例，期间有一个空格，那么替换为“space”后，“hello world”字符串变为“hellosapceworld”长度由11变成15，因此我们设输入字符串中的空格个数为n，要替换的字符“space”中含有5个字符，则：

输出的字符串的长度 = 原字符串长度 +(5-1)*n

因此我们在替换时可以选择使用两个指针或者两个标号作为索引，不断替换两个位置的值，并且值得注意的是，当我们检测到空格时，此时我们要停下检测原始字符串的值，在新的字符串中开始在空格的位置及之后的位置替换字符串“space”，也就是说此时原始字符的指针停下来了，但是，输出字符串的指针并没有停下来。

首先，先来确定下字符串中包含有多少空格，我们定义一个新的函数用来确定字符串中的空格数量，输入的参数为一个字符串，返还值为字符串中的空格数，代码如下：

int space_num(char* str)
{
	int num = 0;
	for (int i = 0; str[i] != '\0'; i++)
	{
		if (str[i] == ' ') num += 1;
	}
	return num;
}

接着，我们就可以进入原始字符串的循环遍历，再次之前我们还需要确定字符串的长度，可以直接包含<string.h>的头文件，使用strlen()直接获取字符串的长度，当然我们也可以自己实现这个函数的功能，输入的参数为一个字符串，返还值为字符串中字符的数量，代码如下：

int str_len_my(char* str)
{
	int num = 0;
	char* idx = str;
	for (idx; *idx != '\0'; idx++) //由于char变量的大小为1，故循环+1即可
	{
		num += 1;
	}
	return num;
}

由于，我们每次需要交换同一个数组中两个位置的值，我们可以再写一个用于交换两个位置的值的函数，别问为什么总自己写函数，问就是为了“优雅”

int exchange(char* temp1, char* temp2)
{
	char temp = 0;
	temp = *temp1;
	*temp1 = *temp2;
	*temp2 = temp;
	return 0;
}

这样的话，我们的准备工作就都完成了，只要编写循环遍历原始数组的部分的主函数就可以了，这里我们可以想一下，循环的时候我们遍历的索引值是什么，我们可以使用原数组的长度作为索引值，每次-1，在等于0后跳出循环，但是我们再来看一下我们替换的过程：

其实，当我们的空格已经全部替换完成后，在之后的量我们就没必要在进行替换了，这样可以更加省时省力，以“hello world为例，如果我们使用其长度本身作为遍历的值，则需要循环11次，而如果我们使用空格的数量作为遍历的值只需要6次”因此我们最终的代码如下：

#include <stdio.h>

int main()
{
	char input[40] = { "hello world"};
	char* temp1 = 0;
	char* temp2 = 0;
	int spacenum = 0;
	spacenum = space_num(input);
	temp1 = &input[str_len_my(input) - 1];                     //temp1指针指向原始字符串的尾部
	temp2 = &input[str_len_my(input) + (5 - 1) * spacenum - 1];//temp2指针指向输出字符串的尾部
	while (spacenum)
	{
		if (*temp1 != ' ') exchange(temp1, temp2);
		else
		{
			*temp2 = 'e'; temp2 -= 1;
			*temp2 = 'c'; temp2 -= 1;
			*temp2 = 'a'; temp2 -= 1;
			*temp2 = 'p'; temp2 -= 1;
			*temp2 = 's'; 
			spacenum -= 1;
		}
		temp1 -= 1;
		temp2 -= 1;
	}
	printf("%s", input);

	return 0;
}
int space_num(char* str)
{
	int num = 0;
	for (int i = 0; str[i] != '\0'; i++)
	{
		if (str[i] == ' ') num += 1;
	}
	return num;
}
int str_len_my(char* str)
{
	int num = 0;
	char* idx = str;
	for (idx; *idx != '\0'; idx++)
	{
		num += 1;
	}
	return num;
}
int exchange(char* temp1, char* temp2)
{
	char temp = 0;
	temp = *temp1;
	*temp1 = *temp2;
	*temp2 = temp;
	return 0;
}

当然，如果引用了头文件的话直接使用库函数可能会更为简洁。