《剑指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
本题考点：
- 考查应聘者对字符串的编程能力。
- 考查应聘者分析时间效率的能力。
- 考查应聘者对内存覆盖是否有高度的警惕。 在分析得知字符串会变长之后，我们能够意识到潜在问题，并主动和面试官沟通以寻找问题的解决方案。
- 考查应聘者的思维能力。 在从前到后替换的思路和面试官否定之后，我们能迅速想到从后到前替换的方法。 这是解决此题的关键。
相关题目：
- 有两个排序的数组A1和A2，内存在A1的末尾有足够的空余空间容纳A2. 请实现一个函数，把A2中的所有数字插入到A1中，并且所有的数字的排序的。
mergeSortedArray.cpp
举一反三：
在合并两个数组(包括字符串)时，如果从前往后复制每个数字（或字符）则需要移动数字（或字符多次），那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率。
