C ++中的重复DNA序列
我们必须编写一种方法来查找在DNA分子中出现多次的所有10个字母长的序列(子串)。
因此,如果输入类似于“AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”,那么输出将为[“AAAAACCCCC”,“CCCCCAAAAA”]。
为了解决这个问题,我们将遵循以下步骤-
定义一个数组ret,n:=s的大小,创建两个名为visited和visited2的集合
定义一个名为bitVal的映射。
将ACGT的对应值(如0123)存储到butVal中。
遮罩:=0
对于i,范围为0至n–1
将子字符串形式的索引i–9到9插入ret
将标记插入Visited2。
面具:=面具*4
掩码:=桅杆或bitVal[s[i]]
遮罩:=遮罩ANDFFFFF
如果i<9,则继续下一个迭代
将遮罩插入已访问
返回ret
例子(C++)
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } typedef long long int lli; class Solution { public: vector<string>findRepeatedDnaSequences(string s) { vector <string> ret; int n = s.size(); set <int> visited; set <int> visited2; map <char, int> bitVal; bitVal['A'] = 0; bitVal['C'] = 1; bitVal['G'] = 2; bitVal['T'] = 3; lli mask = 0; for(int i = 0; i < n; i++){ mask <<= 2; mask |= bitVal[s[i]]; mask &= 0xfffff; if(i < 9) continue; if(visited.count(mask) && !visited2.count(mask)){ ret.push_back(s.substr(i - 9, 10)); visited2.insert(mask); } visited.insert(mask); } return ret; } }; main(){ Solution ob; print_vector(ob.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT")); }
输入值
"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出结果
[AAAAACCCCC, CCCCCAAAAA, ]