关于java:LeetCode187重复的DNA序列

38次阅读

共计 1499 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：所有 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);
        }
    }
}