第3章 结构之法——字符串及链表的探索

_2011-01-18_上午10.47.45.png
研究院每天下午三点钟有大量新鲜水果供应,这是大家每天盼望的时刻,部分同事
还拍了一部叫“三点”的电影,限量发行。

这一章覆盖了常用的数据结构。对字符串、链表、队列和树等数据结构的处理几乎是每个程序中会涉及的问题。同学们在课堂上也学过,这些问题有什么好考的呢?
大家都知道二叉树的前序、中序和后序遍历算法,但是当给出了两个遍历输出的结果,要求还原二叉树的时候,就能考察出大家是否真正掌握了这些不同遍历算法的含义及使用它们的办法。

有些同学对于“指针”比较恐惧,笔者也听说某些大学里“C语言”这门课不讲指针,于是学生和老师在上课的时候都轻松了一阵子,但是在找工作和实际工作中,就不轻松了——“出来混,总是要还的”。事实上指针就是内存中的地址,没什么可怕的。

有不少同学学习了Java、C#,这些现代的语言和运行环境(例如 Java VM、CLR),通常把实现的细节给掩盖了。你觉得很方便,例如:要排序,则array.sort(),要新的实体,就new()一个,不用担心什么时候需要释放,多好!但是不要忘了有句谚语:The devil is in the details。

在“操控CPU使用率”这个面试题目中,有一个应聘者的C#代码从逻辑上看都没有任何问题,但是在运行中,CPU的使用率就是不平滑,会突然产生巨大的抖动,然后回归正常。反复研究之后,发现问题原来出自——

TimeSpan ts = new TimeSpan();

这句话没有错,但是他把这句话放在了一个循环里面,这样在很短的时间内,程序就创建了大量的TimeSpan对象。程序员不管释放,但是CLR要管,所以CLR就要经常进行垃圾清理(GC)工作,导致CPU的使用率急剧上涨。这些details(细节)处理不好,你的程序就会出现你不能理解的奇怪行为。


3.1 字符串移位包含的问题


给定两个字符串s1和s2,要求判定s2是否能够被s1做循环移位(rotate)得到的字符串包含。例如,给定s1 = AABCD 和s2 = CDAA,返回true;给定s1 = ABCD和s2 = ACBD,返回false。

- uniquestudio uniquestudio
关于3.1字符串移位包含的问题,我有新的思路。
详见 字符串问题

3.2 电话号码对应英语单词


电话的号码盘一般可以用于输入字母。如用2可以输入A、B、C,用3可以输入D、E、F等。如图3-1所示。

.png
图3-1 手机按键示意图

对于号码5869872,可以依次输出其代表的所有字母组合。如:JTMWTPA、JTMWTPB……

  1. 您是否可以根据这样的对应关系设计一个程序,尽可能快地从这些字母组合中找到一个有意义的单词来表述一个电话号码呢?如:可以用单词“computer”来描述号码26678837。
  2. 对于一个电话号码,是否可以用一个单词来代表呢?怎样才是最快的方法呢?显然,肯定不是所有的电话号码都能够对应到单词上去。但是根据问题1的解答,思路相对比较清晰。


3.3 计算字符串的相似度


许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程度。我们定义了一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:

  1. 修改一个字符(如把“a”替换为“b”);
  2. 增加一个字符(如把“abdd ”变为“aebdd ”);
  3. 删除一个字符(如把“travelling”变为“traveling”)。

比如,对于“abcdefg”和“abcdef ”两个字符串来说,我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离,而相似度等于“距离+1”的倒数。也就是说,“abcdefg”和“abcdef”的距离为1,相似度为1 / 2 = 0.5。

给定任意两个字符串,你是否能写出一个算法来计算出它们的相似度呢?

- gpww gpww: 用书中解法
strA = "appidimiologist";
strB = "epidemiologist";
会很慢,下面这个解法会快很多:
最长公共子序列 计算字符串的相似度

- firewoods firewoods:
strA = "aba";
strB = "bab";
最常公共子序列长度是2, 所以字符串之间的距离是1.
而实际上, 这2个字符串之间的距离应该是2吧?

- flyinghearts flyinghearts
实际上就是求字符串的编辑距离 edit distance
本题是动态规划经典应用之一,希望改成用该方法求解。

希望增加 与最长公共子序列LCS的关系:
一般情况下,edit distance 与 LCS 毫无关系
但不允许 直接进行“修改”操作时(修改一个字符,需要“删除”和“增加”两个步骤):
edit distance = len(a) + len(b) - 2 * LCS(a, b)

- gaobo gaobo:
我觉得用最长公共子序列挺好,速度快很多:http://yishan.cc/blogs/gpww/archive/2009/10/08/2-6.aspx


3.4 从无头单链表中删除节点


假设有一个没有头指针的单链表。一个指针指向此单链表中间的一个节点(不是第一个,也不是最后一个节点),请将该节点从单链表中删除。
例如有如下链表,如图3-5所示。

3.5.png
图3-5

- flyinghearts flyinghearts
希望强调下,使用该方法的缺点:可能产生野指针。


3.5 最短摘要的生成


互联网搜索已经成为了大家工作和生活的一部分。在输入一些关键词之后,搜索引擎会返回许多结果,每个结果都包含一段概括网页内容的摘要。例如,在www.live.com中搜索“微软亚洲研究院 使命”,第一个结果是微软亚洲研究院的首页,如图3-8所示。

在搜索结果中,标题和URL之间的内容就是我们所说的摘要:

3.8.png
图3-8 搜索引擎中的最短摘要


这些最短摘要是怎样生成的呢?可以对问题进行如下的简化。

假设给定的已经是经过网页分词之后的结果,词语序列数组为W。其中W[0], W[1],…, W[N]为一些已经分好的词语。

假设用户输入的搜索关键词为数组Q。其中Q[0], Q[1],…, Q[m]为所有输入的搜索关键词。

这样,生成的最短摘要实际上就是一串相互联系的分词序列。比如从W[i]到W[j],其中,0<i<j<=N。例如图3-8中,“微软亚洲研究院成立于1998年,我们的使命”包含了所有的关键字——“微软亚洲研究院 使命”。

那么,我们该怎么做呢?

- yangjunpro yangjunpro:
原始问题出于简化的考虑,应该是假设了正文摘要可以在一台机器的主存中放下。但是实际应用场景中,这个假设未必成立。我们不妨假设一下,如果有1个TB的正文数据,而我们手上拥有的单台机器上的最大物理内存只有2GB(单机数目无限),那么我们可以通过什么样的手法解决最短摘要生成的这个问题呢?如果进一步约束,我们手上拥有的单机数目也是有限的,只有200台的话,又可以怎样解决这个问题呢?我想这些都会是比较有趣的延伸思考吧。


3.6编程判断两个链表是否相交


给出两个单向链表的头指针(如图3-9所示),比如h1、h2,判断这两个链表是否相交。这里为了简化问题,我们假设两个链表均不带环。

_2011-01-18_上午11.28.23.png


- flyinghearts flyinghearts
希望增加双指针操作方法,这是链表题的常用方法。

- july july:
第九章、闲话链表追赶问题(第二节):
http://blog.csdn.net/v_JULY_v/archive/2011/05/26/6447013.aspx
有任何问题,bug请指出。
July、2011.05.27。


‍‍‍‍3.7 队列中取最大值操作问题‍‍‍‍



假设有这样一个拥有3个操作的队列:

  1. EnQueue(v):将v加入队列中
  2. DeQueue:使队列中的队首元素删除并返回此元素
  3. MaxElement:返回队列中的最大元素

请设计一种数据结构和算法,让MaxElement操作的时间复杂度尽可能地低。

队列是遵守“先入先出”原则的一种复杂数据结构。其底层的数据结构不一定要用数组来实现,还可以使用其他特殊的数据结构来实现,以达到降低MaxElement操作复杂度的目的。

- gpww gpww 从这个题目学到的用法...寻找最远点对(三)增强堆栈

- flyinghearts flyinghearts
希望能将函数名改下,与stl的名字保持一致

解法二,应该详细描述如何定位队列的元素,因为在维护堆的过程中元素是在不断移动。比如说设计的数据结构是基于双向链表,并构成最大堆。
题目应该将“设计栈结构”,应该单独列为一个子问题。设计队列结构,结果先考虑设计设计栈结构,总觉得怪怪的。
底层数据结构必须保证效率,用栈来实现队列,或用队列实现栈,都不大好。解答中,设计的队列结构,不应该依赖于所额外设计的栈结构,效率差而且空间浪费严重。

解法三,应该详细介绍怎么维护指针,最好加图说明,在pop、push过程中,指针的变化。

- gaobo gaobo:这个我做了点改进:http://yishan.cc/blogs/gpww/archive/2011/02/18/1791.aspx


3.8 求二叉树中节点的最大距离



如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的,我们姑且定义“距离”为两个节点之间边的个数。

写一个程序求一棵二叉树中相距最远的两个节点之间的距离。

如图3-12所示,粗箭头的边表示最长距离。
_2011-01-18_上午11.32.54.png

- flyinghearts flyinghearts:本题不允许自行设计数据结构,解法不合题意。
- uniquestudio uniquestudio其实就是找树的直径,书上的解法属于树形动规,另外我有一种贪心思路,可以证明是正解
从任意一个节点出发寻找离这个节点最远的点A,然后再从A点出发找到离A点最远的点B,AB即为此树的直径。同样对多叉树一样有效,用反证法可以证明。网络上有很多对树的直径的证明,我就不多说了。
- SammyLan SammyLan其实题目思路很简单,我们做如下定义:L(i)-经过结点i的最长距离, H(i)-从结点i到叶子结点的最长路径上结点的个数,则有L(i) = H(i->left)+H(i->right);所求的最大距离L=Max(L(1),......L(n));用后序遍历自底向上地求出每个结点的最长距离,求最大值即可,算法复杂度为O(N),如下
int MaxLength(Node * node)
{
int maxLen =0;
MaxLength(node,maxLen);
return maxLen;
}
int MaxLength(Node * node, int & maxLen)
{
if(node==0)
return 0;
int l = Height(node->_lChild);
int r = Height(node->_rChild);
if(maxLen<(l+r))
maxLen = l+r;
return 1 + max(l,r);
}

3.9重建二叉树


每一个学过算法和数据结构的同学都能很流利地背诵出二叉树的三种遍历次序——前序、中序、后序,也都能很快地写出相应的算法(希望如此)。那么,如果已经知道了遍历的结果,能不能把一棵二叉树重新构造出来呢?

给定一棵二叉树,假设每个节点都用唯一的字符来表示,具体结构如下:
struct NODE {
 NODE* pLeft;
 NODE* pRight;
 char chValue; // it can be other data type
};

假设已经有了前序遍历和中序遍历的结果,希望通过一个算法重建这棵树。

给定函数的定义如下:
void Rebuild(char* pPreOrder, char* pInOrder,int nTreeLen, NODE** pRoot)


参数

pPreOrder:以null为结尾的前序遍历结果的字符串数组。
pInOrder:以null为结尾的中序遍历结果的字符串数组。
nTreeLen:树的长度。
pRoot:返回node类型,根据前序和中序遍历结果重新构建树的根节点。

例如
前序遍历结果:a b d c e f
中序遍历结果:d b a e c f

重建的树如图3-17所示。
_2011-01-18_上午11.37.37.png

请用C或C++来实现二叉树的重建。

- flyinghearts flyinghearts:
希望将代码改写为C++代码,用引用而不是指针。另外,代码需要再卦装下,将pRoot设置为NULL,应该由程序来完成,而不应该由调用者手动完成。如果调用者忘记设置的话,还会造成内存泄漏(分配pTemp,但却没释放)。

3.10 分层遍历二叉树


问题1:给定一棵二叉树,要求按分层遍历该二叉树,即从上到下按层次访问该二叉树(每一层将单独输出一行),每一层要求访问的顺序为从左到右,并将节点依次编号。那么分层遍历如图3-18中的二叉树,正确输出应为:
1
2 3
4 5 6
7 8

_2011-01-18_上午11.49.58.png

问题2:写另外一个函数,打印二叉树中某层次的节点(从左到右),其中根节点为第0层,函数原型为int PrintNodeAtLevel(Node* root, int level),成功返回1,失败则返回0。


3.11 程序改错



一次面试之后,应聘者和面试者微笑着握手告别,但是他们对面试的评价往往相差很远,例如——

应聘者:来了一个比较和气的员工,我们谈了谈各种排序的优劣,我昨天晚上在网上看的东西都用上了,我几乎要把他侃晕了。后来,他要我写一个二分查找的程序,我略加思索,很快地写好了,写得太快了,有一个条件没有考虑,让他看了出来。后来他叫我再检查一下还有什么错,我还是比较自信的,觉得代码没什么大问题。他挑出来一些小小的问题,无外乎一些“牛角尖”的问题,我也很快搞定了……我觉得面试也不过如此。

面试者:我们先谈了谈了谈各种排序的优劣,我发现他混淆了各种排序方法的优缺点和适用范围,叙述得完全没有条理(例如……)。我叫他写一个完整的二分查找程序。他想了很长时间,最后写出来的解法有一个严重的错误,我指出之后,他能想出一个改正的方法,但不是最优的。我强调“完整的程序”,让他再检查一下还有什么错,他根本不会用一些测试用例去检查,而是把程序又自己读了一遍,说没有错误。我指出了至少4个小错误,他能认识这些错误,但是在修改中把原来算法的结构破坏了,最后的解法显得非常混乱。他在这个题目中花了很长时间……我觉得他明显达不到我们的要求。

二分查找是算法设计的基本功。它的思想很简单:分而治之;即通过把一个大问题分解成多个子问题来降低解题的复杂度。思路固然简单,但是许多人在写代码实现的时候却往往容易出现各种错误。下面是一个程序片段(如代码清单3-17所示),其中包含了一些常见的错误。你能够找出来吗?

问题:找出一个有序(字典序)字符串数组arr中值等于字符串v的元素的序号,如果有多个元素满足这个条件,则返回其中序号最大的。

int bisearch(char** arr, int b, int e, char* v)
{
 int minIndex = b, maxIndex = e, midIndex;
 while(minIndex < maxIndex)
 {
 midIndex = (minIndex + maxIndex) / 2;
 if(strcmp(arr[midIndex], v) <= 0)
 {
 minIndex = midIndex;
 }
 else
 {
 maxIndex = midIndex – 1;
 }
 }
 if(!strcmp(arr[maxIndex], v))
 {
 return maxIndex;
 }
 else
 {
 return -1;
 }
}
代码清单3-17:带有错误的二分查找源码

- flyinghearts flyinghearts:
《编程珠矶》上说二分法,只有10%的程序员能写对,从有人提出该法到出现一个无bug的代码,经历了十几年。
应该补充采用区间的不同表示(全闭合或前闭后开)时代码的区别。
那个错误例子,实际上只需改动一行:
midIndex = (minIndex + maxIndex) / 2;
改为:
midIndex = minIndex + (maxIndex - minIndex + 1) / 2;

代码3-18,最好注明下采用全闭合区间。函数原型最好用const char*。如果把该代码最后部份对arr[maxIndex]和v的比较去掉,得到的新代码,就是采用前闭后开区间的写法!