資料結構
網路
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+ 次檢視
廣告