程序以查找C ++中的基因的总突变组
假设我们有一个称为基因的字符串列表,其中每个元素具有相同的长度,每个元素包含字符“A”,“C”,“G”和/或“T”。现在有一些规则-
当两个字符串s1和s2是除一个字符之外的相同字符串时,则s1和s2在同一突变组中。
当两个字符串s1和s2在一个组中,而s2和s3在一个组中时,则s1和s3在同一组中。
我们必须找到可以产生的突变组的总数。
因此,如果输入像基因=[“ACGT”,“ACGC”,“ACTT”,“TTTT”,“TGTT”],则输出将为2,因为存在两个突变组:[“ACGT”,“ACGC”,“ACTT”]和[“TTTT”,“TTTG”]
为了解决这个问题,我们将遵循以下步骤-
定义一张称为父图
定义一个函数getPar()
,这将需要一个
如果parent[a]与a相同,则:
返回一个
parent[a]=getPar(parent[a])
返回父母[a]
定义一个函数unite()
,这将需要a,b,
parA:=getPar(a),parB:=getPar(b)
如果parA不等于parB,则:
parent[parA]:=parB
返回真
返回假
定义一个函数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中的每个元素,执行
temp:=它
对于[A,C,G,T]中的每个字符x
返回ret
temp[j]:=x
如果s中存在temp,则:
如果unite(temp,it),则:
如果x不等于[j],则:
parent[it]:=它
对于v中的每个元素,执行
对于初始化j:=0,当j<它的大小时,更新(将j增加1),执行:
让我们看下面的实现以更好地理解-
示例
#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