本文共 5131 字，大约阅读时间需要 17 分钟。

算法-Hash+滑动窗口-重复的DNA序列

1 概述

1.1 题目出处

https://leetcode-cn.com/problems/repeated-dna-sequences/

1.2 题目描述

所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。

示例：

输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”

输出：[“AAAAACCCCC”, “CCCCCAAAAA”]

2 滑动窗口

2.1 解题思路

思路是关注最近的两个相同字符间距离，同时增加水位限制，水位始终为0或相同字符较旧那个位置的下一个位置。

水位指向当前首个不重复数字位置，用来限制计算重复元素的最小位置，不能低于水位去找重复元素来计算路径长度，因为水位所在的位置之前已经有其他重复元素了。

比如abca，初始为0，直到第二个a时水位更新为前一个a的下一个位置即1

再比如 kacbak 第一次遇到重复元素a时，将水位置为 1 + 1 = 2 第二次，又遇到重复元素k，此时因为上次重复的k的位置0在数位2之下，表示旧k位置和水位之间有其他重复元素，这里就是a 所以不能直接以 第二个k的位置 5 - 第一个k的位置的下一个位置 1 + 1 这样计算长度，因为存在重复元素a！

同时本算法用128位的int数组代替了HashMap，速度再次提高

取128的原因是ascii码一共128个。也可以设为256，因为char为8bit，即针最多2^8-1 个字符

2.2 代码

class Solution {
       public List
   
     findRepeatedDnaSequences(String s) {
           List
    
      resultList = new ArrayList<>();        if(s == null || s.length() < 11){
               return resultList;        }        int window = 10;        Map
     
       cntMap = new HashMap<>();        for(int i = 0; i < s.length() - 9; i++){
               String str = s.substring(i, i + window);            Integer times = cntMap.get(str);            if(times == null){
                   cntMap.put(str, 1);            }else{
                   cntMap.put(str, ++times);                if(times == 2){
                       resultList.add(str);                }            }        }        return resultList;    }}
     
    
   

2.3 时间复杂度

O((N - L)* L)

• L为目标字符串长度，共有N-L+1 个L长度的字符串，每个这样的字符串对应长度L的char数组，所以复杂度要乘以L

2.4 空间复杂度

O((N - L)* L)

• 共有N-L+1 个L长度的字符串，每个字符串占用L空间

3 按位编码

3.1 解题思路

因为原题只有4个字符，所以可想到两位bit来表示。

• 00表示’A’
• 01表示’B’
• 10表示’C’
• 11表示’D’

每十个字符串可组成一段20位的bit序列，可转为一个int整型数值，用它就能表示一个唯一的DNA序列了。

3.2 代码

class Solution {
       public List
   
     findRepeatedDnaSequences(String s) {
           // 结果list        List
    
      resultList = new ArrayList<>();        if(s == null || s.length() < 11){
               return resultList;        }        // 这就是反复使用的整型值        int value = 0;        // 用来存放该字符对应整型编码已出现次数的map        Map
     
       cntMap = new HashMap<>();        // 用来将原value最高2位置为0的魔数        int magic = (int)Math.pow(2, 18) - 1;                char[] cs2 = s.toCharArray();        // 下面开始滑动计算每个字符串，只要出现次数等于2就放入resultList        for(int i = 0; i < cs2.length; i++){
               // 最高2位置为0            value &= magic;            // 左移两位，腾出最低两位            value = value << 2;            // 将当前字符编码后放入value            value = calculate(value, cs2[i]);            if(i < 9){
                   continue;            }            // 计算该编码出现次数            Integer times = cntMap.get(value);            if(times == null){
                   cntMap.put(value, 1);            }else{
                   cntMap.put(value, ++times);                if(times == 2){
                       resultList.add(s.substring(i - 9, i+1));                }            }        }        return resultList;    }    // 字符编码为两位bit    private int calculate(int value, char c){
           switch (c){
               case 'C': {
                   value |= 1;                break;            }            case 'G': {
                   value |= 2;                break;            }            case 'T': {
                   value |= 3;                break;            }            default:break;        }        return value;    }}
     
    
   

3.3 时间复杂度

O((N - L)* L)

• L为目标字符串长度，共有N-L+1 个L长度的字符串，每个这样的字符串对应长度L的char数组，所以复杂度要乘以L

3.4 空间复杂度

O((N - L)* L)

• 共有N-L+1 个L长度的字符串，每个字符串占用L空间

4 利用int数组存储记录出现数

代码:

class Solution {
       public List
   
     findRepeatedDnaSequences(String s) {
           // 结果list        List
    
      resultList = new ArrayList<>();        if(s == null || s.length() < 11){
               return resultList;        }        // 这就是反复使用的整型值        int value = 0;        // 用来存放该字符对应整型编码已出现次数的map        // Map
     
       cntMap = new HashMap<>();        int[] cnt = new int[1<<20];        // 用来将原value最高2位置为0的魔数        int magic = (1 << 18) - 1;                char[] cs2 = s.toCharArray();        for(int i = 0; i < 9; i++){
               // 最高2位置为0            value &= magic;            // 左移两位，腾出最低两位            value = value << 2;            // 将当前字符编码后放入value            value = calculate(value, cs2[i]);        }        // 下面开始滑动计算每个字符串，只要出现次数等于2就放入resultList        for(int i = 9; i < cs2.length; i++){
               // 最高2位置为0            value &= magic;            // 左移两位，腾出最低两位            value = value << 2;            // 将当前字符编码后放入value            value = calculate(value, cs2[i]);            // 计算该编码出现次数            if(++cnt[value] == 2){
                   resultList.add(s.substring(i - 9, i+1));            }        }        return resultList;    }    // 字符编码为两位bit    private int calculate(int value, char c){
           switch (c){
               case 'C': {
                   value |= 1;                break;            }            case 'G': {
                   value |= 2;                break;            }            case 'T': {
                   value |= 3;                break;            }            default:break;        }        return value;    }}
     
    
   

转载地址：http://kmpkb.baihongyu.com/