数据结构
网络
关系型数据库管理系统 (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 次查看
