LeetCode 433. 最小基因变化(广度优先搜索)
发布日期:2021-07-01 03:25:40
浏览次数:2
分类:技术文章
本文共 1722 字,大约阅读时间需要 5 分钟。
1. 题目
一条基因序列由一个带有8个字符的字符串表示,其中每个字符都属于 “A”, “C”, “G”, "T"中的任意一个。
假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。
例如,基因序列由"AACCGGTT" 变化至 “AACCGGTA” 即发生了一次基因变化。
与此同时,每一次基因变化的结果,都需要是一个合法的基因串,即该结果属于一个基因库。
现在给定3个参数 — start, end, bank,分别代表起始基因序列,目标基因序列及基因库,请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。
如果无法实现目标变化,请返回 -1。注意:起始基因序列默认是合法的,但是它并不一定会出现在基因库中。所有的目标基因序列必须是合法的。假定起始基因序列与目标基因序列是不一样的。示例 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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-genetic-mutation 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. BFS解题
- 模板题,用队列实现,每个单词的字符变成4种可能
- bank 字符串插入哈希set中,找到了就删除(访问过了)
class Solution { public: int minMutation(string start, string end, vector& bank) { if(start.size()!=end.size()) return -1; unordered_set s; for(string& b : bank) s.insert(b);//同时兼做未访问的集合 if(!s.count(end)) return -1; queue q; string cur, temp; int step = 0, n, i, j; char ch[4] = { 'A','G','C','T'}; q.push(start); if(s.count(start)) s.erase(start); while(!q.empty()) { n = q.size(); while(n--) { cur = q.front(); if(cur == end) return step; q.pop(); for(i = 0; i < cur.size(); ++i) { for(j = 0; j < 4; ++j) { temp = cur; temp[i] = ch[j]; if(s.count(temp))//未访问的 { q.push(temp); s.erase(temp); } } } } step++; } return -1; }};
0 ms 6.7 MB
转载地址:https://michael.blog.csdn.net/article/details/106156216 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月30日 12时33分10秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
渐进式Web应用程序的深入概述
2019-05-03
Webpack4教程 - 第三部分,如何使用插件
2019-05-03
Web API 持续集成:PostMan+Newman+Jenkins(图文讲解)
2019-05-03
如何搭建基于C#和 Appium 的 Android自动测试环境
2019-05-03
如何在WSL下使用VS Code
2019-05-03
当异步不再能满足需求:对浏览器中的多线程的介绍
2019-05-03
Webpack 4教程:为什么要优化代码
2019-05-03
“别更新了,学不动了” 之:全栈开发者 2019 应该学些什么?
2019-05-03
在 Angular 8 中,我们可以期待些什么
2019-05-03
Webpack 4教程 - 第四部分,使用SplitChunksPlugin分离代码
2019-05-03
Webpack 4教程 - 第八部分 使用prefetch和preload进行动态加载
2019-05-03
“宇宙最强” IDE,Visual Studio 2019 正式发布
2019-05-03
每个程序员都该学习的5种开发语言
2019-05-03
都 9012了,该选择 Angular、React,还是Vue?
2019-05-03
WebApp 安全风险与防护课堂开课了!
2019-05-03
每个Web开发者都该了解的12条命令行
2019-05-03
十分钟教你理解TypeScript中的泛型
2019-05-03
2019 Vue开发指南:你都需要学点啥?
2019-05-03
如何编写更好的SQL查询:终极指南-第一部分
2019-05-03
WebApp 安全风险与防护课堂(第二讲)开课了!
2019-05-03