資訊專欄INFORMATION COLUMN
摘要：已知每一步可以將當(dāng)前基因序列中的一位進(jìn)行改變，變成另一個(gè)已知的基因序列。為了減少重復(fù)的遍歷，每經(jīng)過一個(gè)基因序列，就會(huì)將它標(biāo)記為已達(dá)。
題目要求
A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T". Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string. For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation. Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string. Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1. Note: Starting point is assumed to be valid, so it might not be included in the bank. If multiple mutations are needed, all mutations during in the sequence must be valid. You may assume start and end string is not the same. Example 1: start: "AACCGGTT" end: "AACCGGTA" bank: ["AACCGGTA"] return: 1 Example 2: start: "AACCGGTT" end: "AAACGGTA" bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"] return: 2 Example 3: start: "AAAAACCC" end: "AACCCCCC" bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"] return: 3
假設(shè)現(xiàn)在有兩個(gè)基因序列，并且用一個(gè)字符串?dāng)?shù)組bank來表示一個(gè)基因序列銀行。已知每一步可以將當(dāng)前基因序列中的一位進(jìn)行改變，變成另一個(gè)已知的基因序列。問最少需要多少步可以將初始的基因序列轉(zhuǎn)化為目標(biāo)基因序列。如果無法轉(zhuǎn)換，則返回-1。
思路和代碼其實(shí)這題是是一個(gè)典型的廣度優(yōu)先算法的題目。廣度優(yōu)先遍歷通常用于尋找最短路徑，將起始基因視作起點(diǎn)，將目標(biāo)基因視作終點(diǎn)，而一個(gè)基因與另一個(gè)基因之間是否是相鄰節(jié)點(diǎn)，則可以通過這兩個(gè)基因之間是否只相差一個(gè)基因位進(jìn)行判斷。為了減少重復(fù)的遍歷，每經(jīng)過一個(gè)基因序列，就會(huì)將它標(biāo)記為已達(dá)。代碼如下：
public int minMutation(String start, String end, String[] bank) {
Queue queue = new LinkedList<>();
Set bankSet = new HashSet();
for(String item : bank) {
bankSet.add(item);
}
int round = 0;
queue.add(start);
while(!queue.isEmpty()) {
int numberOfGenes = queue.size();
while(numberOfGenes-- > 0){
String tmp = queue.poll();
if(tmp.equals(end)) {
return round;
}
Iterator iterator = bankSet.iterator();
while(iterator.hasNext()) {
String cur = iterator.next();
int count = 0;
for(int i = 0 ; i 1) {
break;
}
}
if(count == 1) {
queue.offer(cur);
iterator.remove();
}
}
}
round++;
}
return -1;
}
對(duì)技術(shù)感興趣的同學(xué)，歡迎加博主的微信RALE_DONG，一起學(xué)習(xí)共同進(jìn)步
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/75916.html
摘要：編碼需要將問題的解編碼成字符串的形式才能使用遺傳算法。遺傳算子遺傳算法有個(gè)最基本的操作選擇，交叉，變異。實(shí)驗(yàn)發(fā)現(xiàn)，比較大的種群的規(guī)模并不能優(yōu)化遺傳算法的結(jié)果。災(zāi)變遺傳算法的局部搜索能力較強(qiáng)，但是很容易陷入局部極值。 一、遺傳算法進(jìn)化論背景知識(shí) 作為遺傳算法生物背景的介紹，下面內(nèi)容了解即可： 種群(Population)：生物的進(jìn)化以群體的形式進(jìn)行，這樣的一個(gè)群體稱為種群。 個(gè)體：組成...
摘要： Ways to complete Kraken Problem Kraken is m*n grids on a rectangular board. From the top left to reach the bottom right corner while moving one grid at a time in either the down, right or down-...
LeetCode[76] Minimum Window Substring Given a string S and a string T, find the minimum window in S whichwill contain all the characters in T in complexity O(n). For example, S = ADOBECODEBANC T = AB...
Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...
閱讀 2823·2021-11-24 09:39
閱讀 3393·2021-11-19 09:40
閱讀 2263·2021-11-17 09:33
閱讀 3753·2021-10-08 10:04
閱讀 3043·2021-09-26 09:55
閱讀 1668·2021-09-22 15:26
閱讀 931·2021-09-10 10:51
閱讀 3130·2019-08-30 15:44
