LeetCode 433. 最小基因变化(广度优先搜索)
发布日期:2021-07-01 03:25:40
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月19日 10时01分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
TestNG 学习总结 - 依赖测试(十一)
2019-05-03
TestNG 学习总结 - 参数化测试(十二)
2019-05-03
TestNG 学习总结 - TestNG运行JUnit测试(十三)
2019-05-03
TestNG 学习总结 - 测试结果报告(十四)
2019-05-03
TestNG 学习总结 - 测试结果报告 - 自定义日志记录(十五)
2019-05-03
TestNG 学习总结 - 测试结果报告 - 自定义记录器(十六)
2019-05-03
TestNG 学习总结 - 测试结果报告 - HTML和XML报告(十七)
2019-05-03
TestNG 学习总结 - 测试结果报告 - Junit报告(十八)
2019-05-03
JVM的内存区域划分
2019-05-03
Java ArrayList工作原理及实现
2019-05-03
Java序列化、反序列化
2019-05-03
Java对象深复制、浅复制
2019-05-03
JVM之垃圾回收
2019-05-03
Java 对象初始化过程
2019-05-03
细分自动化测试
2019-05-03
Selenium RC
2019-05-03
Java中List与数组的转换
2019-05-03
使用WebDriver完成web页面切换操作(附源码)
2019-05-03
WebDriver自定义显示等待条件
2019-05-03
在eclipse中显示GC情况
2019-05-03