[Leetcode] Repeated DNA Sequences 重復DNA序列

wing324 發布于2019-08-14 16:15 / 1027人閱讀

摘要：哈希表法復雜度時間空間思路最簡單的做法，我們可以把位移一位后每個子串都存入哈希表中，如果哈希表中已經有這個子串，而且是第一次重復，則加入結果中。如果哈希表沒有這個子串，則把這個子串加入哈希表中。

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是編程語言

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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