重复的DNA序列【LC187】
DNA序列 由一系列核苷酸组成，缩写为
'A','C','G'和'T'.。
- 例如，
"ACGAATTCCG"是一个 DNA序列 。- 在研究 DNA 时，识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串
s，返回所有在 DNA 分子中出现不止一次的 长度为10的序列(子字符串)。你可以按 任意顺序 返回答案。
- 思路计算每个长度为10的子字符串的字符串哈希编码值，当遇到相同的哈希编码值时，将该字符串放入结果集中
- 注意：不严谨，未判断长度是否相同
- 实现
字符串哈希的「构造 数组」和「计算哈希」的过程，不会溢出吗？
会溢出，溢出就会变为负数，当且仅当两个哈希值溢出程度与 Integer.MAX_VALUE 呈**不同【相同？】**的倍数关系时，会产生错误结果（哈希冲突），此时考虑修改 或者采用表示范围更大的 long 来代替 int。->不取余也是可以的
- 溢出1->Integer.MIN_VALUE:-2147483648
class Solution { // private final static long MOD = 1000000007; public List<String> findRepeatedDnaSequences(String s) { int n = s.length(); int base = 7; int[] h = new int[n + 1]; int[] p = new int[n + 1]; p[0] = 1; Map<Integer, Integer> count = new HashMap<>(); List<String> res = new ArrayList<>(); for (int i = 1; i <= n; i++){ h[i] = h[i - 1] * base + s.charAt(i - 1); p[i] = p[i - 1] * base; } for (int i = 0; i <= n - 10; i++){ int code = hash(h, p, i, i + 10 - 1); int cnt = count.getOrDefault(code, 0); if (cnt == 1){ res.add(s.substring(i, i + 10)); } count.put(code, cnt + 1); } return res; } private int hash(int[] h, int[] p, int l, int r){ return h[r + 1] - h[l] * p[r - l + 1]; } }
