反向输出dna序列_重复的DNA序列（字符串映射成整数）
发布时间
阅读量：
阅读量
题目描述
具有重复特性的DNA序列 第187. 第187页 所有 DNA 由四种碱基单位 A、C、G 和 T 构成，并以链状结构排列。例如：“ACGAATTCCG”。在 DNA 研究中识别其重复序列往往能提供重要线索。 设计一个算法来搜索特定子串，在 DNA 字符串 s 中出现次数超过一次的子串。其长度必须固定为 10 个字符。 示例： 当输入 DNA 字符串 s 为 "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 时... _则返回列表 ["AAAAACCCCC", "CCCCCAAAAA"]
方法一
总体思想 ：将字符串映射成二进制。这样在比较时，时间复杂度变为O(1)。
note1 ：映射可以使用HashMap，也可以直接使用ASCII码
note2 ：合理使用掩码，保证二进制在位数限制之内（二级制数的界限）
第一步，字符与二进制的映射
本题中，一共有4个字符表示不同的DNA序列，我们可以将这4个字符映射到00，01，10，11
也可以直接用下面的ASCII映射，取后三位也可以得到一一映射的关系
A: 1000001
C: 1000011
G: 1000111
T: 1010100
使用 L7 =0x00000007 作为后三位的掩码，对每一个字符，取其最后三位的二进制数。
第二步，滑动窗口 + HashSet记录已出现过的序列
二进制转换及窗口滑动示意图
当窗口发生滑动时，在掩码L30 = 0x3fffffff的作用下进行处理操作，在此过程中确保所记录的二进制数据的有效范围限定在10乘以3的范围内
第三步，若已出现过，则记录 子串 到答案
public List<String> findRepeatedDnaSequences(String s) {
if(s.length() < 10){
return new ArrayList<>();
}
char[] cs = s.toCharArray();
HashSet<Integer> existSet = new HashSet<>();
HashSet<String> ans = new HashSet<>();
int L30 = 0x3fffffff;
int L7 = 0x00000007;
int dnaMask = 0;
for (int i = 0; i < 10; i++){
dnaMask <<= 3;
dnaMask |= (cs[i] & L7);
}
existSet.add(dnaMask);
for(int i = 11; i <= s.length(); i++){
dnaMask <<= 3;
dnaMask &= L30;
dnaMask |= (cs[i - 1] & L7);
if(existSet.contains(dnaMask)){
ans.add(s.substring(i-10, i));
} else {
existSet.add(dnaMask);
}
}
return new ArrayList<>(ans);
}方法二
参考：
City：“重复”相关的问题zhuanlan.zhihu.com
全部评论 (0)
还没有任何评论哟~