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, ]

Arnab Chakraborty

更新于： 2020 年 5 月 2 日

1K+ 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习