Leetcode 433.最小基因变化
2024-09-02 01:28:15
最小基因变化
一条基因序列由一个带有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
利用广度优先搜索查找最短路径
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue; class Solution {
public int minMutation(String start, String end, String[] bank) {
if (bank == null || bank.length == 0) return -1;
char[] gen = {'A','C','G','T'};
HashSet<String> bankSet = new HashSet<>();
for (String s : bank)
bankSet.add(s);
Queue<String> q = new LinkedList<>();
HashMap<String, Integer> res = new HashMap<>();
res.put(start, 0);
q.add(start);
while (!q.isEmpty()) {
String s = q.poll();
bankSet.remove(s);
for (int i = 0; i < s.length(); i++) {
char[] next = s.toCharArray();
for (char c : gen) {
next[i] = c;
String nextS = new String(next);
if (bankSet.contains(nextS)) {
res.put(nextS, res.get(s) + 1);
if (nextS.equals(end)) return res.get(nextS);
q.add(nextS);
}
}
}
}
return -1;
}
}
最新文章
- 开发中容易写错的一条SQL语句
- PSP(11.9~11.16)
- java中重载与重写的区别
- JS重点特性——闭包详解
- VS2012解决方案的设置
- node.js事件触发
- javascript知识点记录(2)
- 北大ACM(POJ1002-487-3279)
- try、catch、finally的使用分析---与 return 相关
- 微信小程序跳转页面
- dedecms 标签的基本用法
- Httpd Nginx Haproxy反向代理
- java基础(八)-----深入解析java四种访问权限
- IDEA中使用lombok插件
- 使用 ffmpeg 转换视频格式
- 基于TQ2440开发板的WiFi模块的使用经验总结
- CodeForces 558B
- 通过反汇编一个简单的C程序,分析汇编代码理解计算机是如何工作的
- 最小生成树 kuangbin专题最后一个题
- js 杂谈
热门文章
- 转:error LNK2005: ...already defined in MSVCRTD.lib
- URAL 1057 Amount of Degrees (数位DP,入门)
- UVA11090 Going in Cycle (二分+判负环)
- 棋盘问题——POJ1321
- 2018.4.16 Java多线程实现龟兔赛跑
- JS函数的length属性
- jquery Syntax error, unrecognized expression:的解决方法
- SDWebImage解析
- Docker 在容器中部署静态网站
- Linux基础学习-LVM逻辑卷管理遇到的问题