广安网站制作设计,网站建设一般多少钱官网,滕州网站建设助企网络,天津网站建设首选 津坤科技重复的DNA序列【LC187】 DNA序列 由一系列核苷酸组成#xff0c;缩写为 A, C, G 和 T.。 例如#xff0c;ACGAATTCCG 是一个 DNA序列 。 在研究 DNA 时#xff0c;识别 DNA 中的重复序列非常有用。 给定一个表示 DNA序列 的字符串 s #xff0c;返回所有在 DNA…重复的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 ListString 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;MapInteger, Integer count new HashMap();ListString 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];}
}复杂度 时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
