赞
踩
【题目】给定一个经过任意位数的旋转后的排序数组,判断某个数是否在里面。
例如,对于一个给定数组 {4, 5, 6, 7, 0, 1, 2},它是将一个有序数组的前三位旋转地放在了数组末尾。假设输入的 target 等于 0,则输出答案是 4,即 0 所在的位置下标是 4。如果输入 3,则返回 -1。
【解析】 这道题目依旧是按照解决代码问题的方法论的步骤进行分析。
先做复杂度分析
这个问题就是判断某个数字是否在数组中,因此,复杂度极限就是全部遍历地去查找,也就是 O(n) 的复杂度。
接着,进入定位问题的环节中
这个问题有很多关键字,因此能够让你立马锁定问题。例如,判断某个数是否在数组里面,这就是一个查找问题。
然后,我们来做数据操作分析
原数组是经过某些处理的排序数组,也就是说原数组是有序的。有序和查找,你就会很快地想到,这个问题极有可能用二分查找的方式去解决,时间复杂度是 O(logn),相比上面 O(n) 的基线也是有显著的提高。
在利用二分查找时,更多的是判断,基本没有数据的增删操作,因此不需要太多地定义复杂的数据结构。
分析到这里,解决方案已经非常明朗了,就是采用二分查找的方法,在 O(logn) 的时间复杂度下去解决这个问题。二分查找可以通过递归来实现。而每次递归的关键点在于,根据切分的点(最中间的那个数字),确定是向左走还是向右走。这也是这个例题中唯一的难点了。
试想一下,在一个旋转后的有序数组中,利用中间元素作为切分点得到的两个子数组有什么样的性质。经过枚举不难发现,这两个子数组中,一定存在一个数组是有序的。也可能出现一个极端情况,二者都是有序的。如下图所示:
对于有序的一边,我们是很容易判断目标值,是否在这个区间内的。如果在其中,也说明了目标值不在另一边的旋转有序组里;反之亦然。
当我们知道了目标值在左右哪边之后,就可以递归地调用旋转有序的二分查找了。之所以可以递归调用,是因为,对于旋转有序组,这个问题和原始问题完全一致,可以调用。对于有序组,它是旋转有序的特殊情况(即旋转 0 位),也一定是可以通过递归的方法去实现查找的。直到不断二分后,搜索空间只有 1 位数字,直接判断是否找到即可。
最后,实现代码
我们给出这个例子的实现代码,如下:
public static void main(String[] args) { int[] arr = { 4, 5, 6, 7, 0, 1, 2 }; int target = 7; System.out.println(bs(arr, target, 0, arr.length-1)); } private static int bs(int[] arr, int target, int begin, int end) { if (begin == end) { if (target == arr[begin]){ return begin; } else{ return -1; } } int middle = (begin + end)/2; if (target == arr[middle]) { return middle; } if (arr[begin] <= arr[middle-1]){ if (arr[begin] <= target && target <= arr[middle-1]) { return bs(arr,target, begin,middle-1); } else { return bs(arr,target, middle+1,end); } } else { if (arr[middle+1] <= target && target <= arr[end]) { return bs(arr,target, middle+1,end); } else { return bs(arr,target, begin,middle-1); } } }
对代码进行解读:
主函数中,第 2 到 4 行。定义数组和 target,并且执行二分查。二分查找包括两部分,其一是二分策略,其二是终止条件。
二分策略在代码的 16~33 行:
【题目】输入两个字符串,用动态规划的方法,求解出最大公共子串。
例如,输入 a = “13452439”, b = “123456”。由于字符串"345"同时在 a 和 b 中出现,且是同时出现在 a 和 b 中的最长的子串。因此输出"345"。
【解析】这里已经定义了问题,就是寻找最大公共子串。同时也定义了方法,就是要用动态规划的方法。那么我们也不需要做太多的分析,只要依赖动态规划的步骤完成就可以了。
首先,我们回顾一下先前学过的最短路径问题。在最短路径问题中,我们是定义了起点和终点后,再去寻找二者之间的最短路径。
而现在的最大公共子串问题是,所有相邻的字符距离都是 1,在不确定起点和终点时,我们需要去寻找起点和终点之间最远的距离。
如果要基于已有的知识来探索陌生问题,那就需要根据每个可能的公共子串起点,去寻找与之对应的最远终点。这样就能得到全部的子串。随后再从中找到最大的那个子串。
别忘了,动态规划的基本方法是:分阶段、找状态、做决策、状态转移方程、定目标、寻找终止条件。下面我们来具体分析一下动态规划的步骤:
这段分析对于初学者来说会非常难懂,接下来我们给一个实现的流程来辅助你理解。
在最短路径问题中,曾重点提到的一个难点是,对于输入的图,采用什么样的数据结构予以保存。最终我们选择了二维数组。
在这个例子中也可以采用二维数组。每一行或每一列就对应了输入字符串 a 和 b 的每个字符,即 6 x 8 的二维数组(矩阵)为:
接着,每个可能的起点字符,都应该同时出现在字符串 a 和 b 中,例如"1"就是一个可能的起点。如果以"1"作为起点,那么它后面的字符就是阶段,显然下个阶段就是 a[1] = 3 和 b[1] = 2。而此时的状态就是当前的公共子串,即 “1”。
决策的结果是,下一个阶段是否进入到公共子串中。很显然 a[1] 不等于 b[1],因此决策的结果是不进入。这也同时命中了终止条件。如果以"3"起点,则因为它之后的 a[2] 等于 b[3],则决策结果是进入到公共子串。
因此状态转移方程 sk+1 = uk(sk),含义是在"3"的状态下决策"4"进入子串,结果得到"34"。我们的目标是寻找最大的公共子串,因此可以用从 1 开始的数字定义距离(子串的长度)。具体步骤如下:
对于每个可能的起点,距离都是 1 (不可能的起点置为 0,图中忽略未写)。则有:
接着利用状态转移方程,去寻找最优子结构。也就是,如果 b[i] = a[j],则 m[i,j] = m[i-1,j-1] + 1。含义为,如果决策结果是相等,则状态增加一个新的字符,进行更新。可以得到:
最终,检索这个矩阵,得到的最大数字就是最大公共子串的长度。根据其所在的位置,就能从 a 或 b 中找到最大公共子串。
代码如下:
public static void main(String[] args) { String a = "13452439"; String b = "123456"; getCommenStr(a, b); } public static void getCommenStr(String a, String b) { char[] c1 = a.toCharArray(); char[] c2 = b.toCharArray(); int[][] m = new int[c2.length+1][c1.length+1]; for (int i = 1; i <= c2.length; i++) { for (int j = 1; j <= c1.length; j++) { if (c2[i - 1] == c1[j - 1]) m[i][j] = m[i - 1][j - 1] + 1; } } int max = 0; int index = 0; for (int i = 0; i < c2.length; i++) { for (int j = 0; j < c1.length; j++) { if (m[i][j] > max) { max = m[i][j]; index = i; } } } String s = ""; for (int i = index - max; i < index; i++) s += b.charAt(i); System.out.println(s); }
下面对代码进行解读:
主函数中定义了字符串 a 和字符串 b,随后调用动态规划代码。
进入 getCommenStr() 函数中之后,首先在第 10 行定义了二维数组。此时二维数组的维数是 7 x 9 的。这主要的原因是,后续会需要用到第一行和第一列的全零向量,作为起始条件。
接着,在第 11~16 行,利用双重循环去完成状态转移的计算。此时就得到了最关键的矩阵,如下所示:
随后的 17~26 行,我们从矩阵 m 中,找到了最大值为 3,在字符串 b 中的索引值为 4(此时 index 为 5,但别忘了我们之前额外定义了一行/一列的全零向量)。
最后,27~30 行,我们根据终点字符串索引值 4 和最大公共子串长度 3,就能找到最大公共子串在 b 中的 2~4 的位置。即 “345”。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。