所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。
示例：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出：["AAAAACCCCC", "CCCCCAAAAA"]
解法一：
//时间复杂度O(n), 空间复杂度O(n)
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
unordered_set<string> us1, us2;
for(int i = 0; i <= int(s.size() - 10); i++) {
string temp = s.substr(i, 10);
if(us1.count(temp)) us2.insert(temp);
else us1.insert(s.substr(i, 10));
}
vector<string> res;
for(auto p = us2.begin(); p != us2.end(); p++) {
res.push_back(*p);
}
return res;
}
};解法一：
遍历一次，每次查看当前的10个字符是否在us1中出现过，如果是，就把它加入结果us2中；否则将它加入us1中。
2020/01/05 17:07