【算法面试题】重复的DNA序列
今天是一道关于位运算的题目，来自leetcode，难度为Medium，Acceptance为44.5%。
题目如下
所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
示例：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC", "CCCCCAAAAA"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-dna-sequences
解题思路
思路一
初看该题很简单，最简单的就是暴力搜索，双层循环，将输入s按照长度10进行截取，窗口index从0开始到s.len - 10，内层循环从index+1开始，同样截取长度是10的子串，如果发现重复的组就把它加入到结果中。用 set 进行结果存储。
代码如下
Java版
public List<String> findRepeatedDnaSequences(String s) {
int len = s.length();
Set<String> res = new HashSet<>();
for (int i = 0; i <= len - 10; i++) {
for (int j = i + 1; j <= len - 10; j++) {
if (s.substring(i, i + 10).equals(s.substring(j, j + 10))) {
res.add(s.substring(i, i + 10));
break;
}
}
}
return new ArrayList<>(res);
}
显然，时间复杂度是O(n^2)，不出所料，超时了……
思路二
在上面的思路中，两层循环相当于每一组子串都遍历了两次，所以造成了时间的浪费。我们可以利用一个 Set ，在遍历的时候就将其放入Set，在加入之前判断 Set 中是否存在，如果存在就说明和之前的发生重复，就把它加到结果中。这样我们可以做到只遍历一次。
代码如下
Java版
public List<String> findRepeatedDnaSequences(String s) {
int len = s.length();
Set<String> res = new HashSet<>();
Set<String> set = new HashSet<>();
for (int i = 0; i <= len - 10; i++) {
String key = s.substring(i, i + 10);
//之前是否存在
if (set.contains(key)) {
res.add(key);
} else {
set.add(key);
}
}
return new ArrayList<>(res);
}
这样，我们将时间复杂度降到了O(N)。
思路二升级版
正常情况下到解法一就已经结束了，也可以AC了。但是考虑上面的思路，时间复杂度降到了O(N)，那么空间复杂度呢。因为每个子串都保存到了Set，子串的个数是N-10个，每个子串的长度是L=10，所以总共是O(10*(N-10))=O(L*N)的空间复杂度。
我们思考能不能把空间复杂度降下来，思路如下：
一 在窗口滑动过程中，每次的字符串相对于之前都是少一个字母，多一个字母，而剩下的 9 个字母是没有变化的。
二 因为这里只有4个字母
A C G T，字符通常占用空间比数字大，如果不是字母而是数字会不会容易一些，比如，我们将A C G T分别看成是0 1 2 3，那么原字符串AAAAACCCCC就变成了0000011111。发现这其实是一个数的二进制表示，我们就可以将其看成是整数存储，这样大大降低了存储空间。
当然如果含有G T的话就不是二进制了，而变成了4进制，考虑二进制比较简单，我们将0000011111看做二进制形式，即00000000000101010101，这样A C G T就可以看做是00 01 10 11。
例
对于 Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"。
就可以看做是 0000000000010101010100000000000010101010100000000000101010111111
当 i 等于 0 的时候，key = AAAAACCCCC
当 i 等于 1 的时候，key = AAAACCCCCA
当 i 等于 2 的时候，key = AAACCCCCAA
就可以看做是
当 i 等于 0 的时候，key = 00000000000101010101
当 i 等于 1 的时候，key = 00000000010101010100
当 i 等于 2 的时候，key = 00000001010101010000
key初始化为0，窗口i = 0 时候的key 只需要左移两位，把最高位两位去掉，低位腾出两位，然后加上新加入的字母A，也就是00，就到了i = 1 时候的key。
此外，key 用int 存储，是32 位的，但我们是10 个字母，每个字母对应两位，所以我们只需要20 位，我们需要把key 和 11111111111111111111(0xfffff) 进行按位与，只保留低20 位，所以更新 key 的话需要三个步骤，左移两位 -> 加上当前的字母 -> 按位与操作。
思路有了，代码如下
public List<String> findRepeatedDnaSequences(String s) {
int len = s.length();
if (len == 0 || len < 10) {
return new ArrayList<>();
}
Set<String> res = new HashSet<>();
Set<Integer> set = new HashSet<>();
char map[] = new char[26];
map['A' - 'A'] = 0;
map['C' - 'A'] = 1;
map['G' - 'A'] = 2;
map['T' - 'A'] = 3;
int key = 0;
char[] array = s.toCharArray();
//第一组单独初始化出来
for (int i = 0; i < 10; i++) {
key = key << 2 | map[array[i] - 'A'];
}
set.add(key);
for (int i = 10; i < len; i++) {
key <<= 2;
key |= map[array[i] - 'A'];
key &= 0xfffff;
if (set.contains(key)) {
res.add(s.substring(i - 9, i + 1));
} else {
set.add(key);
}
}
return new ArrayList<>(res);
}
总结
思路二的话是很常规的思路，也可以AC。升级版的话，通过对 key 的选取，在空间复杂度上进行了轻微的优化，这里需要对二进制有较深的理解。
