本文最后更新于 2025-03-31T00:09:09+08:00
题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| 所有 DNA 都由一系列缩写为 'A','C','G' 和 'T' 的核苷酸组成,例如:"ACGAATTCCG"。在研究 DNA 时,识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串,目标子串的长度为 10,且在 DNA 字符串 s 中出现次数超过一次。
示例 1:
输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出:["AAAAACCCCC","CCCCCAAAAA"] 示例 2:
输入:s = "AAAAAAAAAAAAA" 输出:["AAAAAAAAAA"]
提示:
0 <= s.length <= 105 s[i] 为 'A'、'C'、'G' 或 'T'
|
题目思路
1、滑动窗口,以 10 为值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| class Solution { public: vector<string> findRepeatedDnaSequences(string s) { vector<string> ans; int n = s.size(); unordered_map<string, int> st; for(int i = 0, j = 9; j < n; j++, i++) { if(st[s.substr(i,10)] == 1) { ans.push_back(s.substr(i, 10)); } st[s.substr(i, 10)]++; } return ans; } };
|
复杂度
187. 重复的DNA序列
https://chaggle.github.io/2021/10/08/Leetcode/187/