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