摘要：題目要求所有的都是有這四個字母組成的，比如。這個問題要求我們在一個序列中找到出現(xiàn)超過兩次的長度為的子序列。因為個字母意味著每個字母至少需要位才能表示出來。因為每個字符串對應(yīng)的二進制長度為，小于整數(shù)的，因此是可行的。
題目要求
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"].
所有的DNA都是有A,C,G,T這四個字母組成的，比如“ACGAATTCCG”。在研究DNA的時候，從DNA序列中找到重復(fù)出現(xiàn)的模式是很有用的。這個問題要求我們在一個DNA序列中找到出現(xiàn)超過兩次的長度為10的子序列。
比如，假設(shè)DNA序列為AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT，那么找到的滿足條件的子序列為["AAAAACCCCC", "CCCCCAAAAA"]
思路一：直接比較String
其實，我們只需要找到所有的長度為10的子序列并且判斷這些子序列是否存在重復(fù)就可以了。如果不考慮生成子字符串的過程，那么這個算法只需要遍歷一次字符串就可以完成了。
代碼如下：
public List findRepeatedDnaSequences(String s) {
//記錄不是第一次遍歷到的結(jié)果
Set result = new HashSet();
//記錄第一次遍歷到的結(jié)果
Set visited = new HashSet();
for(int i = 0 ; i(result);
}
思路二：將String轉(zhuǎn)化為Integer
上一題的思路其實基本沒有問題，唯一的缺點是，一個長度為n的字符串能夠產(chǎn)生n-9個長度為10的子字符串。這n-9個子字符串所占用的空間將會遠遠超過n-9個整數(shù)所占用的空間。如果之間存儲字符串，那么很可能會造成內(nèi)存溢出。因此我們需要考慮將字符串轉(zhuǎn)化為整數(shù)并存儲。
其實如果是將26個字母全部轉(zhuǎn)化為整數(shù)，并用整數(shù)表示任意10個字母所組成的字符串是不可能的。因為26個字母意味著每個字母至少需要5位才能表示出來。比如00000代表A， 00001代表B。而10個字母意味著需要5*10=50位，而一個整形是32位。
而本題中，只有四個字母A，C，G和T，只需要兩位就可以表示這四個字母，分別是:
A----00----0
C----01----1
G----10----2
T----11----3
那么ACGAATTCCG對應(yīng)的二進制碼就是00 01 10 00 00 11 11 01 01 10, 再將這個二進制數(shù)轉(zhuǎn)換成對應(yīng)的十進制數(shù)。因為每個字符串對應(yīng)的二進制長度為20，小于整數(shù)的32，因此是可行的。
代碼如下：
public List findRepeatedDnaSequences2(String s){
List result = new ArrayList();
Set firstTime = new HashSet();
Set secondTime = new HashSet();
//也可以使用hashmap，但是用數(shù)組的話可以很好的提升性能
char[] map = new char[26];
map["A"-"A"] = 0;//00
map["C"-"A"] = 1;//01
map["G"-"A"] = 2;//10
map["T"-"A"] = 3;//11
char[] sArray = s.toCharArray();
for(int i = 0 ; i
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/70814.html
