資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
