数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的最小基因突变
假设我们有一个基因字符串。它可以用长度为 8 的字符串表示，该字符串由这些字母组成 [A, C, G, T]。现在考虑我们想要调查突变，其中一次突变实际上是基因字符串中一个字符的改变。例如，“AACCGTTT” 变为 “AACCGTTA” 就是 1 次突变。
我们还有一个给定的基因“库”，其中包含所有有效的基因突变。基因必须存在于库中才能使其成为有效的基因字符串。
现在假设我们给定三样东西 - 开始、结束、库，我们的任务是确定从“开始”突变到“结束”所需的最小突变次数。如果无法从开始转换到结束，则返回 -1。
因此，如果输入类似于 start = "AACCGGTT"，end = "AAACGGTA"，bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]，则输出将为 2。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 putStar()，它将接收 s，
定义一个数组 ret
对于初始化 i := 0，当 i ≪ s 的大小，更新（i 增加 1），执行：
temp := s 从 0 到 i-1 的子字符串连接 " * " + s 从索引 i + 1 到结尾的子字符串
将 temp 插入到 ret 的末尾
返回 ret
从主方法执行以下操作：
定义一个名为 graph 的映射。
对于初始化 i := 0，当 i < bank 的大小，更新（i 增加 1），执行：
s := bank[i]
out = putStar(bank[i])
对于初始化 j := 0，当 j < out 的大小，更新（j 增加 1），执行：
将 s 插入到 graph[out[j]] 的末尾
定义一个队列 q
将 start 插入到 q 中
定义一个集合 visited
将 start 插入到 visited 中
对于初始化 lvl := 1，当 q 不为空，更新（lvl 增加 1），执行：
sz := q 的大小
当 sz 不为零，每次迭代减少 sz，执行：
node := q 的第一个元素
从 q 中删除元素
out = putStar(node)
对于初始化 i := 0，当 i < out 的大小，更新（i 增加 1），执行：
u := out[i]
对于初始化 j := 0，当 j < graph[u] 的大小，更新（j 增加 1），执行：
v := graph[u, j]
如果 v 在 visited 中，则退出循环
如果 v 与 end 相同，则返回 lvl
将 v 插入到 visited 中
将 v 插入到 q 中
返回 -1
让我们看看以下实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector <string> putStar(string s){
vector <string> ret;
for(int i = 0; i < s.size(); i++){
string temp = s.substr(0, i) + "*" + s.substr(i + 1);
ret.push_back(temp);
}
return ret;
}
int minMutation(string start, string end, vector<string>& bank) {
unordered_map < string, vector <string> > graph;
for(int i = 0; i < bank.size(); i++){
string s = bank[i];
vector <string> out = putStar(bank[i]);
for(int j = 0; j < out.size(); j++){
graph[out[j]].push_back(s);
}
}
queue <string> q;
q.push(start);
set <string> visited;
visited.insert(start);
for(int lvl = 1; !q.empty(); lvl++){
int sz = q.size();
while(sz--){
string node = q.front();
q.pop();
vector <string> out = putStar(node);
for(int i = 0; i < out.size(); i++){
string u = out[i];
for(int j = 0; j < graph[u].size(); j++){
string v = graph[u][j];
if(visited.count(v)) continue;
if(v == end) return lvl;
visited.insert(v);
q.push(v);
}
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<string> v = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
cout << (ob.minMutation("AACCGGTT", "AAACGGTA", v));
}输入
"AACCGGTT", "AAACGGTA", {"AACCGGTA", "AACCGCTA", "AAACGGTA"}输出
2
246 次查看
