Go Java演演算法重複的DNA序列詳解

2022-08-15 14:03:57

重複的DNA序列

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

例如，"ACGAATTCCG" 是一個 DNA序列。

在研究 DNA 時，識別 DNA 中的重複序列非常有用。

給定一個表示 DNA序列的字串 s ，返回所有在 DNA 分子中出現不止一次的長度為 10 的序列(子字串)。你可以按任意順序返回答案。

範例 1：

輸入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

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

範例 2：

輸入：s = "AAAAAAAAAAAAA"

輸出：["AAAAAAAAAA"]

提示：

0 <= s.length <= 105

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

方法一：雜湊表（Java）

我們可以用一個雜湊表統計 ss 所有長度為 1010 的子串的出現次數，返回所有出現次數超過 1010 的子串。

程式碼實現時，可以一邊遍歷子串一邊記錄答案，為了不重複記錄答案，我們只統計當前出現次數為 22 的子串。

思路：用map儲存子串出現的次數，迴圈dna序列，每次擷取長度為10的子串，加入map中並更新出現的次數，次數超過2，加入ans

能做兩個優化：

統計字串的時候，可以通過位運算來壓縮hashmap的key的大小。由於只用了 'A' 'C' 'G' 'T' 四個字元，我們可以用兩位二進位制來標記每種型別。長度為10的字串一共需要20位二進位制表示，用一個int即可標記出來。
滑動視窗，不用從每個位置開始往後數十個位置來統計字串。由於前面已經用了位運算對映字串到int，我們可以直接通過<<和|操作即可實現視窗內字串對映的改變。

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 的長度，L=10 即目標子串的長度。

時間複雜度：O(N*L)

空間複雜度：O(N*L)

方法二：雜湊表——優化（Go）

具體的方法思路已經在上文中表述，該方法為雜湊表的優化方法。

由於 ss 中只含有 44 種字元，我們可以將每個字元用 22 個位元表示，即：

A 表示為二進位制 00；

C 表示為二進位制 01；

G 表示為二進位制 10；

T 表示為二進位制 11。

如此一來，一個長為 10 的字串就可以用 20 個位元表示，而一個 int 整數有 32 個位元，足夠容納該字串，因此我們可以將 ss 的每個長為 10 的子串用一個 int 整數表示（只用低 20 位）。

注意到上述字串到整數的對映是一一對映，每個整數都對應著一個唯一的字串，因此我們可以將方法一中的雜湊表改為儲存每個長為 10 的子串的整數表示。

方法思路：

滑動視窗向右移動一位：x = x << 2，由於每個字元用 2 個位元表示，所以要左移 2 位；
一個新的字元 ch 進入視窗：x = x | bin[ch]，這裡 bin[ch] 為字元 ch 的對應二進位制；
視窗最左邊的字元離開視窗：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演演算法重複的DNA序列詳解的詳細內容，更多關於Go Java演演算法重複DNA序列的資料請關注it145.com其它相關文章！

Go Java演演算法重複的DNA序列詳解

目錄

重複的DNA序列

方法一：雜湊表（Java）

方法二：雜湊表——優化（Go）

方法思路：

熱門文章