4.21 如何求解迷宫问题【出自 YMX 笔试题】难度系数★★★★☆ 题目描述被考察系数★★★★☆给定一个大小为 N×N 的迷宫一只老鼠需要从迷宫的左上角对应矩阵的[0][0]走到迷宫的右下角对应矩阵的[N-1][N-1]老鼠只能向两个方向移动向右或向下。在迷宫中 0 表示没有路是死胡同 1 表示有路。例如给定下面的迷宫图中标粗的路径就是一条合理的路径。请给出算法来找到这样一条合理路径。分析与解答最容易想到的方法就是尝试所有可能的路径找出可达的一条路。显然这种方法效率非常低这里重点介绍一种效率更高的回溯法。主要思路为当碰到死胡同的时候回溯到前一步然后从前一步出发继续寻找可达的路径。算法的主要框架如下申请一个结果矩阵来标记移动的路径if 到达了目的地打印解决方案矩阵else 1在结果矩阵中标记当前为 1 1 表示移动的路径。 2向右前进一步然后递归地检查走完这一步后判断是否存在到终点的可达的路线。 3如果步骤 2中的移动方法导致没有通往终点的路径那么选择向下移动一步然后检查使用这种移动方法后是否存在到终点的可达的路线。 4如果上面的移动方法都会导致没有可达的路径那么标记当前单元格在结果矩阵中为 0返回 false并回溯到前一步中。根据以上框架很容易进行代码实现。示例代码如下class Maze { val N 4 /* 打印从起点到终点的路线 */ fun printSolutionsol ArrayIntArray { for i in 0 until N { for j in 0 until N printsol[i][j].toString println } } /* 判断 x 和 y 是否是一个合理的单元 */ private fun isSafemaze ArrayIntArray x Int y Int Boolean { return x in 0..N - 1 y 0 y N maze[x][y] 1 } /* * 使用回溯的方法找到一条从左上角到右下角的路径 * maze 表示迷宫 x、 y 表示起点 sol 存储结果 */ fun getPathmaze ArrayIntArray x Int y Int sol ArrayIntArray Boolean { /* 到达目的地 */ if x N - 1 y N - 1 { sol[x][y] 1 return true } /* 判断 maze[x][y]是否是一个可走的单元 */ if isSafemaze x y { /* 标记当前单元为 1 */ sol[x][y] 1 /* 向右走一步 */ if getPathmaze x 1 y sol return true /* 向下走一步 */ if getPathmaze x y 1 sol return true /* 标记当前单元为 0 用来表示这条路不可行然后回溯 */ sol[x][y] 0 return false } return false } } fun mainargs ArrayString { val rat Maze val maze arrayOfintArrayOf1 0 0 0 intArrayOf1 1 0 1 intArrayOf0 1 0 0 intArrayOf1 1 1 1 val sol arrayOfintArrayOf0 0 0 0 intArrayOf0 0 0 0 intArrayOf0 0 0 0 intArrayOf0 0 0 0 if rat.getPathmaze 0 0 sol { print不存在可达的路径 } else { rat.printSolutionsol } } 程序的运行结果如下 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 14.22 如何从三个有序数组中找出它们的公共元素【出自 YMX 笔试题】难度系数★★★★☆ 被考察系数★★★☆☆题目描述给定以非递减顺序排序的三个数组找出这三个数组中的所有公共元素。例如给出下面三个数组 ar1[] {2 5 12 20 45 85} ar2[] {16 19 20 85 200} ar3[] {3 4 15 20 39 72 85 190} 。那么这三个数组的公共元素为 {20 85}。分析与解答最容易想到的方法是首先找出两个数组的交集然后再把这个交集存储在一个临时数组中最后再找出这个临时数组与第三个数组的交集。这种方法的时间复杂度为 ON1 N2 N3其中 N1、 N2 和 N3 分别为三个数组的大小。这种方法不仅需要额外的存储空间而且还需要额外的两次循环遍历。下面介绍另外一种只需要一次循环遍历、而且不需要额外存储空间的方法主要思路如下假设当前遍历的三个数组的元素分别为 ar1[i]、 ar2[j]和 ar3[k]则存在以下几种可能性 1如果 ar1[i]、 ar2[j]和 ar3[k]相等则说明当前遍历的元素是三个数组的公有元素可以直接打印出来然后通过执行 i j k使三个数组同时向后移动此时继续遍历各数组后面的元素。 2如果 ar1[i]ar2[j]则执行 i来继续遍历 ar1 中后面的元素因为 ar1[i]不可能是三个数组公有的元素。 3如果 ar2[j]ar3[k]同理可以通过 j来继续遍历 ar2 后面的元素。 4如果前面的条件都不满足说明 ar1[i]ar2[j]而且 ar2[j]ar3[k]此时可以通过 k来继续遍历 ar3 后面的元素。实现代码如下fun findCommonar1 IntArray ar2 IntArray ar3 IntArray { var i 0 var j 0 var k 0 val n1 ar1.size val n2 ar2.size val n3 ar3.size /* 遍历三个数组 */ while i n1 j n2 k n3 { /* 找到了公有的元素 */ if ar1[i] ar2[j] ar2[j] ar3[k] { print${ar1[i]} i j k } else if ar1[i] ar2[j] i else if ar2[j] ar3[k] j else k/* ar3[k]不可能是共有的元素 *//* ar2[j]不可能是共有的元素 *//* ar[i]不可能是 共有的元素 */ } } fun mainargs ArrayString { val ar1 intArrayOf2 5 12 20 45 85 val ar2 intArrayOf16 19 20 85 200 val ar3 intArrayOf3 4 15 20 39 72 85 190 findCommonar1 ar2 ar3 } 程序的运行结果如下 20 85算法性能分析这种方法的时间复杂度为 ON1 N2 N3。4.23 如何求两个有序集合的交集【出自 WY 笔试题】难度系数★★★★☆ 题目描述被考察系数★★★★☆有两个有序的集合集合中的每个元素都是一段范围求其交集例如集合{[48][913]}和{[612]}的交集为{[68][912]}。分析与解答方法一蛮力法最简单的方法就是遍历两个集合针对集合中的每个元素判断是否有交集如果有则求出它们的交集实现代码如下data class MySetvar min Int var max Int private fun getIntersections1 MySet s2 MySet MySet { return when { s1.min s2.min -when { s1.max s2.min -null s1.max s2.max - MySets2.min s1.max else - MySets2.min s2.max } s1.min s2.max -when { s1.max s2.max - MySets1.min s1.max else - MySets1.min s2.max } else -null } } fun getIntersectionl1 ArrayListMySet l2 ArrayListMySet ArrayListMySet { val result ArrayListMySet for i in l1.indices for j in l2.indices { val s getIntersectionl1[i] l2[j] if s null result.adds } return result } fun mainargs ArrayString { val l1 ArrayListMySet val l2 ArrayListMySet l1.addMySet4 8 l1.addMySet9 13 l2.addMySet6 12 val result getIntersectionl1 l2 for i in result.indices println[${result[i].min} ${result[i].max}] } 代码运行结果如下 [68] [912]算法性能分析这种方法的时间复杂度为 On^2。方法二特征法上述这种方法显然没有用到集合有序的特点因此它不是最佳的方法。假设两个集合为 s1 和 s2。当前比较的集合为 s1[i]和 s2[j]其中 i 与 j 分别表示的是集合 s1 与 s2 的下标。可以分为如下几种情况1 s1 集合的下界小于 s2 的上界 S1[i] _________S2[j] _________在这种情况下 s1[i]和 s2[j]显然没有交集那么接下来只有 s1[i1]与 s2[j]才有可能会有交集。2 s1 的上界介于 s2 的下界与上界之间S1[i] _________ S2[j] _________在这种情况下 s1[i]和 s2[j]有交集 s2[j]的下界和 s1[i]的上界那么接下来只有 s1[i1]与 s2[j]才有可能会有交集。3 s1 包含 s2S1[i] ___________________ S2[j] _________在这种情况下 s1[i]和 s2[j]有交集交集为 s2[j]那么接下来只有 s1[i]与 s2[j1]才有可能会有交集。4 s2 包含 s1S1[i] _________ S2[j] ______________在这种情况下 s1[i]和 s2[j]有交集交集为 s1[i]那么接下来只有 s1[i1]与 s2[j]才有可能会有交集。5 s1 的下界介于 s2 的下界与上界之间S1[i] _______________ S2[j] _____________在这种情况下 s1[i]和 s2[j]有交集交集为 s1[i]的下界和 s2[j]的上界那么接下来只有s1[i]与 s2[j1]才有可能会有交集。6 s2 的上界小于 s1 的下界 S1[i] _______ S2[j] _________在这种情况下 s1[i]和 s2[j]显然没有交集那么接下来只有 s1[i]与 s2[j1]才有可能会有交集。根据以上分析给出实现代码如下fun getIntersectionl1 ListMySet l2 ListMySet ListMySet { val result mutableListOfMySet var i 0 var j 0 while i l1.size j l2.size { val s1 l1[i] val s2 l2[j] if s1.min s2.min { when { s1.max s2.min - i s1.max s2.max - { result.addMySets2.min s1.max i } else - { result.addMySets2.min s2.max j } } } else if s1.min s2.max { if s1.max s2.max { result.addMySets1.min s1.max i } else { result.addMySets1.min s2.max j } } else { j } } return result } fun mainargs ArrayString { val l1 mutableListOfMySet val l2 mutableListOfMySet l1.addMySet4 8 l1.addMySet9 13 l2.addMySet6 12 val result getIntersectionl1 l2 for i in result.indices println[${result[i].min} ${result[i].max}] }算法性能分析这种方法的时间复杂度为 On1n2其中 n1、 n2 分别为两个集合的大小。