反复的DNA序列
题目形容：所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在钻研 DNA 时，辨认 DNA 中的反复序列有时会对钻研十分有帮忙。
编写一个函数来找出所有指标子串，指标子串的长度为 10，且在 DNA 字符串 s 中呈现次数超过一次。
示例阐明请见LeetCode官网。
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
解法一：哈希
首先，判断非凡状况，如果字符串的长度小于11，阐明不够组成一个指标子串，不可能有反复的序列，间接返回空。
否则，初始化一个map，用来记录每一个不反复的长度为10的子串，key为子串，value示意相应的key是否是反复序列。而后遍历字符串，每10位作为一个子串，判断以后子串如果不存在，则增加到key中；如果存在且已标为反复，则跳过，如果没有标为反复，则标为反复子串。
最初，返回标为反复的子串即为反复的序列。
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.stream.Collectors;public class LeetCode_187 { /** * 哈希 * * @param s * @return */ public static List<String> findRepeatedDnaSequences(String s) { // 如果字符串的长度小于11，阐明不够组成一个指标子串，不可能有反复的序列，间接返回空 if (s == null || s.length() < 11) { return new ArrayList<>(); } // 记录每一个不反复的长度为10的子串，key为子串，value示意相应的key是否是反复序列 Map<String, Boolean> map = new HashMap<>(); // 长度距离为10，从第一个字符开始 int startIndex = 0, endIndex = startIndex + 10; // 遍历到最初一个字符完结 while (endIndex <= s.length()) { String substring = s.substring(startIndex, endIndex); // 如果以后子串不存在，则增加到key中；如果存在且已标为反复，则跳过，如果没有标为反复，则标为反复子串 if (map.containsKey(substring)) { if (!map.get(substring)) { map.put(substring, true); } } else { map.put(substring, false); } startIndex++; endIndex++; } return map.entrySet().stream().filter(e -> e.getValue()).map(Map.Entry::getKey).collect(Collectors.toList()); } public static void main(String[] args) { // 测试用例，冀望输入： ["AAAAACCCCC","CCCCCAAAAA"] for (String str : findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT")) { System.out.println(str); } }}【每日寄语】 星星之火，能够燎原。