网站长春网站建设收录查询 站长工具

1 题目：重复的DNA序列

官方标定难度：中

DNA序列 由一系列核苷酸组成，缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’.。

例如，“ACGAATTCCG” 是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：

输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
输出：[“AAAAACCCCC”,“CCCCCAAAAA”]

示例 2：

输入：s = “AAAAAAAAAAAAA”
输出：[“AAAAAAAAAA”]

提示：

$0<=s.length<=10^5$
s[i]==‘A’、‘C’、‘G’ or ‘T’

2 solution

直接用 map 统计每一个长度为 10 的子串，然后返回重复 2 次以上的

代码

class Solution {
public:vector<string> findRepeatedDnaSequences(string s) {vector<string> ans;unordered_map<string, int> map;for (int i = 0; i + 9 < s.size(); i++) {string t = s.substr(i, 10);map[t]++;if(map[t]==2) ans.push_back(t);}return ans;}
};

结果

3 进阶

直接将长度为 10 的串映射成一个整数

代码

class Solution {
public:vector<string> findRepeatedDnaSequences(string s) {unordered_map<char, int> f = {{'A', 0},{'C', 1},{'G', 2},{'T', 3}};int t = 0;for (int i = 0; i < 9; i++) t = t * 4 + f[s[i]];unordered_map<int, int> map;int N = 1 << 18;vector<string> ans;for (int i = 9; i < s.size(); i++) {t = t % N * 4 + f[s[i]];map[t]++;if (map[t] == 2) ans.push_back(s.substr(i - 9, 10));}return ans;}
};

结果