Go Java算法重復(fù)的DNA序列詳解
重復(fù)的DNA序列
DNA序列 由一系列核苷酸組成,縮寫為 'A', 'C', 'G' 和 'T'.。
例如,"ACGAATTCCG" 是一個 DNA序列 。
在研究 DNA 時,識別 DNA 中的重復(fù)序列非常有用。
給定一個表示 DNA序列 的字符串 s ,返回所有在 DNA 分子中出現(xiàn)不止一次的 長度為 10 的序列(子字符串)。你可以按 任意順序 返回答案。
- 示例 1:
輸入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
輸出:["AAAAACCCCC","CCCCCAAAAA"]
- 示例 2:
輸入:s = "AAAAAAAAAAAAA"
輸出:["AAAAAAAAAA"]
提示:
0 <= s.length <= 105
s[i]=='A'、'C'、'G' or 'T'
方法一:哈希表(Java)
我們可以用一個哈希表統(tǒng)計(jì) ss 所有長度為 1010 的子串的出現(xiàn)次數(shù),返回所有出現(xiàn)次數(shù)超過 1010 的子串。
代碼實(shí)現(xiàn)時,可以一邊遍歷子串一邊記錄答案,為了不重復(fù)記錄答案,我們只統(tǒng)計(jì)當(dāng)前出現(xiàn)次數(shù)為 22 的子串。
思路:用map存儲子串出現(xiàn)的次數(shù),循環(huán)dna序列,每次截取長度為10的子串,加入map中 并更新出現(xiàn)的次數(shù),次數(shù)超過2,加入ans
能做兩個優(yōu)化:
- 統(tǒng)計(jì)字符串的時候,可以通過位運(yùn)算來壓縮hashmap的key的大小。由于只用了 'A' 'C' 'G' 'T' 四個字符,我們可以用兩位二進(jìn)制來標(biāo)記每種類型。長度為10的字符串一共需要20位二進(jìn)制表示,用一個int即可標(biāo)記出來。
- 滑動窗口,不用從每個位置開始往后數(shù)十個位置來統(tǒng)計(jì)字符串。由于前面已經(jīng)用了位運(yùn)算映射字符串到int,我們可以直接通過<<和|操作即可實(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 的長度,L=10 即目標(biāo)子串的長度。
時間復(fù)雜度:O(N*L)
空間復(fù)雜度:O(N*L)
方法二:哈希表——優(yōu)化(Go)
具體的方法思路已經(jīng)在上文中表述,該方法為哈希表的優(yōu)化方法。
由于 ss 中只含有 44 種字符,我們可以將每個字符用 22 個比特表示,即:
A 表示為二進(jìn)制 00;
C 表示為二進(jìn)制 01;
G 表示為二進(jìn)制 10;
T 表示為二進(jìn)制 11。
如此一來,一個長為 10 的字符串就可以用 20 個比特表示,而一個 int 整數(shù)有 32 個比特,足夠容納該字符串,因此我們可以將 ss 的每個長為 10 的子串用一個 int 整數(shù)表示(只用低 20 位)。
注意到上述字符串到整數(shù)的映射是一一映射,每個整數(shù)都對應(yīng)著一個唯一的字符串,因此我們可以將方法一中的哈希表改為存儲每個長為 10 的子串的整數(shù)表示。
方法思路:
- 滑動窗口向右移動一位:x = x << 2,由于每個字符用 2 個比特表示,所以要左移 2 位;
- 一個新的字符 ch 進(jìn)入窗口:x = x | bin[ch],這里 bin[ch] 為字符 ch 的對應(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序列的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
MyBatis映射文件resultMap元素中使用多個association的方法
這篇文章主要介紹了MyBatis映射文件resultMap元素中使用多個association的方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03基于Spring p標(biāo)簽和c標(biāo)簽注入方式
這篇文章主要介紹了Spring p標(biāo)簽和c標(biāo)簽注入方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-09-094位吸血鬼數(shù)字的java實(shí)現(xiàn)思路與實(shí)例講解
今天小編就為大家分享一篇關(guān)于4位吸血鬼數(shù)字的java實(shí)現(xiàn)思路與實(shí)例講解,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧2019-03-03SpringBoot實(shí)現(xiàn)WebSocket全雙工通信的項(xiàng)目實(shí)踐
本文主要介紹了SpringBoot實(shí)現(xiàn)WebSocket全雙工通信的項(xiàng)目實(shí)踐,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05