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