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

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

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

题目描述
重复的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记录已出现过的序列

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

在窗口滑动过程中，使用掩码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);
    }