題目
DNA序列 由一系列核苷酸組成，縮寫為 ‘A’, ‘C’, ‘G’ 和 ‘T’.。
例如，“ACGAATTCCG” 是一個(gè) DNA序列 。
在研究 DNA 時(shí)，識(shí)別 DNA 中的重復(fù)序列非常有用。
給定一個(gè)表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出現(xiàn)不止一次的 長度為 10 的序列(子字符串)。你可以按 任意順序 返回答案。
示例 1：文章來源：http://www.zghlxwxcb.cn/news/detail-827755.html
輸入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
輸出：[“AAAAACCCCC”,“CCCCCAAAAA”]文章來源地址http://www.zghlxwxcb.cn/news/detail-827755.html
方法
- 哈希+滑動(dòng)窗口
- 由于 s 中只含有 4 種字符，我們可以將每個(gè)字符用 2 個(gè)比特表示，即：
- A 表示為二進(jìn)制 00
- C 表示為二進(jìn)制 01
- G 表示為二進(jìn)制 10
- T 表示為二進(jìn)制 11
- 我們可以將 s 的每個(gè)長為 10 的子串用一個(gè) int 整數(shù)表示（只用低 20 位），該 int 作為哈希表的key
- 窗口每次向右滑動(dòng)一個(gè)字符，左邊的兩個(gè) bit 滑出，右邊滑入兩個(gè)新的 bit
- 由于 s 中只含有 4 種字符，我們可以將每個(gè)字符用 2 個(gè)比特表示，即：
代碼
class Solution {
public:
// vector<string> findRepeatedDnaSequences(string s) {
// int n = s.size();
// map<string, int> maps;
// for(int i = 0; i <= n-10; i++){
// maps[s.substr(i, 10)]++;
// }
// vector<string> ret;
// for(auto it : maps){
// if(it.second > 1){
// ret.push_back(it.first);
// }
// }
// return ret;
// }
vector<string> findRepeatedDnaSequences(string s){
int n = s.size();
map<char, int> maps = {{'A', 0}, {'T', 1}, {'C', 2}, {'G', 3}};
map<int, int> cnt;
int x = 0;
for(int i = 0; i < 10-1; i++){
x = (x<<2) | maps[s[i]];
}
vector<string> ret;
for(int i = 0; i <= n-10; i++){
x = ((x << 2) | maps[s[i + 10 - 1]]) & ((1 << (10 * 2)) - 1);
if(cnt[x] < 2){
cnt[x]++;
if(cnt[x] == 2){
ret.push_back(s.substr(i, 10));
}
}
}
return ret;
}
};
到了這里，關(guān)于力扣_字符串10—重復(fù)的DNA序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
