 [申请本帖为精选刷题题目讨论帖] LeetCode新题 Repeated DNA Sequences

47主题 379积分  379 发表于 2-6-2015 04:24 AM | 显示全部楼层 |阅读模式

亲！马上注册或者登录会查看更多内容！

x
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T,
for example: "ACGAATTCCG". When studying DNA,
it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings)
that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

//A=0x41, C=0x43, G=0x47, T=0x54
//A=0101, C=0103, G=0107, T=0124

public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
if (s.length() <= 10)
return re;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int cur = 0;
int i = 0;
while (i < 9) {
cur = (cur << 3) | (s.charAt(i++) & 7);
}
while (i < s.length()) {
cur = ((cur & mask) << 3) | (s.charAt(i++) & 7);
if (map.containsKey(cur)) {
int counts = map.get(cur);
if (counts == 1)
map.put(cur, ++counts);
} else {
map.put(cur, 1);
}
}
return re;
}
}

0主题 1153积分  1153 发表于 2-6-2015 10:32 PM | 显示全部楼层
 good，感谢分享！

38主题 269积分  269 发表于 2-9-2015 03:58 AM | 显示全部楼层
 能不能解释解释  cur = (cur << 3) | (s.charAt(i++) & 7);   cur = ((cur & mask) << 3) | (s.charAt(i++) & 7);这两步操作？不理解，为什么mask选Integer max

 本版积分规则 回帖后跳转到最后一页   