今日面试题:树的高度

有一个棵树,不一定是二叉树,有n个节点,编号为0到n-1。有一个数组A,数组的索引为0到n-1,数组的值A[i]表示节点i的父节点的id,根节点的父节点id为-1。给定数组A,求得树的高度。

=====================================================

字母表分析

原题

每一种语言,都有自己的字母表,类似英文的a-z,但是顺序不相同。例如,有的语言可能是z是第一个之类的。

现在给定这个语言的字典,请分析这个字典,得到这个语言的字母表的顺序。 例如:有如下的字母:

1. C

2. CAC

3. CB

4. BCC

5. BA

经过分析,得到字母表为C->A->B。

分析

这个题目,在给出例子的时候,结果写作:C->B->A,这个是疏忽了,幸好很多同学都发现了,没有引起太多的舞蹈。

所以,在这里很感谢大家指出问题所在,并且,如果在分析中,大家有觉得不合适的地方,也请大家指出。稍后,会在待字闺中或者微博中说明,真切的希望更多的同学受益。

这个题目其实是比较简单的一个题目。可能题目描述上,有点吓人,其实理解了之后,就会发现,还是蛮简单的。

这个题目的关键就在于:

字典其实隐含了字母的顺序的

这个是很自然的,如果没有想到这一点,这个题目任意解都可以的。而字典有序,是可以作为一个常识的。我们延续题目中的例子进行分析。

首先,C一定是在B之前的,这个是由字典本身的属性决定的。那么剩下的如何考虑呢?比较完第一个字母不同的情况,则比较第一个字母相同的情况。

考虑C和CA,根据我们的经验,A一定是在C后面的,如果A在C的前面,则应该是CA,C的顺序。这样:

  • 根据C和CAC,我们得到C->A(表示C在A的前面,后面同理)
  • 根据CAC和CB,我们得到A->B
  • 根据CB和BCC,我们得到C->B

综合,我们有C->A,A->B,C->B这三个关系,但是,还没有结束。根据这三组关系,如何得到CAB的关系呢? 这三组关系,构成了一个有向无环图,很自然就想要要用拓扑排序得到CAB之间的整体排序。

拓扑排序的算法,不在这里详述,总结一下这个题目的思路:

  • 构建有向无环图:按照字典中单词的顺序,每两个进行比较,找到第一对不相同的字母,确定他们的顺序
  • 对有向无环图进行拓扑排序

构建有向无环图的时间复杂度为O(N*M),N是字典中单词数目,M是单词长度;有向图拓扑排序的时间复杂度是O(|V|+|E|)。

这个题目,并不是难题,解决的过程中,仅仅抓住字典的特点即可。

【分析完毕】

本文来自微信:待字闺中,2013-08-27发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。