看到檢測有沒有重復(fù)這種涧偷，我想了一下還是用了HashMap第岖，其實可以優(yōu)先用Set的，專門為這種情況設(shè)計的柿赊，分糖那題就是這樣俩功。
if (map.get(key) == 2)這個操作還是蠻風(fēng)騷的。
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;
}
我發(fā)現(xiàn)我容易懼怕瞻颂，然后就開始磨時間豺谈，但實際上一旦懂了其中的原理一下子啥都清楚明了了。
比如這個操作贡这，我一開始看不懂的是for循環(huán)里那個<<和|是干嘛的茬末，后來在紙上畫了一下，就發(fā)現(xiàn)<<操作就相當(dāng)于把DNA鏈往左拉2 bits，那么低位自動補(bǔ)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
