剑指offer笔记面试题5----替换空格

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

注意：看到这个题目，我们首先应该想到的是原来一个空格字符，替换之后变成'%'、'2'和'0'这3个字符，因此字符串会边长。如果是在原来的字符串上进行替换，就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上进行替换，那么我们可以自己分配足够多的内存。由于有两种不同的解决方案，我们应该向面试官问清楚，让他明确告诉我们他的需求。假设面试官让我们在原来的字符串上进行替换，并且保证输入的字符串后面有足够多的空余内存。

测试用例：

输入的字符串中包含空格（空格位于字符串的最前面；空格位于字符串的最后面；空格位于字符串的中间；字符串中有连续多个空格）。
输入的字符串中没有空格。
特殊输入测试（字符串是一个nullptr指针；字符串是一个空字符串；字符串只有一个空格字符；字符串中有连续多个空格）。

测试代码：

void test(char* testName, char str[], int length, char expected[]){

	if(testName != nullptr){

		printf("%s begins: ", testName);

	}

	replaceBlank(str, length);

	if(expected == nullptr && str == nullptr){

		printf("passed.\n");

	}

	else if(expected == nullptr && str != nullptr){

		printf("failed.\n");

	}

	else if(strcmp(str, expected) == 0){

		printf("passed.\n");

	}

	else{

		printf("failed.\n");

	}

} 

//空格在句子中间

void test1(){

	const int length = 100;

	char str[length] = "hello world";

	test("test1", str, length, "hello%20world");

} 

//空格在句子开头

void test2(){

	const int length = 100;

	char str[length] = " helloworld";

	test("test2", str, length, "%20helloworld");

} 

//空格在句子末尾

void test3(){

	const int length = 100;

	char str[length] = "helloworld ";

	test("test3", str, length, "helloworld%20");

} 

//连续有两个空格

void test4(){

	const int length = 100;

	char str[length] = "hello  world";

	test("test4", str, length, "hello%20%20world");

} 

//传入nullptr

void test5(){

	test("test5", nullptr, 0, nullptr);

} 

//传入内容为空字符串

void test6(){

	const int length = 100;

	char str[length] = "";

	test("test6", str, length, "");

} 

//传入内容为一个空格的字符串

void test7(){

	const int length = 100;

	char str[length] = " ";

	test("test7", str, length, "%20");

} 

//传入的字符串没有空格

void test8(){

	const int length = 100;

	char str[length] = "helloworld";

	test("test8", str, length, "helloworld");

} 

//传入的字符串全是空格

void test9(){

	const int length = 100;

	char str[length] = "   ";

	test("test9", str, length, "%20%20%20");

}

本题考点：

考查应聘者对字符串的编程能力。
考查应聘者分析时间效率的能力。我们要能清晰地分析出两种不同方法的时间效率各是多少。
考查应聘者对内存覆盖是否有高度的警惕。在分析得知字符串会变长之后，我们能够意识到潜在的问题，并主动和面试官沟通以寻找问题的解决方案。
考查应聘者的思维能力。在从前到后替换的思路被面试官否定之后，我们能够迅速先到从后往前替换的方法，这是解决此题的关键。

实现代码：

#include <cstdio>

#include <cstring>

//length为字符数组str的总容量，大于或等于字符串str的实际长度

void replaceBlank(char str[], int length){

	if(str == nullptr && length <= 0){

		return;

	}

	//originalLength为字符串str的实际长度

	int originalLength = 0;

	int numberOfBlank = 0;

	int i = 0;

	while(str[i] != '\0'){

		originalLength++;

		if(str[i] == ' '){

			numberOfBlank++;

		}

		i++;

	}

	//newLength为把空格替换成'%20'之后的长度

	int newLength = originalLength + numberOfBlank * 2;

	if(newLength > length){

		return;

	}

	int indexOfOriginal = originalLength;

	int indexOfNew = newLength;

	while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal){

		if(str[indexOfOriginal] == ' '){

			str[indexOfNew--] = '0';

			str[indexOfNew--] = '2';

			str[indexOfNew--] = '%';

		}

		else{

			str[indexOfNew--] = str[indexOfOriginal];

		}

		--indexOfOriginal;

	}

}

int main(){

	test1();

	test2();

	test3();

	test4();

	test5();

	test6();

	test7();

	test8();

	test9();

	return 0;

}

巴特西

剑指offer笔记面试题5----替换空格

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

测试用例：

测试代码：

本题考点：

实现代码：

最新文章

热门文章