LeeC187 Repeated DNA Sequences
class Solution { public: vector<string>findRepeatedDnaSequence(string s) {vector<string> res; unordered_map<int,int>m; int cur = 0; int mask = 0x7ffffff; for (int i = 0; i < 9;++i) { cur = (cur << 3) | (s[i] & 7); } for (int i = 9; i < s.size();++i) { cur = ((cur&mask) << 3) | (s[i] & 7); if (m.find(cur) != m.end()) { if (m[cur] == 1) res.push_back(s.substr(i-9,10)); ++m[cur]; } else{ m[cur] = 1; } } return res; }}
题目描述:
所有 DNA 由一系列缩写为 A,C,G 和 T 的核苷酸组成,例如:“ACGAATTCCG”。在研究 DNA 时,识别 DNA 中的重复序列有时会对研究非常有帮助。编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列(子串)。
题目解析
解题方法: 首先,先将 A , C , G , T 的 ASCII 码用二进制来表示:
A: 0100 0001 C: 0100 0011 G: 0100 0111 T: 0101 0100
可以用末尾的三位区分这四个字符,7&s[i],用mask0x7ffffff提取出后27位,向左移三位,将第十位的后三位放进末尾,用哈希表记录出现的频率。
#笔试题目##C/C++#