Kotlin程序员面试算法宝典【1.6】

2.9 如何从给定的车票中找出旅程

【出自 YMX 面试题】

给定一趟旅途旅程中所有的车票信息，根据这个车票信息找出这趟旅程的路线。例如：给定下面的车票：（“西安”到“成都”）， （“北京”到“上海”）， （“大连”到“西安”）， （“上海”到“大连”）。那么可以得到旅程路线为：北京->上海，上海->大连，大连->西安，西安->成都。假定给定的车票不会有环，也就是说有一个城市只作为终点而不会作为起点。

分析与解答：

对于这种题目，一般而言可以使用拓扑排序进行解答。根据车票信息构建一个图，然后找出这张图的拓扑排序序列，这个序列就是旅程的路线。但这种方法的效率不高，它的时间复杂度为 O（N）。这里重点介绍另外一种更加简单的方法： hash 法。主要的思路为根据车票信息构建一个 HashMap，然后从这个 HashMap 中找到整个旅程的起点，接着就可以从起点出发依次找到下一站，进而知道终点。具体的实现思路如下：

（ 1）根据车票的出发地与目的地构建 HashMap。

Tickets= {（“西安”到“成都”）， （“北京”到“上海”）， （“大连”到“西安”）， （“上海”到“大连”） }

（ 2）构建 Tickets 的逆向 hashmap 如下（将旅程的起始点反向）：

ReverseTickets= {（“成都”到“西安”）， （“上海”到“北京”）， （“西安”到“大连”）， （“大连”到“上海”） }

（ 3）遍历 Tickets，对于遍历到的 key 值，判断这个值是否在 ReverseTickets 中的 key 中存在，如果不存在，那么说明遍历到的 Tickets 中的 key 值就是旅途的起点。例如： “北京”在ReverseTickets 的 key 中不存在，因此“北京”就是旅途的起点。实现代码如下：

private fun printResult（input： Map<String， String>） { /* 用来存储把 input 的键与值调换后的信息 */ val reverseInput = hashMapOf<String， String>（） for （（key， value） in input） reverseInput.put（value， key） var start： String？ = null /* 找到起点 */ for （（key） in input） { if （！reverseInput.containsKey（key）） { start = key break } } if （start == null） { println（"输入不合理"） return } /* 从起点出发按照顺序遍历路径 */ var to： String？ = input[start] print（"$start->$to"） to = input[to] while （to ！= null） { print（"， $start->$to"） start = to to = input[to] } } fun main（args： Array<String>） { val input = HashMap<String， String>（） input.put（"西安"， "成都"） input.put（"北京"， "上海"） input.put（"大连"， "西安"） input.put（"上海"， "大连"） printResult（input） }

程序的运行结果如下： 北京->上海， 北京->大连， 大连->西安， 西安->成都

算法性能分析：

这种方法的时间复杂度为 O（N），空间复杂度也为 O（N）。

2.10 如何从数组中找出满足 a+b=c+d 的两个数对

【出自 YMX 面试题】

给定一个数组，找出数组中是否有两个数对（a， b）和（c， d），使得 a+b=c+d，其中， a、 b、 c和 d 是不同的元素。 如果有多个答案， 打印任意一个即可。 例如给定数组： {3， 4， 7， 10， 20， 9， 8}，可以找到两个数对 （3， 8） 和（4， 7），使得 3+8 = 4+7。

分析与解答：

最简单的方法就是使用四重遍历，对所有可能的数对，判断是否满足题目要求，如果满足则打印出来，但是这种方法的时间复杂度为 O（N^4），很显然不满足要求。下面介绍另外一种方法——hash 法，算法的主要思路是：以数对为单位进行遍历，在遍历过程中，把数对和数对的值存储在哈希表中（键为数对的和，值为数对），当遍历到一个键值对，如果它的和在哈希表中已经存在，那么就找到了满足条件的键值对。下面以 HashMap 为例给出实现代码：

/* 用来存储数对 */ class Pair（var first： Int， var second： Int） fun findPairs（arr： IntArray）： Boolean { /* 键为数对的和，值为数对 */ val sumPair = hashMapOf<Int， Pair>（） val n = arr.size /* 遍历数组中所有可能的数对 */ for （i in 0 until n） { for （j in i + 1 until n） { /* 如果这个数对的和在 map 中没有，则放入 map 中 */ val sum = arr[i] + arr[j] if （！sumPair.containsKey（sum）） sumPair.put（sum， Pair（i， j）） /* map 中已经存在与 sum 相同的数对了，找到并打印出来 */ else { /* 找出已经遍历过的并存储在 map 中和为 sum 的数对 */ sumPair[sum]？.apply { println（"（${arr[first]}， ${arr[second]}）， （${arr[i]}， ${arr[j]}）"） } return true } } } return false } fun main（args： Array<String>） { val arr = intArrayOf（3， 4， 7， 10， 20， 9， 8） findPairs（arr） }

程序的运行结果如下：

（3， 8）， （4， 7）

算法性能分析：

这种方法的时间复杂度为 O（n^2）。因为使用了双重循环，而 HashMap 的插入与查找操作实际的时间复杂度为 O（1）。

第 3 章 二 叉 树

3.1 二叉树基础知识

二叉树（ Binary Tree）也称为二分树、二元树、对分树等，它是 n（n≥0）个有限元素的集合，该集合或者为空、或者由一个称为根（ root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。

在二叉树中，一个元素也称作一个结点。二叉树的递归定义是：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称作根结点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。

以下是一些常见的二叉树的基本概念：

（ 1）结点的度。结点所拥有的子树的个数称为该结点的度。

（ 2）叶子结点。度为 0 的结点称为叶子结点，或者称为终端结点。

（ 3）分支结点。度不为 0 的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶子结点外，其余的都是分支结点。

（ 4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。

（ 5）路径、路径长度。如果一棵树的一串结点 n1，n2，…，nk 有如下关系：结点 ni 是 ni+1的父结点（ 1≤i<k），就把 n1，n2，…，nk 称为一条由 n1 至 nk 的路径。这条路径的长度是 k-1。

（ 6）祖先、子孙。在树中，如果有一条路径从结点 M 到结点 N，那么 M 就称为 N 的祖先，而 N 称为 M 的子孙。

（ 7）结点的层数。规定树的根结点的层数为 1，其余结点的层数等于它的双亲结点的层数加 1。

（ 8）树的深度。树中所有结点的最大层数称为树的深度。

（ 9）树的度。树中各结点度的最大值称为该树的度，叶子结点的度为 0。

（ 10）满二叉树。在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。

（ 11）完全二叉树。一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（ 1≤i≤n）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

二叉树的基本性质如下所示：

性质 1：一棵非空二叉树的第 i 层上最多有 2i-1 个结点（ i≥1）。

性质 2：一棵深度为 k 的二叉树中，最多具有 2k-1 个结点，最少有 k 个结点。

性质 3：对于一棵非空的二叉树，度为 0 的结点（即叶子结点）总是比度为 2 的结点多一个，即如果叶子结点数为 n0，度数为 2 的结点数为 n2，则有 n0=n2+1。

证明：用 n0 表示度为 0（叶子结点）的结点总数，用 n1 表示度为 1 的结点总数， n2 表示度为 2 的结点总数， n 表示整个完全二叉树的结点总数。则 n=n0+n1+n2，根据二叉树和树的性质，可知 n=n1+2*n2+1（所有结点的度数之和+1=结点总数） ，根据两个等式可知n0+n1+n2=n1+2*n2+1，所以， n2=n0-1，即 n0=n2+1。所以，答案为 1。

性质 4：具有 n 个结点的完全二叉树的深度为〓 log2 n 」 +1。

证明：根据性质 2，深度为 k 的二叉树最多只有 2k-1 个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数 n 位于 k 层和 k-1 层满二叉树容量之间，即

2 1 2 1 k k -1 - < - n≤ 或 2 2 k k -1

n < 性质 5：对于具有 n 个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从 1 开始顺序编号，则对于任意的序号为 i 的结点，有： （ 1）如果 i>1，则序号为 i 的结点的双亲结点的序号为 i/2（其中“/”表示整除）；如果 i=1，则序号为 i 的结点是根结点， 无双亲结点。 （ 2） 如果 2i≤n， 则序号为 i 的结点的左孩子结点的序号为 2i； 如果 2i>n，则序号为 i 的结点无左孩子。 （ 3）如果 2i+1≤n， 则序号为 i 的结点的右孩子结点的序号为 2i+1；如果 2i+1>n，则序号为 i 的结点无右孩子。

此外， 若对二叉树的根结点从 0 开始编号， 则相应的 i 号结点的双亲结点的编号为（i-1）/2，左孩子的编号为 2i+1，右孩子的编号为 2i+2。

例题 1：一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是多少？

分析：二叉树的公式： n=n0+n1+n2=n0+n1+（n0-1）=2*n0+n1-1。而在完全二叉树中， n1只能取 0 或 1。 若 n1=1， 则 2*n0=1001， 可推出 n0 为小数， 不符合题意； 若 n1=0， 则 2*n0-1=1001，则 n0=501。所以，答案为 501。

例题 2：如果根的层次为 1，具有 61 个结点的完全二叉树的高度为多少？

分析：根据二叉树的性质，具有 n 个结点的完全二叉树的深度为 +1，因此，含有 61 个结点的完全二叉树的高度为 +1，即应该为 6 层。所以，答案为 6。

例题 3：在具有 100 个结点的树中，其边的数目为多少？

分析：在一棵树中，除了根结点之外，每一个结点都有一条入边，因此，总边数应该是100-1，即 99 条。所以，答案为 99。

二叉树有顺序存储和链式存储两种存储结构， 本章涉及的算法都采用的是链式存储结构，本章示例代码用到的二叉树的结构如下：

class BiTNode { var data： Int = 0 var lChild： BiTNode？ = null var rChild： BiTNode？ = null }

3.2 如何把一个有序整数数组放到二叉树中

【出自 WR 面试题】

难度系数：★★★★☆ 被考察系数：★★★☆☆

分析与解答：

如果要把一个有序的整数数组放到二叉树中，那么所构造出来的二叉树必定也是一棵有序的二叉树。鉴于此，实现思路是：取数组的中间元素作为根结点，将数组分成左右两部分，对数组的两部分用递归的方法分别构建左右子树。如下图所示：

如上图所示，首先取数组的中间结点 6 作为二叉树的根结点，把数组分成左右两部分，然后对于数组的左右两部分子数组分别运用同样的方法进行二叉树的构建，例如，对于左半部分子数组，取中间结点 3 作为树的根结点，再把孩子数组分成左右两部分。依此类推，就可以完成二叉树的构建，实现代码如下：

/** 方法功能：把有序数组转换为二叉树 */ fun arrayToTree（arr： IntArray， start： Int， end： Int）： BiTNode？ { val root： BiTNode？ if （end >= start） { root = BiTNode（） val mid = （start + end + 1） / 2 //树的根结点为数组中间的元素 root.data = arr[mid] //递归的用左半部分数组构造 root 的左子树 root.lChild = arrayToTree（arr， start， mid - 1） //递归的用右半部分数组构造 root 的右子树 root.rChild = arrayToTree（arr， mid + 1， end） } else { root = null } return root } /** 用中序遍历的方式打印出二叉树结点的内容 */ fun printTreeMidOrder（root： BiTNode？） { if （root == null） return //遍历 root 结点的左子树 if （root.lChild ！= null） printTreeMidOrder（root.lChild） //遍历 root 结点 print（"${root.data} "） //遍历 root 结点的右子树 if （root.rChild ！= null） printTreeMidOrder（root.rChild） } fun main（args： Array<String>） { val arr = intArrayOf（1， 2， 3， 4， 5， 6， 7， 8， 9， 10） print（"数组： "） arr.indices.forEach { i ->print（"${arr[i]} "） } println（） val root： BiTNode？ root = arrayToTree（arr， 0， arr.size - 1） print（"转换成树的中序遍历为："） printTreeMidOrder（root） println（） }

程序的运行结果如下：

数组： 1 2 3 4 5 6 7 8 9 10

转换成树的中序遍历为：1 2 3 4 5 6 7 8 9 10

算法性能分析：

由于这种方法只遍历了一次数组，因此，算法的时间复杂度为 O（N），其中， N 表示的是数组长度。