题目

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

• 例如，"ACGAATTCCG" 是一个 DNA序列 。

在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

示例 2：

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

提示：

• 0 <= s.length <= 10⁵
• s[i]``==``'A'、'C'、'G' or 'T'

题解

static final char[] CHARS = "ACGT".toCharArray();
static final int[] BITS = new int[128];
static final int MAX = (1 << 20) - 1;

static {
    BITS['A'] = 0;
    BITS['C'] = 1;
    BITS['G'] = 2;
    BITS['T'] = 3;
}

public List<String> findRepeatedDnaSequences(String s) {
    if (s.length() <= 10) {
        return Collections.emptyList();
    }
    // values就是出现过的值 added就是重复的值
    // 正常来说重复的数量远小于出现过的数量
    Set<Integer> values = new HashSet<>(), added = new HashSet<>();
    int temp = 0;

    // 滑动计算
    for (int i = 0; i < s.length(); i++) {
        // 移除头2位 只要低20位
        temp = (temp << 2 | BITS[s.charAt(i)]) & MAX;

        // i > 8 表示至少滑动了10位
        if (i > 8 && !values.add(temp)) {
            added.add(temp);
        }
    }

    // 根据结果将数字解码为10位字符串
    return
        added.stream()
            // 解码
            .map(it ->
                IntStream.range(0, 10)
                    .mapToObj(i -> String.valueOf(CHARS[(it >>> (18 - 2 * i)) & 3]))
                    .collect(Collectors.joining())
            )
            .collect(Collectors.toList());
}