反向输出dna序列_重复的DNA序列（字符串映射成整数）

以你之姓@ 2023-01-02 08:26 164阅读 0赞

![8131845625734c68b77c4b2aa0f92493.png][]

> *题目描述*  
> 重复的DNA序列 *187. 重复的DNA序列* *所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。* *编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。* *示例：* *输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"* *输出：\["AAAAACCCCC", "CCCCCAAAAA"\]*

## 方法一 ##

**总体思想**：将字符串映射成二进制。这样在比较时，时间复杂度变为O(1)。

**note1**：映射可以使用HashMap，也可以直接使用ASCII码

**note2**：合理使用掩码，保证二进制在位数限制之内（二级制数的界限）

**第一步，字符与二进制的映射**

本题中，一共有4个字符表示不同的DNA序列，我们可以将这4个字符映射到00，01，10，11

也可以直接用下面的ASCII映射，取后三位也可以得到一一映射的关系

> A: 1000001  
> C: 1000011  
> G: 1000111  
> T: 1010100

使用 L7 =0x00000007 作为后三位的掩码，对每一个字符，取其最后三位的二进制数。

**第二步，滑动窗口 + HashSet记录已出现过的序列**

![e3955b1066931a85893a27793717589a.png][]

二进制转换及窗口滑动示意图

在窗口滑动过程中，使用掩码L30 =0x3fffffff，保证记录的二进制数字有效范围在10 \* 3之内。

**第三步，若已出现过，则记录 子串 到答案**

public List<String> findRepeatedDnaSequences(String s) {
         
            if(s.length() < 10){
         
                return new ArrayList<>();
            }
    
            char[] cs = s.toCharArray();
            HashSet<Integer> existSet = new HashSet<>();
            HashSet<String> ans = new HashSet<>();
            int L30 = 0x3fffffff;
            int L7 = 0x00000007;
    
            int dnaMask = 0;
            for (int i = 0; i < 10; i++){
         
                dnaMask <<= 3;
                dnaMask |= (cs[i] & L7);
            }
            existSet.add(dnaMask);
    
            for(int i = 11; i <= s.length(); i++){
         
                dnaMask <<= 3;
                dnaMask &= L30;
                dnaMask |= (cs[i - 1] & L7);
    
                if(existSet.contains(dnaMask)){
         
                    ans.add(s.substring(i-10, i));
                } else {
         
                    existSet.add(dnaMask);
                }
            }
    
            return new ArrayList<>(ans);
        }

## 方法二 ##

参考：

City：“重复”相关的问题zhuanlan.zhihu.com

![d52ad1f7872609198dde47dfe38afd2e.png][]

[8131845625734c68b77c4b2aa0f92493.png]: /images/20221120/1777b3d9a59d4964bcf975c4e174b81d.png
[e3955b1066931a85893a27793717589a.png]: /images/20221120/d25cc9b6d8ba4ba49f0f64dd2a4093b2.png
[d52ad1f7872609198dde47dfe38afd2e.png]: /images/20221120/c8cb2b389ee845229eb22f2e162a195a.png