成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Repeated DNA Sequences 重復DNA序列

wing324 / 1035人閱讀

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

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)

思路

最簡單的做法，我們可以把位移一位后每個子串都存入哈希表中，如果哈希表中已經(jīng)有這個子串，而且是第一次重復，則加入結(jié)果中。如果已經(jīng)遇到多次，則不加入結(jié)果中。如果哈希表沒有這個子串，則把這個子串加入哈希表中。

代碼 
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位開始作為結(jié)尾，位移一位，比較一次子串
            String substr = s.substring(index - 10, index);
            if(map.containsKey(substr)){
                // 如果是第一次遇到，則加入結(jié)果
                if(map.get(substr) == 1){
                    res.add(substr);
                }
                // 標記為已經(jīng)遇到過一次了
                map.put(substr, 2);
            } else {
                // 如果不存在，則加入表中
                map.put(substr, 1);
            }
        }
        return res;
    }
}
編碼法 復雜度

時間 O(N) 空間 O(N)

思路

實際上我們的哈希表可以不用存整個子串，因為我們知道子串只有10位，且每一位只可能有4種不同的字母，那我們可以用4^10個數(shù)字來表示每種不同的序列，因為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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66173.html

相關(guān)文章

  • leetcode187. Repeated DNA Sequences

    摘要：題目要求所有的都是有這四個字母組成的，比如。這個問題要求我們在一個序列中找到出現(xiàn)超過兩次的長度為的子序列。因為個字母意味著每個字母至少需要位才能表示出來。因為每個字符串對應的二進制長度為，小于整數(shù)的，因此是可行的。 題目要求 All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for...

    Noodles 評論0 收藏0

  • 187. Repeated DNA Sequences

    摘要：題目鏈接這道題要求所有重復出現(xiàn)的序列，那么可以想到得用，因為這里限制了是個字符長的序列，所以每次其實是去掉第一個，再加一個，這個思想和挺像的，需要用或者來表示。 187. Repeated DNA Sequences 題目鏈接：https://leetcode.com/problems... 這道題要求所有重復出現(xiàn)的序列，那么可以想到得用hash table，因為這里限制了是10個字符...

    kviccn 評論0 收藏0

  • 通過自學python求已經(jīng)知道DNA模版的相輔相成DNA序列

    　　本文關(guān)鍵給大家介紹了通過自學python求已經(jīng)知道DNA模版的相輔相成DNA序列的實例詳細說明，感興趣的小伙伴可以參考借鑒一下，希望可以有一定的幫助，祝愿大家多多的發(fā)展，盡早漲薪?！　NA序列　　ACTGATCGATTACGTATAGTATTTGCTATCATACATATATATCGATGCGTTCAT　　求其相輔相成DNA序列。　　在微生物上DNA相輔相成編碼序列概述表述能夠表述為：A與T...

    89542767 評論0 收藏0

  • Python一階矩馬爾可夫過程形成任意DNA序列完成實例

    　　此篇文章關(guān)鍵給大家介紹了Python完成一階矩馬爾可夫過程形成任意DNA序列實例詳細說明，感興趣的小伙伴可以參考借鑒一下，希望可以有一定的幫助，祝愿大家多多的發(fā)展，盡早漲薪?！　?.基本原理　　針對DNA序列，一階矩馬爾可夫過程可以看作現(xiàn)階段堿基對的種類僅在于上一位堿基對種類。如下圖1所示，1條編碼序列的開始（由B逐漸）有可能是A、T、G、C4種堿基對（且概率同樣，均是0.25），若編碼序列某...

    89542767 評論0 收藏0

  • 第三代基因測序技術(shù)革新 云計算的應用

    摘要：第三代基因測序技術(shù)革新云計算的應用一位準媽媽，在懷孕周時，需要做唐氏兒的篩查，傳統(tǒng)唐篩的方式準確率低，如果結(jié)果顯示危險性高，那么準媽媽還需要做羊膜穿刺等進一步檢查。未來組目前已經(jīng)擁有兩臺第三代基因測序儀，而未來這一數(shù)字將增長至五臺。 第三代基因測序技術(shù)革新 云計算的應用一位準媽媽，在懷孕12-24周時，需要做唐氏兒的篩查，傳統(tǒng)唐篩的方式準確率低，如果結(jié)果顯示危險性高，那么準媽媽還需要做...

    RaoMeng 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<