找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 8196|回复: 11
收起左侧

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

[复制链接]

47

主题

2

精华

379

积分

高级会员

Rank: 3Rank: 3

积分
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
//A,C,G,T最后3bit不同,即与mask“0111”作与运算可唯一标识ACGT。
下面上代码:
public class Solution {
                public List<String> findRepeatedDnaSequences(String s) {
                        int mask = 0x7FFFFFF;
                        List<String> re = new LinkedList<String>();
                        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)
                                                re.add(s.substring(i - 10, i));
                                        map.put(cur, ++counts);
                                } else {
                                        map.put(cur, 1);
                                }
                        }
                        return re;
                }
        }




0

主题

0

精华

1153

积分

顶级会员

Rank: 6Rank: 6

积分
1153
发表于 2-6-2015 10:32 PM | 显示全部楼层
good,感谢分享!
回复 支持 反对

使用道具 举报

38

主题

6

精华

272

积分

高级会员

Rank: 3Rank: 3

积分
272
发表于 2-9-2015 03:58 AM | 显示全部楼层
能不能解释解释  cur = (cur << 3) | (s.charAt(i++) & 7);   cur = ((cur & mask) << 3) | (s.charAt(i++) & 7);这两步操作?不理解,为什么mask选Integer max
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表