亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[Leetcode] Repeated DNA Sequences 重復(fù)DNA序列

wing324 / 1094人閱讀

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

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"].
哈希表法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

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

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

時(shí)間 O(N) 空間 O(N)

思路

實(shí)際上我們的哈希表可以不用存整個(gè)子串，因?yàn)槲覀冎雷哟挥?0位，且每一位只可能有4種不同的字母，那我們可以用4^10個(gè)數(shù)字來(lái)表示每種不同的序列，因?yàn)?b>4^10=2^20<2^32所以我們可以用一個(gè)Integer來(lái)表示。具體的編碼方法是用每?jī)晌籦it表示一個(gè)字符。

代碼 
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);
            // 每?jī)晌槐硎疽粋€(gè)字符
            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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66173.html

相關(guān)文章

  • leetcode187. Repeated DNA Sequences

    摘要：題目要求所有的都是有這四個(gè)字母組成的，比如。這個(gè)問(wèn)題要求我們?cè)谝粋€(gè)序列中找到出現(xiàn)超過(guò)兩次的長(zhǎng)度為的子序列。因?yàn)閭€(gè)字母意味著每個(gè)字母至少需要位才能表示出來(lái)。因?yàn)槊總€(gè)字符串對(duì)應(yīng)的二進(jìn)制長(zhǎng)度為，小于整數(shù)的，因此是可行的。 題目要求 All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for...

    Noodles 評(píng)論0 收藏0

  • 187. Repeated DNA Sequences

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

    kviccn 評(píng)論0 收藏0

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

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

    89542767 評(píng)論0 收藏0

  • Python一階矩馬爾可夫過(guò)程形成任意DNA序列完成實(shí)例

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

    89542767 評(píng)論0 收藏0

  • 第三代基因測(cè)序技術(shù)革新 云計(jì)算的應(yīng)用

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

    RaoMeng 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<