看到检测有没有重复这种，我想了一下还是用了HashMap，其实可以优先用Set的，专门为这种情况设计的，分糖那题就是这样。
if (map.get(key) == 2)这个操作还是蛮风骚的。
MAP:
public List<String> findRepeatedDnaSequences(String s) {
List<String> res = new ArrayList<>();
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < s.length() - 9; i++) {
String key = s.substring(i, i + 10);
map.put(key, map.getOrDefault(key, 0) + 1);
if (map.get(key) == 2) {
res.add(key);
}
}
return res;
}
SET:
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);
}
这题是MEDIUM，所以肯定不能是这种难度，我看了解法，这个题目描述ACGT这种嘌呤嘧啶的DNA真是perfectly match位操作，而且<<左移这种就跟基因检录的模型一模一样。。所以下面有bit manipulation的操作：
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;
}
我发现我容易惧怕，然后就开始磨时间，但实际上一旦懂了其中的原理一下子啥都清楚明了了。
比如这个操作，我一开始看不懂的是for循环里那个<<和|是干嘛的，后来在纸上画了一下，就发现<<操作就相当于把DNA链往左拉2 bits，那么低位自动补0，然后|不是「异或」，而是「或」操作，就自动把读取到的那一位字母加到后面的integer上了。这样一共是10 char * 2 bits/char = 20 bits，而Java 里一个Char是4bytes = 32bits。
https://discuss.leetcode.com/topic/8894/clean-java-solution-hashmap-bits-manipulation
