2021.10.08 - 117.重复的DNA序列

• 1. 题目
• 2. 思路
• • (1) HashSet
  • (2) HashMap
  • (3) 字符串转整数
• 3. 代码

• 遍历字符串，将所有子串都添加到第一个HashSet中，若添加失败，则表示该子串重复出现，将该子串添加到第二个HashSet中，保证多次重复的子串不会被重复添加。

• 利用HashMap存储子串及其出现的次数，当出现的次数等于2时，将该子串添加到结果集中。

• 将每种字符用2位二进制数表示，则长度为10的子串可由一个20位的二进制数表示。
• 利用位运算控制滑动窗口，计算出每个子串所表示的整数，然后利用HashMap存储该整数及其出现的次数即可。

import java.util.*;

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public List findRepeatedDnaSequences(String s) {
        Set set1 = new HashSet<>();
        Set set2 = new HashSet<>();
        for (int i = 0; i <= s.length() - 10; i++) {
            if (!set1.add(s.substring(i, i + 10))) {
                set2.add(s.substring(i, i + 10));
            }
        }
        List res = new ArrayList<>();
        for (String str : set2) {
            res.add(str);
        }
        return res;
    }
}

class Solution1 {
    public List findRepeatedDnaSequences(String s) {
        List res = new ArrayList<>();
        Map map = new HashMap<>();
        for (int i = 0; i <= s.length() - 10; i++) {
            String str = s.substring(i, i + 10);
            map.put(str, map.getOrDefault(str, 0) + 1);
            if (map.get(str) == 2) {
                res.add(str);
            }
        }
        return res;
    }
}

class Solution2 {
    public List findRepeatedDnaSequences(String s) {
        if (s.length() <= 10) {
            return new ArrayList<>();
        }
        Map bin = new HashMap() {{
            put('A', 0);
            put('C', 1);
            put('G', 2);
            put('T', 3);
        }};
        List res = new ArrayList<>();
        int value = 0;
        for (int i = 0; i < 9; i++) {
            value = (value << 2) | bin.get(s.charAt(i));
        }
        Map map = new HashMap<>();
        for (int i = 0; i <= s.length() - 10; i++) {
            value = ((value << 2) | bin.get(s.charAt(9 + i))) & ((1 << 20) - 1);
            map.put(value, map.getOrDefault(value, 0) + 1);
            if (map.get(value) == 2) {
                res.add(s.substring(i, i + 10));
            }
        }
        return res;
    }
}