昌做网站,wap文字游戏搭建教程,电商网站开发模版,最近国际重大新闻事件20225.20 如何在二维数组中寻找最短路线【出自 TX 面试题】难度系数#xff1a;★★★★☆ 题目描述#xff1a;被考察系数#xff1a;★★★★☆寻找一条从左上角#xff08; arr[0][0]#xff09;到右下角#xff08; arr[m-1][n-1]#xff09;的路线#xff0c;使得沿途…5.20 如何在二维数组中寻找最短路线【出自 TX 面试题】难度系数★★★★☆ 题目描述被考察系数★★★★☆寻找一条从左上角 arr[0][0]到右下角 arr[m-1][n-1]的路线使得沿途经过的数组中的整数的和最小。分析与解答对于这道题可以从右下角开始倒着来分析这个问题最后一步到达 arr[m-1][n-1]只有两条路通过 arr[m-2][n-1]到达或通过 arr[m-1][n-2]到达假设从 arr[0][0]到 arr[m-2][n-1]沿途数组最小值为 fm-2n-1到 arr[m-1][n-2] 沿途数组最小值为 fm-1n-2。因此最后一步选择的路线为 min{fm-2n-1 fm-1n-2}。同理选择到 arr[m-2][n-1]或 arr[m-1][n-2]的路径可以采用同样的方式来确定。由此可以推广到一般的情况。假设到 arr[i-1][j]与 arr[i][j-1]的最短路径的和为 fi-1j和fij-1那么到达 arr[i][j]的路径的上所有数字和的最小值为 fijmin{ fi-1j fij-1} arr[i][j]。方法一递归法根据这个递归公式可知 可以采用递归的方法来实现 递归的结束条件为遍历到 arr[0][0]。在求解的过程中还需要考虑另外一种特殊情况遍历到 arr[i][j]当 i0 或 j0的时候只能沿着一条固定的路径倒着往回走直到 arr[0][0]。根据这个递归公式与递归结束条件可以给出实现代码如下fun getMinPatharr ArrayIntArray i Int j Int Int { //倒着走到了第一个结点递归结束 return if i 0 j 0 arr[i][j] else if i 0 j 0 arr[i][j] Math.mingetMinPatharr i - 1 j getMinPatharr i j - 1 else if i 0 j 0 arr[i][j] getMinPatharr i - 1 j else arr[i][j] getMinPatharr i j - 1//j 0 i 0 //下面两个条件只有一条路径可选 //选取两条可能路径上的最小值 } fun getMinPatharr ArrayIntArray Int { return if arr null || arr.isEmpty 0 else getMinPatharr arr.size - 1 arr[0].size - 1 } fun mainargs ArrayString { val arr arrayOfintArrayOf1 4 3 intArrayOf8 7 5 intArrayOf2 1 5 printlngetMinPatharr } 程序的运行结果如下 1这种方法虽然能得到题目想要的结果但是效率太低主要是因为里面有大量的重复计算过程比如在计算 fi-1j与 fj-1i的过程中都会计算 fi-1j-1。如果把第一次计算得到的fi-1j-1缓存起来就不需要额外的计算了而这也是典型的动态规划的思路下面重点介绍动态规划方法。方法 2动态规划法动态规划法其实也是一种空间换时间的算法通过缓存计算中间值从而减少重复计算的次数从而提高算法的效率。方法 1 从 arr[m-1][n-1]开始逆向通过递归来求解而动态规划要求正向求解以便利用前面计算出来的结果。对于本题而言显然 fi0arr[0][0]…arr[i][0] f[0j] arr[0][0]…arr[0][j]。根据递推公式 fijmin{ fi-1j fij-1} arr[i][j]从 i1 j1 开始顺序遍历二维数组可以在遍历的过程中求出所有的 fij的值同时把求出的值保存到另外一个二维数组中以供后续使用。当然在遍历的过程中可以确定这个最小值对应的路线在这种方法中除了求出最小值以外顺便还打印出了最小值的路线实现代码如下fun getMinPatharr ArrayIntArray Int { if arr.isEmpty return 0 val row arr.size val col arr[0].size //用来保存计算的中间值 val cache Arrayrow { IntArraycol } cache[0][0] arr[0][0] for i in 1 until col { cache[0][i] cache[0][i - 1] arr[0][i] } for j in 1 until row { cache[j][0] cache[j - 1][0] arr[j][0] } //在遍历二维数组的过程中不断把计算结果保存到 cache 中 for i in 1 until row { for j in 1 until col { //可以确定选择的路线为 arr[i][j-1] if cache[i - 1][j] cache[i][j - 1] { cache[i][j] cache[i][j - 1] arr[i][j] print[$i${j - 1}] } else { cache[i][j] cache[i - 1][j] arr[i][j] print[${i - 1}$j] }//可以确定选择的路线为 arr[i-1][j] } } println[${row - 1}${col - 1}] return cache[row - 1][col - 1] } 程序的运行结果如下 路径 [01] [02] [20] [21] [22] 最小值为 17算法性能分析这种方法对二维数组进行了一次遍历因此其时间复杂度为 Om*n。此外由于这种方法同样申请了一个二维数组来保存中间结果因此其空间复杂度也为 Om*n。5.21 如何截取包含中文的字符串【出自 MT 面试题】难度系数★★★☆☆ 题目描述被考察系数★★★☆☆编写一个截取字符串的函数输入为一个字符串和字节数输出为按字节截取的字符串。但是要保证汉字不被截半个例如人 ABC4应该截为人 AB输入人 ABC 们 DEF 6应该输出为人 ABC而不是人 ABC们的半个。fun truncateStrstr String len Int String { if str.isBlank return val chrArr str.toCharArray var sb StringBuilder var count 0 //用来记录当前截取字符的长度 for cc in chrArr { if count len { if isChinesecc { //如果要求截取子串的长度只差一个字符但是接下来的字符是中文 //则截取结果子串中不保存这个中文字符 if count 1 len return sb.toString count 2 sb sb.appendcc } else { count 1 sb sb.appendcc } } else { break } } return sb.toString } //判断字符 c 是否是中文字符如果是返回 true fun isChinesec Char Boolean { val sb c.toString return sb.toByteArray.size 1 } fun mainargs ArrayString { val sb 人 ABC 们 DEF printlntruncateStrsb 6 } 程序的运行结果如下 人 ABC5.22 如何求相对路径【出自 SLL 笔试题】难度系数★★★☆☆ 题目描述被考察系数★★★☆☆编写一个函数根据两个文件的绝对路径算出其相对路径。例如a/qihoo/app/a/b/c/d/new.cb/qihoo/app/1/2/test.c那么 b 相对于 a 的相对路径是../../../../1/2/test.c分析与解答首先找到两个字符串相同的路径 /aihoo/app然后处理不同的目录结构 a/a/b/c /d/new.cb/1/2/test.c。处理方法为对于 a 中的每一个目录结构在 b 前面加“../”对于本题而言除了相同的目录前缀外 a 还有四级目录 a/b/c/d因此只需要在 b /1/2/test.c前面增加四个../得到的../../../../1/2/test.c就是 b 相对 a 的路径。实现代码如下fun getRelativePathpath1 String path2 String String { if path1 null || path2 null { println参数不合法\n return null } var relativePath //用来指向两个路径中不同目录的起始路径 var diff1 0 var diff2 0 var i 0 var j 0 val len1 path1.length val len2 path2.length while i len1 j len2 { //如果目录相同则往后遍历 if path1[i] path2[j] { if path1[i] / { diff1 i diff2 j } i j } else // 不同的目录 { //把 path1 非公共部分的目录转换为../ diff1 //跳过目录分隔符/ while diff1 len1 { //碰到下一级目录 if path1[diff1] / { relativePath ../ } diff1 } //把 path2 的非公共部分的路径加到后面 diff2 relativePath path2.substringdiff2 break } } return relativePath } fun mainargs ArrayString { val path1 /qihoo/app/a/b/c/d/new.c val path2 /qihoo/app/1/2/test.c printlngetRelativePathpath1 path2 } 程序的运行结果如下 ../../../../1/2/test.c算法性能分析这种方法的时间复杂度与空间复杂度都为 Omaxmn其中 m 和 n 分别为两个路径的长度。5.23 如何查找到达目标词的最短链长度【出自 JD 面试题】难度系数★★★☆☆ 题目描述被考察系数★★★☆☆给定一个字典和两个长度相同的“开始”和“目标”的单词。找到从“开始”到“目标”最小链的长度。如果它存在那么这条链中的相邻单词只有一个字符不同而链中的每个单词都是有效的单词即它存在于字典中。可以假设词典中存在“目标”字所有词典词的长度相同。例如给定一个单词字典为{pooN pbcc zamc poIc pbca pbIc poIN} start TooNtarget pbca输出结果为 7因为 TooNstart- pooN - poIN - poIc - pbIc - pbcc - pbcatarget。分析与解答本题主要的解决方法是使用 BFS 的方式从给定的字符串开始遍历所有相邻两个单词只有一个不同的字符的单词直到遍历找到目标单词或者遍历完所有的单词为止。实现代码如下import java.util.* /* 用来存储单词链的队列 */ class QItemvar word String var len Int /* 判断两个字符串是否只有一个不同的字符 */ fun isAdjacenta String b String Boolean { var diff 0 val len a.length for i in 0 until len { if a[i] b[i] diff if diff 1 return false } return diff 1 } /* 返回从 start 到 target 的最短链 */ fun shortestChainLenstart String target String D MutableSetString Int { val q ArrayDequeQItem val item QItemstart 1 q.additem /*把第一个字符串添加进来*/ while q.isEmpty { val curr q.peek q.removeFirst val it D.iterator while it.hasNext { val temp it.next /*如果这两个字符串只有一个字符不同*/ if isAdjacentcurr.word temp { item.word temp item.len curr.len 1 q.pushitem /*把这个字符串放入到队列中*/ /* 把这个字符串从队列中删除以避免被重复遍历 */ it.remove /* 通过转变后得到了目标字符*/ if temp target return item.len } } } return 0 } fun mainargs ArrayString { val d HashSetString d.addpooN d.addpbcc d.addzamc d.addpoIc d.addpbca d.addpbIc d.addpoIN val start TooN val target pbca println最短的链条的长度为 shortestChainLenstart target d } 程序的运行结果为 最短的链条的长度为 7算法性能分析这种方法的时间复杂度为为 On²m其中 n 为单词的个数 m 为字符串的长度。