合肥市网站建设公司,wordpress开发网站,织梦网站防黑怎么做,广州影视制作公司一、题目
基因序列可以表示为一条由8个字符组成的字符串#xff0c;其中每个字符都是A、C、G和T之一。假设我们需要调查从基因序列start变为end所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如#xff0c;AACCGGTT -- AACCGGTA就是一…一、题目
基因序列可以表示为一条由8个字符组成的字符串其中每个字符都是A、C、G和T之一。假设我们需要调查从基因序列start变为end所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如AACCGGTT -- AACCGGTA就是一次基因变化。 另有一个基因库 bank 记录了所有有效的基因变化只有基因库中的基因才是有效的基因序列。变化后的基因必须位于基因库bank中。给你两个基因序列start和end以及一个基因库bank请你找出并返回能够使start变化为end所需的最少变化次数。如果无法完成此基因变化返回-1。
注意起始基因序列start默认是有效的但是它并不一定会出现在基因库中。
示例 1 输入start AACCGGTT, end AACCGGTA, bank [AACCGGTA] 输出1
示例 2 输入start AACCGGTT, end AAACGGTA, bank [AACCGGTA,AACCGCTA,AAACGGTA] 输出2
示例 3 输入start AAAAACCC, end AACCCCCC, bank [AAAACCCC,AAACCCCC,AACCCCCC] 输出3 start.length 8 end.length 8 0 bank.length 10 bank[i].length 8 start、end和bank[i]仅由字符[A, C, G, T]组成 二、代码
【1】广度优先搜索 经过分析可知题目要求将一个基因序列A变化至另一个基因序列B需要满足以下条件 1、序列A与 序列B之间只有一个字符不同 2、变化字符只能从A, C, G, T中进行选择 3、变换后的序列B一定要在字符串数组bank中。
根据以上变换规则我们可以进行尝试所有合法的基因变化并找到最小的变换次数即可。步骤如下 1、如果start与end相等此时直接返回0如果最终的基因序列不在bank中则此时按照题意要求无法生成直接返回−1 2、首先我们将可能变换的基因 sss 从队列中取出按照上述的变换规则尝试所有可能的变化后的基因比如一个AACCGGTA我们依次尝试改变基因s的一个字符并尝试所有可能的基因变化序列s0,s1,s2,⋯,si,⋯,s23变化一次最多可能会生成3×824种不同的基因序列。 3、我们需要检测当前生成的基因序列的合法性si首先利用哈希表检测si 是否在数组bank中如果是则认为该基因合法否则改变化非法直接丢弃其次我们还需要用哈希表记录已经遍历过的基因序列如果该基因序列已经遍历过则此时直接跳过如果合法且未遍历过的基因序列则我们将其加入到队列中。 4、如果当前变换后的基因序列与end相等则此时我们直接返回最小的变化次数即可如果队列中所有的元素都已经遍历完成还无法变成end则此时无法实现目标变化返回−1。
class Solution {public int minMutation(String start, String end, String[] bank) {SetString cnt new HashSetString();SetString visited new HashSetString();char[] keys {A, C, G, T}; for (String w : bank) {cnt.add(w);}if (start.equals(end)) {return 0;}if (!cnt.contains(end)) {return -1;}QueueString queue new ArrayDequeString();queue.offer(start);visited.add(start);int step 1;while (!queue.isEmpty()) {int sz queue.size();for (int i 0; i sz; i) {String curr queue.poll();for (int j 0; j 8; j) {for (int k 0; k 4; k) {if (keys[k] ! curr.charAt(j)) {StringBuffer sb new StringBuffer(curr);sb.setCharAt(j, keys[k]);String next sb.toString();if (!visited.contains(next) cnt.contains(next)) {if (next.equals(end)) {return step;}queue.offer(next);visited.add(next);}}}}}step;}return -1;}
}时间复杂度 O(C×n×m)其中n为基因序列的长度m为数组bank的长度。对于队列中的每个合法的基因序列每次都需要计算C×n种变化在这里C4队列中最多有m个元素因此时间复杂度为O(C×n×m)。 空间复杂度 O(n×m)其中n为基因序列的长度m为数组bank的长度。合法性的哈希表中一共存有m个元素队列中最多有m个元素每个元素的空间为O(n)队列中最多有m个元素每个元素的空间为O(n)因此空间复杂度为O(n×m)。
【2】预处理优化 经过分析可知题目要求将一个基因序列A变化至另一个基因序列B需要满足一下条件 1、A与 序列B之间只有一个字符不同 2、变化字符只能从A, C, G, T中进行选择 3、变换后的序列B一定要在字符串数组bank中。
已知方法一中广度优先搜索方法我们可以对bank进行预处理只在合法的基因变化进行搜索即可。由于题目中给定的bank基因库的长度较小因此可以直接在对bank进行预处理找到基因库中的每个基因的合法变换而不需要像方法一中每次都需要去计算基因的变化序列我们将每个基因的合法变化关系存储在邻接表adj中每次基因变化搜索只在adj中进行即可。
class Solution {public int minMutation(String start, String end, String[] bank) {int m start.length();int n bank.length;ListInteger[] adj new List[n];for (int i 0; i n; i) {adj[i] new ArrayListInteger();}int endIndex -1;for (int i 0; i n; i) {if (end.equals(bank[i])) {endIndex i;}for (int j i 1; j n; j) {int mutations 0;for (int k 0; k m; k) {if (bank[i].charAt(k) ! bank[j].charAt(k)) {mutations;}if (mutations 1) {break;}}if (mutations 1) {adj[i].add(j);adj[j].add(i);}}}if (endIndex -1) {return -1;}QueueInteger queue new ArrayDequeInteger();boolean[] visited new boolean[n];int step 1;for (int i 0; i n; i) {int mutations 0;for (int k 0; k m; k) {if (start.charAt(k) ! bank[i].charAt(k)) {mutations;}if (mutations 1) {break;}}if (mutations 1) {queue.offer(i);visited[i] true;}} while (!queue.isEmpty()) {int sz queue.size();for (int i 0; i sz; i) {int curr queue.poll();if (curr endIndex) {return step;}for (int next : adj[curr]) {if (visited[next]) {continue;}visited[next] true;queue.offer(next);}}step;}return -1;}
}时间复杂度 O(m×n2)其中m为基因序列的长度n为数组bank的长度。计算合法的基因变化adj需要的时间为O(m×n2)广度优先搜索时队列中最多有n个元素需要的时间为O(n)因此时间复杂度为O(m×n2)。 空间复杂度 O(n2)其中n为数组bank的长度。计算合法的基因变化adj需要的空间为O(n^2)队列中最多有n个元素因此空间复杂度为O(n^2)。
