leetcode433. Minimum Genetic Mutation

aisuhua 發布于2019-08-19 10:22 / 1438人閱讀

摘要：已知每一步可以將當前基因序列中的一位進行改變，變成另一個已知的基因序列。為了減少重復的遍歷，每經過一個基因序列，就會將它標記為已達。

題目要求

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

假設現在有兩個基因序列，并且用一個字符串數組bank來表示一個基因序列銀行。已知每一步可以將當前基因序列中的一位進行改變，變成另一個已知的基因序列。問最少需要多少步可以將初始的基因序列轉化為目標基因序列。如果無法轉換，則返回-1。

思路和代碼

其實這題是是一個典型的廣度優先算法的題目。廣度優先遍歷通常用于尋找最短路徑，將起始基因視作起點，將目標基因視作終點，而一個基因與另一個基因之間是否是相鄰節點，則可以通過這兩個基因之間是否只相差一個基因位進行判斷。為了減少重復的遍歷，每經過一個基因序列，就會將它標記為已達。代碼如下：

    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;
    }

對技術感興趣的同學，歡迎加博主的微信RALE_DONG，一起學習共同進步

云服務器 GPU云服務器 mutation Minimum Genetic Leetcod

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/75916.html

遺傳算法GA(Genetic Algorithm)入門知識梳理

摘要：編碼需要將問題的解編碼成字符串的形式才能使用遺傳算法。遺傳算子遺傳算法有個最基本的操作選擇，交叉，變異。實驗發現，比較大的種群的規模并不能優化遺傳算法的結果。災變遺傳算法的局部搜索能力較強，但是很容易陷入局部極值。一、遺傳算法進化論背景知識作為遺傳算法生物背景的介紹，下面內容了解即可：種群(Population)：生物的進化以群體的形式進行，這樣的一個群體稱為種群。個體：組成...

gxyz 2019-06-26 18:12 評論0 收藏0
AO Rettiwt

摘要： 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-...

Zoom 2019-08-16 10:26 評論0 收藏0
Leetcode[76] Minimum Window Substring

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...

suemi 2019-08-16 10:26 評論0 收藏0
[LintCode/LeetCode] Minimum Window Substring

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...

Corwien 2019-08-14 15:43 評論0 收藏0