摘要：题目要求所有的都是有这四个字母组成的，比如。这个问题要求我们在一个序列中找到出现超过两次的长度为的子序列。因为个字母意味着每个字母至少需要位才能表示出来。因为每个字符串对应的二进制长度为，小于整数的，因此是可行的。
题目要求
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
想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/70814.html
