美文网首页
【算法面试题】重复的DNA序列

【算法面试题】重复的DNA序列

作者: ab409 | 来源:发表于2020-05-28 21:38 被阅读0次

    【算法面试题】重复的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进行截取,窗口index0开始到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

    此外,keyint 存储,是32 位的,但我们是10 个字母,每个字母对应两位,所以我们只需要20 位,我们需要把key11111111111111111111(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

    相关文章

      网友评论

          本文标题:【算法面试题】重复的DNA序列

          本文链接:https://www.haomeiwen.com/subject/zgdzahtx.html