《剑指offer 阅读笔记四》数据结构之字符串

原文链接: http://yiouejv.com/%E5%89%91%E6%8C%87offer/%E5%AD%97%E7%AC%A6%E4%B8%B2/

字符串是否若干字符组成的序列。由于字符串在编程时使用的频率非常高,为了优化,很多语言都对字符串做了特殊的规定.

C/C++中每个字符串都以字符'\0'作为结尾,这样我们就能很方便地找到字符串最后尾部.

但由于这个特点, 每个字符串中都有一个额外的字符开销,稍不留神就会造成字符串的越界.

char str[10];
strcpy(str, "0123456789");

我们先声明一个长度为10的字符数组,然后把字符串"0123456789"复制到数组中. "0123456789"看起来只有10个字符, 但实际上它的末尾还有一个’\0’字符,因此它的实际长度为11字节.
要正确的复制该字符串,至少需要一个长度为11字节的数组.

为了节省内存, C/C++把常量字符串放到单独的一个内存区域.当几个指针赋值给相同的常量字符串时,他们实际上会指向相同的内存地址. 但用常量内存初始化数组,情况却有所不同,下面通过一个面试题来学习这一知识点. 运行下面的代码, 得到的结果是什么?

#include <iostream>
using namespace std;


int main(int argv, const char* argc)
{
	char str1[] = "hello world";
	char str2[] = "hello world";

	const char* str3 = "hello world";
	const char* str4 = "hello world";

	if (str1 == str2)
		cout << "str1 and str2 are same" << endl;
	else
		cout << "str1 and str2 are not same" << endl;

	if (str3 == str4)
		cout << "str3 and str4 are same" << endl;
	else
		cout << "str3 and str4 are not same" << endl;

	return 0;
}

str1 和 str2 是两个字符串数组,我们会为他们分配两个长度为12字节的空间, 并把"hello world"的内容分别赋值到数组中去. 这是两个初始地址不同的数组, 因此str1 和 str2的值也不相同.

str3 和 str4 是两个指针,我们无须为他们分配内存以存储字符串的内容,而只需要把他们指向"hello world"在内存中的地址就可以了,由于"hello world"是常量字符串,他在内存中只有一个拷贝,因此str3 和 str4 指向同一个地址.

面试题5: 替换空格

question
请实现一个函数, 把字符串中的每个空格替换成"%20". 例如, 输入"We are happy.", 则输出"We%20are%20happy."

tip
在网络编程中,如果url参数含有特殊字符,如空格,"#"等, 则可能导致服务器端无法获取正确的参数,我们需要将这些特殊字符转换成服务器可以识别的字符.转换的规则是在’%‘的后面跟上ASCII码的两位十六进制表示. 比如空格的ASCII码是32, 即十六进制的0x20, 因此空格被替换成%20, 再比如’#'的ASCII码为35,即表示为0x23, 他在url中被替换为%23.

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

解法一: 时间复杂度为O(n^2), 不足以拿到offer
	遍历原字符数组, 遇到空格, 在把空格所在位置后面的元素往后移两个位置。 需要保证数组足够长。你会发现空格后面的字符可能存在被移动多次的可能。 解法二对这个问题就行了优化。

解法二: 时间复杂度为O(n)，搞定offer就靠他了
	先遍历一次字符串，统计空格的个数，并可以由此计算出替换之后字符串的总长度，我们从字符串的后面开始复制和替换，这样就避免了后面的字符可能移动多次的情况。

answer
解法一： string_blank_replace1.cpp
解法二： string_blank_replace2.cpp

本题考点：