题目：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中长度为10的重复子串。最简单的想法就是一个嵌套循环。但是我尝试了一下最终显示的是用时过长，无法正确提交。那么想想别的了思路呢，我们就想到了，把DNA遍历一遍，获得所有长度为10的子串，并将其保存在set中，然后每当添加新的子串时，如果该子串已经在set中，则说明其为重复子串。应该输出。但是这里如果直接添加到List当中，你会发现最终的输出结果的list中会有重复子串。所以这里使用两个set来过滤重复的子串。代码入下：
public static List<String> findRepeatedDnaSequences1(String s) { Set<String> tmp = new HashSet<>(); Set<String> res = new HashSet<>(); List<String> rr = new ArrayList<>(); for(int i=0; i<s.length()-9; i++){ String ss = s.substring(i, i+10); if(tmp.contains(ss)) res.add(ss); else tmp.add(ss); } for(String aa:res) rr.add(aa); return rr; }这段代码第一次运行时间击败了92%的用户。然后我在看discuss的时候发现了一段类似的代码，写得十分简洁。击败了60%的用户。如下：
public List<String> findRepeatedDnaSequences(String s) { Set seen = new HashSet(), repeated = new HashSet(); for (int i = 0; i + 9 < s.length(); i++) { String ten = s.substring(i, i + 10); if (!seen.add(ten)) repeated.add(ten); } return new ArrayList(repeated);}然后后来又运行了一次自己写的代码，发现也变成了只击败68%的用户。一脸茫然==所以呢，有的时候排名是一种衡量算法效率的方法，但可能会因为代码的风格习惯等因素，甚至是因为测试服务器不稳定==，即便使用了相同的方法也会造成不一样的结果，不必太过放在心上。 恩，还看到另外一种思路，使用移位运算，来获得10位字符串的唯一键值。相当于我代码里使用的求子串操作。在之前的题目中也碰到过一些使用位操作的解法，都很巧妙。但是无奈自己当年没有好好学位运算这方面的知识，所以总是想不到这种解法的思路和想法。还是要多多学习啊
public List<String> findRepeatedDnaSequences(String s) { Set<Integer> Words = new HashSet<>(); Set<Integer> doubleWords = new HashSet<>(); List<String> rv = new ArrayList<>(); char[] map = new char[26]; //map['A' - 'A'] = 0; map['C' - 'A'] = 1; map['G' - 'A'] = 2; map['T' - 'A'] = 3; for(int i = 0; i < s.length() - 9; i++) { int v = 0; for(int j = i; j < i + 10; j++) { v <<= 2; v |= map[s.charAt(j) - 'A']; } if(!words.add(v) && doubleWords.add(v)) { rv.add(s.substring(i, i + 10)); } } return rv;}新闻热点
疑难解答
