重復(fù)的DNA序列

所有 DNA 由一系列縮寫(xiě)為 A，C，G 和 T 的核苷酸組成，例如："ACGAATTCCG"。在研究 DNA 時(shí)，識(shí)別 DNA 中的重復(fù)序列有時(shí)會(huì)對(duì)研究非常有幫助。

編寫(xiě)一個(gè)函數(shù)來(lái)查找 DNA 分子中所有出現(xiàn)超多一次的10個(gè)字母長(zhǎng)的序列（子串）。

示例:

輸入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

?

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

?

思路：將字符串中所有長(zhǎng)度為10的子串以及出現(xiàn)的次數(shù)用map保存，但是需要消耗很大的空間。

考慮到只有4中可能的字符A,C,G,T;可以對(duì)字符進(jìn)行編碼，用2bit來(lái)表示一個(gè)字符，一個(gè)含有10個(gè)字符的子串只要20bit就能表示，用一個(gè)int類(lèi)型就能表示。

總長(zhǎng)度為n的字符串，可能的子串共有n-9種，因此最多用n-9個(gè)int就能表示所有的字符組合。最壞的情況下，20bit共有2^20中組合，即1024*1024，

一個(gè)int類(lèi)型4byte,因此額外消耗4MB的二外空間。

?

1 class Solution { 2 public List<String> findRepeatedDnaSequences(String s) { 3 List<String> list = new ArrayList<String>(); 4 if(s.length() < 10) return list; 5 Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 6 for(int i=10; i<=s.length(); i++) { 7 int result = 0; 8 for(int j=i-10, k=0; j<i; j++,k++) { 9 char c = s.charAt(j); 10 int num = 0; 11 switch(c) { 12 case 'A': num = 0; break; 13 case 'C': num = 1; break; 14 case 'G': num = 2; break; 15 case 'T': num = 3; break; 16 } 17 result += (num << 2*(9-k)); 18 } 19 if(map.containsKey(result) && map.get(result) == 0) { 20 list.add(s.substring(i-10, i)); 21 map.put(result, 1); 22 } else if(!map.containsKey(result)) 23 map.put(result, 0); 24 } 25 return list; 26 } 27 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/kexinxin/p/10202996.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的Leetcode 187.重复的DNA序列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。