专项培训网站建设方案,重庆市沙坪坝区,哪些网站可以免费发布广告,出国劳务187. 重复的DNA序列
难度#xff1a;中等
题目
DNA序列 由一系列核苷酸组成#xff0c;缩写为 A, C, G 和 T.。
例如#xff0c;ACGAATTCCG 是一个 DNA序列 。
在研究 DNA 时#xff0c;识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串 …187. 重复的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^5s[i]A、C、G or T
个人题解
思路
哈希逐个判断即可
class Solution {public ListString findRepeatedDnaSequences(String s) {ListString ansList new ArrayList();MapString, Boolean singleExistMap new HashMap();String temp;for (int left 0, right 10; right s.length(); left, right) {temp s.substring(left, right);if (singleExistMap.containsKey(temp) singleExistMap.get(temp)) {ansList.add(temp);singleExistMap.put(temp, Boolean.FALSE);}else if (!singleExistMap.containsKey(temp)){singleExistMap.put(temp, Boolean.TRUE);}}return ansList;}
}官方题解
方法一哈希表
我们可以用一个哈希表统计 s 所有长度为 10 的子串的出现次数返回所有出现次数超过 10 的子串。
代码实现时可以一边遍历子串一边记录答案为了不重复记录答案我们只统计当前出现次数为 2 的子串。
class Solution {static final int L 10;public ListString findRepeatedDnaSequences(String s) {ListString ans new ArrayListString();MapString, Integer cnt new HashMapString, Integer();int n s.length();for (int i 0; i n - L; i) {String sub s.substring(i, i L);cnt.put(sub, cnt.getOrDefault(sub, 0) 1);if (cnt.get(sub) 2) {ans.add(sub);}}return ans;}
}复杂度分析
时间复杂度O(NL)N是字符串 s 的长度L 10 即目标子串的长度空间复杂度O(NL)
方法二哈希表 滑动窗口 位运算
由于 s 中只含有 4 种字符我们可以将每个字符用 2 个比特表示即
A 表示为二进制 00C 表示为二进制 01G 表示为二进制 10T 表示为二进制 11
如此一来一个长为 10 的字符串就可以用 20 个比特表示而一个 int 整数有 32 个比特足够容纳该字符串因此我们可以将 s 的每个长为 10 的子串用一个 int 整数表示只用低 20 位。
注意到上述字符串到整数的映射是一一映射每个整数都对应着一个唯一的字符串因此我们可以将方法一中的哈希表改为存储每个长为 10 的子串的整数表示。
如果我们对每个长为 10 的子串都单独计算其整数表示那么时间复杂度仍然和方法一一样为O(NL)。为了优化时间复杂度我们可以用一个大小固定为 10 的滑动窗口来计算子串的整数表示。设当前滑动窗口对应的整数表示为 x 当我们要计算下一个子串时就将滑动窗口向右移动一位此时会有一个新的字符进入窗口以及窗口最左边的字符离开窗口这些操作对应的位运算按计算顺序表示如下
滑动窗口向右移动一位x x 2由于每个字符用 2 个字符表示所以要左移 2 位一个新的字符 ch 进入窗口x x | bin[ch] 这里的 bin[ch] 为字符 ch 的对应二进制窗口最左边的字符离开窗口x x ((1 20) - 1) 由于我们只考虑 x 的低 20 位比特需要将其余位置零即与上 (1 20) - 1
将这三步合并就可以用 O(1) 的时间计算出下一个子串的整数表示即 x (( x 2) | bin[ch]) (1 20) - 1)
class Solution {static final int L 10;MapCharacter, Integer bin new HashMapCharacter, Integer() {{put(A, 0);put(C, 1);put(G, 2);put(T, 3);}};public ListString findRepeatedDnaSequences(String s) {ListString ans new ArrayListString();int n s.length();if (n L) {return ans;}int x 0;for (int i 0; i L - 1; i) {x (x 2) | bin.get(s.charAt(i));}MapInteger, Integer cnt new HashMapInteger, Integer();for (int i 0; i n - L; i) {x ((x 2) | bin.get(s.charAt(i L - 1))) ((1 (L * 2)) - 1);cnt.put(x, cnt.getOrDefault(x, 0) 1);if (cnt.get(x) 2) {ans.add(s.substring(i, i L));}}return ans;}
}复杂度分析
时间复杂度O(N)N是字符串 s 的长度空间复杂度O(N)
