资讯专栏INFORMATION COLUMN

187. Repeated DNA Sequences

kviccn / 567人阅读

摘要:题目链接这道题要求所有重复出现的序列,那么可以想到得用,因为这里限制了是个字符长的序列,所以每次其实是去掉第一个,再加一个,这个思想和挺像的,需要用或者来表示。

187. Repeated DNA Sequences

题目链接:https://leetcode.com/problems...

这道题要求所有重复出现的序列,那么可以想到得用hash table,因为这里限制了是10个字符长的序列,所以每次其实是去掉第一个letter,再加一个letter,这个思想和rabin karp挺像的,需要用int或者long来表示string。

public class Solution {
    public List findRepeatedDnaSequences(String s) {
        Set res = new HashSet();
        Set dup = new HashSet();
        Map map = new HashMap();
        map.put("A", 0);  map.put("C", 1);  map.put("G", 2);  map.put("T", 3);
        int hash = 0;
        for(int i = 0; i < s.length(); i++) {
            hash = (hash << 2) | map.get(s.charAt(i));
            hash &= 0xfffff;
            if(i >= 9 && !dup.add(hash)) {
                res.add(s.substring(i-9, i+1));
            }
        }
        return new ArrayList(res);
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/69904.html

相关文章

  • leetcode187. Repeated DNA Sequences

    摘要:题目要求所有的都是有这四个字母组成的,比如。这个问题要求我们在一个序列中找到出现超过两次的长度为的子序列。因为个字母意味着每个字母至少需要位才能表示出来。因为每个字符串对应的二进制长度为,小于整数的,因此是可行的。 题目要求 All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for...

    Noodles 评论0 收藏0
  • [Leetcode] Repeated DNA Sequences 重复DNA序列

    摘要:哈希表法复杂度时间空间思路最简单的做法,我们可以把位移一位后每个子串都存入哈希表中,如果哈希表中已经有这个子串,而且是第一次重复,则加入结果中。如果哈希表没有这个子串,则把这个子串加入哈希表中。 Repeated DNA Sequences All DNA is composed of a series of nucleotides abbreviated as A, C, G, a...

    wing324 评论0 收藏0
  • python Sequence type

    摘要:其实本来是要一下的,就去查了一下是什么意思,发现还有很多要注意的地方,所以就记一下。 其实本来是要reverse一下list的,就去查了一下list[::-1]是什么意思,发现还有很多要注意的地方,所以就记一下。 主要是参照https://docs.python.org/3/library/stdtypes.html?highlight=list#list 首先Sequence ty...

    Ali_ 评论0 收藏0
  • 从 Quora 的 187 个问题中学习机器学习和NLP

    摘要:许多的顶尖研究人员都会积极的在现场回答问题。虽然有许多主题的常见问题页面比如,这是一个机器学习的,但是这些都是非常不全面的,或者不够精致。在这篇文章中,我试图做一个更加全面的有关机器学习和问题的。 作者:chen_h微信号 & QQ:862251340微信公众号:coderpai简书地址:http://www.jianshu.com/p/ac18... showImg(https:/...

    hidogs 评论0 收藏0
  • 通过自学python求已经知道DNA模版的相辅相成DNA序列

      本文关键给大家介绍了通过自学python求已经知道DNA模版的相辅相成DNA序列的实例详细说明,感兴趣的小伙伴可以参考借鉴一下,希望可以有一定的帮助,祝愿大家多多的发展,尽早涨薪。  DNA序列  ACTGATCGATTACGTATAGTATTTGCTATCATACATATATATCGATGCGTTCAT  求其相辅相成DNA序列。  在微生物上DNA相辅相成编码序列概述表述能够表述为:A与T...

    89542767 评论0 收藏0

发表评论

0条评论

kviccn

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<