187. Repeated DNA Sequences(重复的DNA序列)
1 问题描述
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
枚举DNA字符串的中所有长度为10的子串,将其插入到哈希Map中,并记录子串数量;遍历哈希map,将所有出
现超过1次的子串存储到结果中。算法复杂度O(n)
Example:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]
2 C++
int g_hash_map[1048576] = {0}; //2^10=1048576
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> result;
if(s.length() < 10)
return result;
for(int i=0; i<1048576; i++)
g_hash_map[i] = 0;
int char_map[128] = {0};
char_map['A'] = 0;
char_map['C'] = 1;
char_map['G'] = 2;
char_map['T'] = 3;
int key = 0;
for(int i=9; i>=0; i--) {
key = (key<<2) + char_map[ s [ i ] ];
}
g_hash_map[key] = 1;
for(int i=10; i<s.length(); i++) {
key = key>>2;
key = key | (char_map[ s [ i ] ] << 18);
g_hash_map[key]++;
}
for(int i=0; i<1048576; i++) {
if(g_hash_map[i] > 1) {
result.push_back(change_int_to_DNA(i));
}
}
return result;
}
private:
string change_int_to_DNA(int DNA) {
static const char DNA_CHAR[] = {'A', 'C', 'G', 'T'};
string str;
for(int i=0; i<10; i++) {
str += DNA_CHAR[DNA & 3];
DNA = DNA >> 2;
}
return str;
}
};
继续阅读
- 我的微信小程序
- 这是我的微信小程序扫一扫
-
- 我的微信公众号
- 我的微信公众号扫一扫
-
评论