LeetCode-433 最小基因变化

简介: LeetCode-433 最小基因变化

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-genetic-mutation

题目描述

基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如,"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 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'] 组成

解题思路

又是晦涩难懂的中文翻译

题目中的意思就是每次基因变异只能变化为基因库中的基因并且每次只能变一个基因,求变化为目标基因的最小步数。

那么可以先针对基因库做预处理,用一个邻接表来记录基因直接的变化关系,顺便找出目标基因的索引。然后使用bfs遍历的方法寻找目标基因,返回遍历的层数,层数就是变异的次数。

代码展示

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        int n = bank.size();
        const int iLength = 8;
        vector<vector<int>> vviAdjacencyTable(n, vector<int>(n, 0));
        int iEndIndex = -1;
        for(int i = 0; i < n; i ++)
        {
            if(bank[i] == end)
                iEndIndex = i;
            for(int j = i + 1; j < n; j++)
            {
                int iCount = 0;
                for(int k = 0; k < iLength; k++)
                {
                    if(bank[i][k] != bank[j][k])
                        iCount++;
                }
                if(iCount == 1)
                {
                    vviAdjacencyTable[i][j] = 1;
                    vviAdjacencyTable[j][i] = 1;
                }    
            }
        }
        if(iEndIndex == -1)
            return -1;
        queue<int> queue_i_Visiting;
        unordered_set<int> set_i_Visited;
        for(int i = 0; i < n; i++)
        {
            int iCount = 0;
            for(int k = 0; k < iLength; k++)
            {
                if(bank[i][k] != start[k])
                    iCount++;
            }
            if(iCount == 1)
            {
                queue_i_Visiting.push(i);
                set_i_Visited.emplace(i);
            }
        }
        int iStep = 1;
        while(!queue_i_Visiting.empty())
        {
            int iSize = queue_i_Visiting.size();
            for(int i = 0; i < iSize; i++)
            {
                int iIndex = queue_i_Visiting.front();
                queue_i_Visiting.pop();
                set_i_Visited.emplace(iIndex);
                if(iIndex == iEndIndex)
                    return iStep;
                for(int j = 0; j < n; j++)
                {
                    if(set_i_Visited.find(j) == set_i_Visited.end() && vviAdjacencyTable[iIndex][j])
                        queue_i_Visiting.push(j);
                }
            }
            iStep++;
        }
        return -1;
    }
};

运行结果

 

相关文章
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
7月前
|
Go
golang力扣leetcode 433. 最小基因变化
golang力扣leetcode 433. 最小基因变化
42 0
|
算法 C++ Python
BFS逛街算法模板-附LeetCode习题-433. 最小基因变化-广度优先搜索
BFS逛街算法模板-附LeetCode习题-433. 最小基因变化-广度优先搜索
LeetCode每日一题——433. 最小基因变化
基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是 ‘A’、‘C’、‘G’ 和 ‘T’ 之一。
107 0
|
算法
​LeetCode刷题实战433:最小基因变化
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
133 0
​LeetCode刷题实战433:最小基因变化
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
58 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
26 1