2.9 如何从给定的车票中找出旅程【出自 YMX 面试题】难度系数★★★☆☆ 题目描述被考察系数★★★★☆给定一趟旅途旅程中所有的车票信息根据这个车票信息找出这趟旅程的路线。例如给定下面的车票“西安”到“成都” “北京”到“上海” “大连”到“西安” “上海”到“大连”。那么可以得到旅程路线为北京-上海上海-大连大连-西安西安-成都。假定给定的车票不会有环也就是说有一个城市只作为终点而不会作为起点。分析与解答对于这种题目一般而言可以使用拓扑排序进行解答。根据车票信息构建一个图然后找出这张图的拓扑排序序列这个序列就是旅程的路线。但这种方法的效率不高它的时间复杂度为 ON。这里重点介绍另外一种更加简单的方法 hash 法。主要的思路为根据车票信息构建一个 HashMap然后从这个 HashMap 中找到整个旅程的起点接着就可以从起点出发依次找到下一站进而知道终点。具体的实现思路如下 1根据车票的出发地与目的地构建 HashMap。Tickets {“西安”到“成都” “北京”到“上海” “大连”到“西安” “上海”到“大连” } 2构建 Tickets 的逆向 hashmap 如下将旅程的起始点反向ReverseTickets {“成都”到“西安” “上海”到“北京” “西安”到“大连” “大连”到“上海” } 3遍历 Tickets对于遍历到的 key 值判断这个值是否在 ReverseTickets 中的 key 中存在如果不存在那么说明遍历到的 Tickets 中的 key 值就是旅途的起点。例如 “北京”在ReverseTickets 的 key 中不存在因此“北京”就是旅途的起点。实现代码如下private fun printResultinput MapString String { /* 用来存储把 input 的键与值调换后的信息 */ val reverseInput hashMapOfString String for key value in input reverseInput.putvalue key var start String null /* 找到起点 */ for key in input { if reverseInput.containsKeykey { 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 mainargs ArrayString { val input HashMapString String input.put西安 成都 input.put北京 上海 input.put大连 西安 input.put上海 大连 printResultinput }程序的运行结果如下 北京-上海 北京-大连 大连-西安 西安-成都算法性能分析这种方法的时间复杂度为 ON空间复杂度也为 ON。2.10 如何从数组中找出满足 abcd 的两个数对【出自 YMX 面试题】难度系数★★★☆☆ 题目描述被考察系数★★★★☆给定一个数组找出数组中是否有两个数对a b和c d使得 abcd其中 a、 b、 c和 d 是不同的元素。 如果有多个答案 打印任意一个即可。 例如给定数组 {3 4 7 10 20 9 8}可以找到两个数对 3 8 和4 7使得 38 47。分析与解答最简单的方法就是使用四重遍历对所有可能的数对判断是否满足题目要求如果满足则打印出来但是这种方法的时间复杂度为 ON^4很显然不满足要求。下面介绍另外一种方法——hash 法算法的主要思路是以数对为单位进行遍历在遍历过程中把数对和数对的值存储在哈希表中键为数对的和值为数对当遍历到一个键值对如果它的和在哈希表中已经存在那么就找到了满足条件的键值对。下面以 HashMap 为例给出实现代码/* 用来存储数对 */ class Pairvar first Int var second Int fun findPairsarr IntArray Boolean { /* 键为数对的和值为数对 */ val sumPair hashMapOfInt 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.containsKeysum sumPair.putsum Pairi j /* map 中已经存在与 sum 相同的数对了找到并打印出来 */ else { /* 找出已经遍历过的并存储在 map 中和为 sum 的数对 */ sumPair[sum].apply { println${arr[first]} ${arr[second]} ${arr[i]} ${arr[j]} } return true } } } return false } fun mainargs ArrayString { val arr intArrayOf3 4 7 10 20 9 8 findPairsarr }程序的运行结果如下3 8 4 7算法性能分析这种方法的时间复杂度为 On^2。因为使用了双重循环而 HashMap 的插入与查找操作实际的时间复杂度为 O1。第 3 章 二 叉 树3.1 二叉树基础知识二叉树 Binary Tree也称为二分树、二元树、对分树等它是 nn≥0个有限元素的集合该集合或者为空、或者由一个称为根 root的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时称该二叉树为空二叉树。在二叉树中一个元素也称作一个结点。二叉树的递归定义是二叉树或者是一棵空树或者是一棵由一个根结点和两棵互不相交的分别称作根结点的左子树和右子树所组成的非空树左子树和右子树又同样都是一棵二叉树。以下是一些常见的二叉树的基本概念 1结点的度。结点所拥有的子树的个数称为该结点的度。 2叶子结点。度为 0 的结点称为叶子结点或者称为终端结点。 3分支结点。度不为 0 的结点称为分支结点或者称为非终端结点。一棵树的结点除叶子结点外其余的都是分支结点。 4左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。 5路径、路径长度。如果一棵树的一串结点 n1n2…nk 有如下关系结点 ni 是 ni1的父结点 1≤ik就把 n1n2…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则有 n0n21。证明用 n0 表示度为 0叶子结点的结点总数用 n1 表示度为 1 的结点总数 n2 表示度为 2 的结点总数 n 表示整个完全二叉树的结点总数。则 nn0n1n2根据二叉树和树的性质可知 nn12*n21所有结点的度数之和1结点总数 根据两个等式可知n0n1n2n12*n21所以 n2n0-1即 n0n21。所以答案为 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≤ 数所以 k〓 log2 n 」 1。三边同时取对数于是有 k n k -1 log ≤ 2 因为 k 是整n 性质 5对于具有 n 个结点的完全二叉树如果按照从上至下和从左到右的顺序对二叉树中的所有结点从 1 开始顺序编号则对于任意的序号为 i 的结点有 1如果 i1则序号为 i 的结点的双亲结点的序号为 i/2其中“/”表示整除如果 i1则序号为 i 的结点是根结点 无双亲结点。 2 如果 2i≤n 则序号为 i 的结点的左孩子结点的序号为 2i 如果 2in则序号为 i 的结点无左孩子。 3如果 2i1≤n 则序号为 i 的结点的右孩子结点的序号为 2i1如果 2i1n则序号为 i 的结点无右孩子。此外 若对二叉树的根结点从 0 开始编号 则相应的 i 号结点的双亲结点的编号为i-1/2左孩子的编号为 2i1右孩子的编号为 2i2。例题 1一棵完全二叉树上有 1001 个结点其中叶子结点的个数是多少分析二叉树的公式 nn0n1n2n0n1n0-12*n0n1-1。而在完全二叉树中 n1只能取 0 或 1。 若 n11 则 2*n01001 可推出 n0 为小数 不符合题意 若 n10 则 2*n0-11001则 n0501。所以答案为 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 arrayToTreearr 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 arrayToTreearr start mid - 1 //递归的用右半部分数组构造 root 的右子树 root.rChild arrayToTreearr mid 1 end } else { root null } return root } /** 用中序遍历的方式打印出二叉树结点的内容 */ fun printTreeMidOrderroot BiTNode { if root null return //遍历 root 结点的左子树 if root.lChild null printTreeMidOrderroot.lChild //遍历 root 结点 print${root.data} //遍历 root 结点的右子树 if root.rChild null printTreeMidOrderroot.rChild } fun mainargs ArrayString { val arr intArrayOf1 2 3 4 5 6 7 8 9 10 print数组 arr.indices.forEach { i -print${arr[i]} } println val root BiTNode root arrayToTreearr 0 arr.size - 1 print转换成树的中序遍历为 printTreeMidOrderroot println }程序的运行结果如下数组 1 2 3 4 5 6 7 8 9 10转换成树的中序遍历为1 2 3 4 5 6 7 8 9 10算法性能分析由于这种方法只遍历了一次数组因此算法的时间复杂度为 ON其中 N 表示的是数组长度。