[Leetcode] Repeated DNA Sequences 重复DNA序列

wing324 发布于2019-08-14 16:15 / 1012人阅读

摘要：哈希表法复杂度时间空间思路最简单的做法，我们可以把位移一位后每个子串都存入哈希表中，如果哈希表中已经有这个子串，而且是第一次重复，则加入结果中。如果哈希表没有这个子串，则把这个子串加入哈希表中。

Repeated DNA Sequences

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"].

哈希表法 复杂度

时间 O(N) 空间 O(N)

思路

最简单的做法，我们可以把位移一位后每个子串都存入哈希表中，如果哈希表中已经有这个子串，而且是第一次重复，则加入结果中。如果已经遇到多次，则不加入结果中。如果哈希表没有这个子串，则把这个子串加入哈希表中。

代码

public class Solution {
    public List findRepeatedDnaSequences(String s) {
        List res = new LinkedList();
        HashMap map = new HashMap();
        for(int index = 10; index <= s.length(); index++){
            // 从第10位开始作为结尾，位移一位，比较一次子串
            String substr = s.substring(index - 10, index);
            if(map.containsKey(substr)){
                // 如果是第一次遇到，则加入结果
                if(map.get(substr) == 1){
                    res.add(substr);
                }
                // 标记为已经遇到过一次了
                map.put(substr, 2);
            } else {
                // 如果不存在，则加入表中
                map.put(substr, 1);
            }
        }
        return res;
    }
}

编码法 复杂度

时间 O(N) 空间 O(N)

思路

实际上我们的哈希表可以不用存整个子串，因为我们知道子串只有10位，且每一位只可能有4种不同的字母，那我们可以用4^10个数字来表示每种不同的序列，因为4^10=2^20<2^32所以我们可以用一个Integer来表示。具体的编码方法是用每两位bit表示一个字符。

代码

public class Solution {
    public List findRepeatedDnaSequences(String s) {
        List res = new LinkedList();
        HashMap map = new HashMap();
        for(int index = 10; index <= s.length(); index++){
            String substr = s.substring(index - 10, index);
            int code = encode(substr);
            if(map.containsKey(code)){
                if(map.get(code) == 1){
                    res.add(substr);
                }
                map.put(code, 2);
            } else {
                map.put(code, 1);
            }
        }
        return res;
    }
    
    private int encode(String str){
        int code = 0;
        for(int i = 0; i < str.length(); i++){
            char c = str.charAt(i);
            // 每两位表示一个字符
            code <<= 2;
            switch(c){
                case "A": code += 0; break;
                case "C": code += 1; break;
                case "T": code += 2; break;
                case "G": code += 3; break;
            }
        }
        return code;
    }
}

GPU云服务器云服务器 DNA序列 DNA dna存储 dna是编程语言

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

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

leetcode187. Repeated DNA Sequences

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

Noodles 2019-08-16 10:58 评论0 收藏0
187. Repeated DNA Sequences

摘要：题目链接这道题要求所有重复出现的序列，那么可以想到得用，因为这里限制了是个字符长的序列，所以每次其实是去掉第一个，再加一个，这个思想和挺像的，需要用或者来表示。 187. Repeated DNA Sequences 题目链接：https://leetcode.com/problems... 这道题要求所有重复出现的序列，那么可以想到得用hash table，因为这里限制了是10个字符...

kviccn 2019-08-16 10:30 评论0 收藏0
通过自学python求已经知道DNA模版的相辅相成DNA序列

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

89542767 2022-12-22 14:31 评论0 收藏0
Python一阶矩马尔可夫过程形成任意DNA序列完成实例

　　此篇文章关键给大家介绍了Python完成一阶矩马尔可夫过程形成任意DNA序列实例详细说明，感兴趣的小伙伴可以参考借鉴一下，希望可以有一定的帮助，祝愿大家多多的发展，尽早涨薪。　　1.基本原理　　针对DNA序列，一阶矩马尔可夫过程可以看作现阶段碱基对的种类仅在于上一位碱基对种类。如下图1所示，1条编码序列的开始（由B逐渐）有可能是A、T、G、C4种碱基对（且概率同样，均是0.25），若编码序列某...

89542767 2022-12-22 14:15 评论0 收藏0
第三代基因测序技术革新云计算的应用

摘要：第三代基因测序技术革新云计算的应用一位准妈妈，在怀孕周时，需要做唐氏儿的筛查，传统唐筛的方式准确率低，如果结果显示危险性高，那么准妈妈还需要做羊膜穿刺等进一步检查。未来组目前已经拥有两台第三代基因测序仪，而未来这一数字将增长至五台。第三代基因测序技术革新云计算的应用一位准妈妈，在怀孕12-24周时，需要做唐氏儿的筛查，传统唐筛的方式准确率低，如果结果显示危险性高，那么准妈妈还需要做...

RaoMeng 2019-06-28 11:18 评论0 收藏0