织梦做网站的详情,微信怎样开通公众号,做网站需要简介,海淀区seo引擎优化187. 重复的DNA序列
所有 DNA 都由一系列缩写为 ‘A’#xff0c;‘C’#xff0c;‘G’ 和 ‘T’ 的核苷酸组成#xff0c;例如#xff1a;“ACGAATTCCG”。在研究 DNA 时#xff0c;识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串‘C’‘G’ 和 ‘T’ 的核苷酸组成例如“ACGAATTCCG”。在研究 DNA 时识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串目标子串的长度为 10且在 DNA 字符串 s 中出现次数超过一次。
示例 1
输入s “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT” 输出[“AAAAACCCCC”,“CCCCCAAAAA”]
示例 2
输入s “AAAAAAAAAAAAA” 输出[“AAAAAAAAAA”]
解题思路
使用滑动窗口位运算
使用Map可以在O1的时间复杂度内获得目标子串出现的次数但是因为0 s.length 100000因此如果使用map统计长度为 10的目标子串空间复杂度非常高。但是因为所有 DNA 都由一系列缩写为 ‘A’‘C’‘G’ 和 ‘T’ 的核苷酸组成所以我们可以使用2位二进制表示一个字符那么长度为10的目标子串也就只需要一个32位的整型来表示朴素的解法中需要枚举所有长度为10的目标子串时间复杂度为o10*s.length我们可以使用滑动窗口维护窗口内的字符串组成时间复杂度为os.length
代码
class Solution {public String decode(int tar) {StringBuilder sb new StringBuilder();for (int i0;i10;i){int curtar3;if (cur0)sb.append(A);else if(cur1)sb.append(C);else if(cur2)sb.append(G);else sb.append(T);tar2;}return sb.reverse().toString();}public int count(char c) {if (cA)return 0;else if(cC)return 1;else if(cG)return 2;else return 3;}public ListString findRepeatedDnaSequences(String s) {ArrayListString strings new ArrayList();MapInteger,Integer mapnew HashMap();int cur0,l0,r0,ns.length(),mask(120)-1;while (rn){if (r-l10){map.put(cur,map.getOrDefault(cur,0)1);cur-(count(s.charAt(l))18);}cur2;curcount(s.charAt(r));}map.put(cur,map.getOrDefault(cur,0)1);for (Map.EntryInteger, Integer entry : map.entrySet()) {if (entry.getValue()1)strings.add(decode(entry.getKey()));}return strings;}
}
