【算法面试题】重复的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
的选取,在空间复杂度上进行了轻微的优化,这里需要对二进制有较深的理解。
关注我
image
网友评论