欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Go Java算法重復(fù)的DNA序列詳解

 更新時(shí)間:2022年08月15日 10:26:33   作者:黃丫丫  
這篇文章主要為大家介紹了Go Java算法之重復(fù)的DNA序列的示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

重復(fù)的DNA序列

DNA序列 由一系列核苷酸組成,縮寫為 'A', 'C', 'G' 和 'T'.。

例如,"ACGAATTCCG" 是一個(gè) DNA序列 。

在研究 DNA 時(shí),識(shí)別 DNA 中的重復(fù)序列非常有用。

給定一個(gè)表示 DNA序列 的字符串 s ,返回所有在 DNA 分子中出現(xiàn)不止一次的 長(zhǎng)度為 10 的序列(子字符串)。你可以按 任意順序 返回答案。

  • 示例 1:

輸入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

輸出:["AAAAACCCCC","CCCCCAAAAA"]

  • 示例 2:

輸入:s = "AAAAAAAAAAAAA"

輸出:["AAAAAAAAAA"]  

提示:

0 <= s.length <= 105

s[i]=='A'、'C'、'G' or 'T'

方法一:哈希表(Java)

我們可以用一個(gè)哈希表統(tǒng)計(jì) ss 所有長(zhǎng)度為 1010 的子串的出現(xiàn)次數(shù),返回所有出現(xiàn)次數(shù)超過(guò) 1010 的子串。

代碼實(shí)現(xiàn)時(shí),可以一邊遍歷子串一邊記錄答案,為了不重復(fù)記錄答案,我們只統(tǒng)計(jì)當(dāng)前出現(xiàn)次數(shù)為 22 的子串。

思路:用map存儲(chǔ)子串出現(xiàn)的次數(shù),循環(huán)dna序列,每次截取長(zhǎng)度為10的子串,加入map中 并更新出現(xiàn)的次數(shù),次數(shù)超過(guò)2,加入ans

能做兩個(gè)優(yōu)化:

  • 統(tǒng)計(jì)字符串的時(shí)候,可以通過(guò)位運(yùn)算來(lái)壓縮hashmap的key的大小。由于只用了 'A' 'C' 'G' 'T' 四個(gè)字符,我們可以用兩位二進(jìn)制來(lái)標(biāo)記每種類型。長(zhǎng)度為10的字符串一共需要20位二進(jìn)制表示,用一個(gè)int即可標(biāo)記出來(lái)。
  • 滑動(dòng)窗口,不用從每個(gè)位置開始往后數(shù)十個(gè)位置來(lái)統(tǒng)計(jì)字符串。由于前面已經(jīng)用了位運(yùn)算映射字符串到int,我們可以直接通過(guò)<<和|操作即可實(shí)現(xiàn)窗口內(nèi)字符串映射的改變。
class Solution {
    static final int L = 10;
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<String>();
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        int n = s.length();
        for (int i = 0; i <= n - L; ++i) {
            String sub = s.substring(i, i + L);
            cnt.put(sub, cnt.getOrDefault(sub, 0) + 1);
            if (cnt.get(sub) == 2) {
                ans.add(sub);
            }
        }
        return ans;
    }
}

其中 N 是字符串 s 的長(zhǎng)度,L=10 即目標(biāo)子串的長(zhǎng)度。

時(shí)間復(fù)雜度:O(N*L)

空間復(fù)雜度:O(N*L)

方法二:哈希表——優(yōu)化(Go)

具體的方法思路已經(jīng)在上文中表述,該方法為哈希表的優(yōu)化方法。

由于 ss 中只含有 44 種字符,我們可以將每個(gè)字符用 22 個(gè)比特表示,即:

A 表示為二進(jìn)制 00;

C 表示為二進(jìn)制 01;

G 表示為二進(jìn)制 10;

T 表示為二進(jìn)制 11。

如此一來(lái),一個(gè)長(zhǎng)為 10 的字符串就可以用 20 個(gè)比特表示,而一個(gè) int 整數(shù)有 32 個(gè)比特,足夠容納該字符串,因此我們可以將 ss 的每個(gè)長(zhǎng)為 10 的子串用一個(gè) int 整數(shù)表示(只用低 20 位)。

注意到上述字符串到整數(shù)的映射是一一映射,每個(gè)整數(shù)都對(duì)應(yīng)著一個(gè)唯一的字符串,因此我們可以將方法一中的哈希表改為存儲(chǔ)每個(gè)長(zhǎng)為 10 的子串的整數(shù)表示。

方法思路:

  • 滑動(dòng)窗口向右移動(dòng)一位:x = x << 2,由于每個(gè)字符用 2 個(gè)比特表示,所以要左移 2 位;
  • 一個(gè)新的字符 ch 進(jìn)入窗口:x = x | bin[ch],這里 bin[ch] 為字符 ch 的對(duì)應(yīng)二進(jìn)制;
  • 窗口最左邊的字符離開窗口:x = x & ((1 << 20) - 1),由于我們只考慮 x 的低 20 位比特,需要將其余位置零,即與上 (1 << 20) - 1。
const L = 10
var bin = map[byte]int{'A': 0, 'C': 1, 'G': 2, 'T': 3}
func findRepeatedDnaSequences(s string) (ans []string) {
    n := len(s)
    if n <= L {
        return
    }
    x := 0
    for _, ch := range s[:L-1] {
        x = x<<2 | bin[byte(ch)]
    }
    cnt := map[int]int{}
    for i := 0; i <= n-L; i++ {
        x = (x<<2 | bin[s[i+L-1]]) & (1<<(L*2) - 1)
        cnt[x]++
        if cnt[x] == 2 {
            ans = append(ans, s[i:i+L])
        }
    }
    return ans
}

以上就是Go Java算法重復(fù)的DNA序列詳解的詳細(xì)內(nèi)容,更多關(guān)于Go Java算法重復(fù)DNA序列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

最新評(píng)論