数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的重复 DNA 序列
假设我们有一个 DNA 序列。众所周知，所有 DNA 都由一系列核苷酸组成，例如 A、C、G 和 T，例如：“ACGAATTCCG”。当我们研究 DNA 时，有时需要识别 DNA 中的重复序列。
我们必须编写一个方法来查找 DNA 分子中出现两次以上的全部 10 个字母长的序列（子字符串）。
因此，如果输入类似于“AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”，则输出将是 ["AAAAACCCCC", "CCCCCAAAAA"]。
为了解决这个问题，我们将遵循以下步骤：
定义一个数组 ret，n := s 的大小，创建两个集合，分别称为 visited 和 visited2
定义一个名为 bitVal 的映射。
将 ACGT 的对应值（如 0123）存储到 butVal 中。
mask := 0
对于 i 从 0 到 n – 1 的范围
mask := mask * 4
mask := mast OR bitVal[s[i]]
mask := mask AND FFFFF
如果 i < 9，则只需继续到下一次迭代
将从索引 i – 9 到 9 的子字符串插入 ret。
将 mark 插入 visited2。
将 mask 插入 visited
返回 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, ]
更新于： 2020 年 5 月 2 日
1K+ 次查看
广告