leetcode433. Minimum Genetic Mutation

aisuhua 发布于2019-08-19 10:22 / 1240人阅读

摘要：已知每一步可以将当前基因序列中的一位进行改变，变成另一个已知的基因序列。为了减少重复的遍历，每经过一个基因序列，就会将它标记为已达。

题目要求

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，一起学习共同进步

专线服务混合云 mutation Minimum Genetic Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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