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

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 printSolution（sol： Array<IntArray>） { for （i in 0 until N） { for （j in 0 until N） print（sol[i][j].toString（） + " "） println（） } } /* 判断 x 和 y 是否是一个合理的单元 */ private fun isSafe（maze： Array<IntArray>， x： Int， y： Int）： Boolean { return x in 0..（N - 1） && y >= 0 && y <N && maze[x][y] == 1 } /* * 使用回溯的方法找到一条从左上角到右下角的路径 * maze 表示迷宫， x、 y 表示起点， sol 存储结果 */ fun getPath（maze： Array<IntArray>， x： Int， y： Int， sol： Array<IntArray>）： Boolean { /* 到达目的地 */ if （x == N - 1 && y == N - 1） { sol[x][y] = 1 return true } /* 判断 maze[x][y]是否是一个可走的单元 */ if （isSafe（maze， x， y）） { /* 标记当前单元为 1 */ sol[x][y] = 1 /* 向右走一步 */ if （getPath（maze， x + 1， y， sol）） return true /* 向下走一步 */ if （getPath（maze， x， y + 1， sol）） return true /* 标记当前单元为 0 用来表示这条路不可行，然后回溯 */ sol[x][y] = 0 return false } return false } } fun main（args： Array<String>） { val rat = Maze（） val maze = arrayOf（intArrayOf（1， 0， 0， 0）， intArrayOf（1， 1， 0， 1）， intArrayOf（0， 1， 0， 0）， intArrayOf（1， 1， 1， 1）） val sol = arrayOf（intArrayOf（0， 0， 0， 0）， intArrayOf（0， 0， 0， 0）， intArrayOf（0， 0， 0， 0）， intArrayOf（0， 0， 0， 0）） if （！rat.getPath（maze， 0， 0， sol）） { print（"不存在可达的路径"） } else { rat.printSolution（sol） } } 程序的运行结果如下： 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1

4.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}。

分析与解答：

最容易想到的方法是首先找出两个数组的交集，然后再把这个交集存储在一个临时数组中，最后再找出这个临时数组与第三个数组的交集。这种方法的时间复杂度为 O（N1 + 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 findCommon（ar1： 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 main（args： Array<String>） { val ar1 = intArrayOf（2， 5， 12， 20， 45， 85） val ar2 = intArrayOf（16， 19， 20， 85， 200） val ar3 = intArrayOf（3， 4， 15， 20， 39， 72， 85， 190） findCommon（ar1， ar2， ar3） } 程序的运行结果如下： 20 85

算法性能分析：

这种方法的时间复杂度为 O（N1 + N2 + N3）。

4.23 如何求两个有序集合的交集

【出自 WY 笔试题】

有两个有序的集合，集合中的每个元素都是一段范围，求其交集，例如集合{[4，8]，[9，13]}和{[6，12]}的交集为{[6，8]，[9，12]}。

分析与解答：方法一：蛮力法

最简单的方法就是遍历两个集合，针对集合中的每个元素判断是否有交集，如果有，则求出它们的交集，实现代码如下：

data class MySet（var min： Int， var max： Int） private fun getIntersection（s1： MySet， s2： MySet）： MySet？ { return when { s1.min < s2.min ->when { s1.max < s2.min ->null s1.max <= s2.max -> MySet（s2.min， s1.max） else -> MySet（s2.min， s2.max） } s1.min <= s2.max ->when { s1.max <= s2.max -> MySet（s1.min， s1.max） else -> MySet（s1.min， s2.max） } else ->null } } fun getIntersection（l1： ArrayList<MySet>， l2： ArrayList<MySet>）： ArrayList<MySet> { val result = ArrayList<MySet>（） for （i in l1.indices） for （j in l2.indices） { val s = getIntersection（l1[i]， l2[j]） if （s ！= null） result.add（s） } return result } fun main（args： Array<String>） { val l1 = ArrayList<MySet>（） val l2 = ArrayList<MySet>（） l1.add（MySet（4， 8）） l1.add（MySet（9， 13）） l2.add（MySet（6， 12）） val result = getIntersection（l1， l2） for （i in result.indices） println（"[${result[i].min}， ${result[i].max}] "） } 代码运行结果如下： [6，8] [9，12]

算法性能分析：

这种方法的时间复杂度为 O（n^2）。方法二：特征法

上述这种方法显然没有用到集合有序的特点，因此，它不是最佳的方法。假设两个集合为 s1 和 s2。当前比较的集合为 s1[i]和 s2[j]，其中， i 与 j 分别表示的是集合 s1 与 s2 的下标。可以分为如下几种情况：

1） s1 集合的下界小于 s2 的上界： S1[i] _________

S2[j] _________

在这种情况下， s1[i]和 s2[j]显然没有交集，那么接下来只有 s1[i+1]与 s2[j]才有可能会有交集。

2） s1 的上界介于 s2 的下界与上界之间：

S1[i] _________ S2[j] _________

在这种情况下， s1[i]和 s2[j]有交集（ s2[j]的下界和 s1[i]的上界），那么接下来只有 s1[i+1]与 s2[j]才有可能会有交集。

3） s1 包含 s2：

S1[i] ___________________ S2[j] _________

在这种情况下， s1[i]和 s2[j]有交集（交集为 s2[j]），那么接下来只有 s1[i]与 s2[j+1]才有可能会有交集。4） s2 包含 s1：

S1[i] _________ S2[j] ______________

在这种情况下， s1[i]和 s2[j]有交集（交集为 s1[i]），那么接下来只有 s1[i+1]与 s2[j]才有可能会有交集。

5） s1 的下界介于 s2 的下界与上界之间：

S1[i] _______________ S2[j] _____________

在这种情况下， s1[i]和 s2[j]有交集（交集为 s1[i]的下界和 s2[j]的上界），那么接下来只有s1[i]与 s2[j+1]才有可能会有交集。

6） s2 的上界小于 s1 的下界： S1[i] _______ S2[j] _________

在这种情况下， s1[i]和 s2[j]显然没有交集，那么接下来只有 s1[i]与 s2[j+1]才有可能会有交集。

根据以上分析给出实现代码如下：

fun getIntersection（l1： List<MySet>， l2： List<MySet>）： List<MySet> { val result = mutableListOf<MySet>（） 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.add（MySet（s2.min， s1.max）） i++ } else -> { result.add（MySet（s2.min， s2.max）） j++ } } } else if （s1.min <= s2.max） { if （s1.max <= s2.max） { result.add（MySet（s1.min， s1.max）） i++ } else { result.add（MySet（s1.min， s2.max）） j++ } } else { j++ } } return result } fun main（args： Array<String>） { val l1 = mutableListOf<MySet>（） val l2 = mutableListOf<MySet>（） l1.add（MySet（4， 8）） l1.add（MySet（9， 13）） l2.add（MySet（6， 12）） val result = getIntersection（l1， l2） for （i in result.indices） println（"[${result[i].min}， ${result[i].max}] "） }

算法性能分析：

这种方法的时间复杂度为 O（n1+n2），其中 n1、 n2 分别为两个集合的大小。