算法-Hash+滑动窗口/按位编码-重复的DNA序列

比眉伴天荒 2023-03-13 05:16 91阅读 0赞

# 算法-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<String> findRepeatedDnaSequences(String s) { 
            List<String> resultList = new ArrayList<>();
            if(s == null || s.length() < 11){ 
                return resultList;
            }
            int window = 10;
            Map<String,Integer> 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 时间复杂度 ##

![在这里插入图片描述][20200511124542688.png]  
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<String> findRepeatedDnaSequences(String s) { 
            // 结果list
            List<String> resultList = new ArrayList<>();
            if(s == null || s.length() < 11){ 
                return resultList;
            }
            // 这就是反复使用的整型值
            int value = 0;
    
            // 用来存放该字符对应整型编码已出现次数的map
            Map<Integer,Integer> 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 时间复杂度 ##

![在这里插入图片描述][20200511143741475.png]  
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<String> findRepeatedDnaSequences(String s) { 
            // 结果list
            List<String> resultList = new ArrayList<>();
            if(s == null || s.length() < 11){ 
                return resultList;
            }
            // 这就是反复使用的整型值
            int value = 0;
    
            // 用来存放该字符对应整型编码已出现次数的map
            // Map<Integer,Integer> 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;
        }
    }

![在这里插入图片描述][2020051115091456.png]

[20200511124542688.png]: /images/20230312/ec938fd768dc4154b6e5102cd574f5d1.png
[20200511143741475.png]: /images/20230312/2a060be73ae946ed8be7016353beb5c7.png
[2020051115091456.png]: /images/20230312/45d644742ec0453eacad317ac005a2fa.png