資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式，用於查詢基因的總突變組
假設我們有一個稱為基因的字串列表，其中每個元素具有相同的長度，並且每個元素包含字元“A”，“C”，“G”和/或“T”。現在有一些規則：
當兩個字串 s1 和 s2 除了一個字元外完全相同，則 s1 和 s2 屬於同一個突變組。
當兩個字串 s1 和 s2 屬於一個組，並且 s2 和 s3 屬於一個組，則 s1 和 s3 屬於同一個組。
我們需要找到可以生成的突變組的總數。
因此，如果輸入類似於 genes = ["ACGT", "ACGC", "ACTT", "TTTT", "TGTT"]，則輸出將為 2，因為有兩個突變組：["ACGT", "ACGC", "ACTT"] 和 ["TTTT", "TTTG"]
為了解決這個問題，我們將遵循以下步驟：
定義一個名為 parent 的對映
定義一個函式 getPar()，它將接收 a，
如果 parent[a] 與 a 相同，則
返回 a
parent[a] = getPar(parent[a])
返回 parent[a]
定義一個函式 unite()，它將接收 a，b，
parA := getPar(a)，parB := getPar(b)
如果 parA 不等於 parB，則
parent[parA] := parB
返回 true
返回 false
定義一個函式 ok()，它將接收 a，b，
cnt := 0
從 i := 0 開始，當 i < a 的大小，更新 (i 增加 1)，執行
cnt := cnt + (當 a[i] 不等於 b[i] 時為 1，否則為 0)
當 cnt 為 1 時返回 true，否則返回 false
從主方法執行以下操作：
對陣列 v 進行排序
透過從 v 中獲取元素定義一個集合 s
ret := v 的大小
對於 v 中的每個元素 it，執行
parent[it] := it
對於 v 中的每個元素 it，執行
從 j := 0 開始，當 j < it 的大小，更新 (j 增加 1)，執行
temp := it
對於 [A, C, G, T] 中的每個字元 x
如果 x 不等於 it[j]，則
temp[j] := x
如果 s 中存在 temp，則
如果 unite(temp, it)，則
返回 ret
讓我們檢視以下實現以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map <string, string> parent;
string getPar(string& a){
if(parent[a] == a)
return a;
return parent[a] = getPar(parent[a]);
}
bool unite(string& a, string& b){
string parA = getPar(a);
string parB = getPar(b);
if(parA != parB){
parent[parA] = parB;
return true;
}
return false;
}
bool ok(string &a, string& b){
int cnt = 0;
for(int i = 0; i < a.size(); i++){
cnt += a[i] != b[i];
}
return cnt == 1;
}
int solve(vector<string> v) {
sort(v.begin(), v.end());
set <string> s(v.begin(), v.end());
int ret = v.size();
for(auto& it : v){
parent[it]= it;
}
for(auto& it : v){
for(int j = 0; j < it.size(); j++){
string temp = it;
for(char x : {'A', 'C', 'G', 'T'}){
if(x != it[j]){
temp[j] = x;
if(s.count(temp)){
if(unite(temp, it)) ret--;
}
}
}
}
}
return ret;
}
};
main(){
vector<string> v = {"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"};
Solution(ob);
cout << ob.solve(v);
}
輸入
{"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"}輸出
2
280 次檢視
