Repeated DNA Sequences高频题

by **Admin** Sat Oct 21, 2017 4:38 pm

!word.add(value) && secondWord.add(value) 这行很妙
一般让你先讲怎么设计数据存储，代码已经反映了，用00,01,10,11,bit省空间
public List<String> findRepeatedDnaSequences(String s) {
List<String> result = new ArrayList<>();
Set<Integer> word = new HashSet<>();
Set<Integer> secondWord = new HashSet<>();
int[] map = new int[26];
map['C' - 'A'] = 1;
map['G' - 'A'] = 2;
map['T' - 'A'] = 3;
int value = 0;
for (int i = 0; i < s.length(); i++) {
value <<= 2;
value |= map[s.charAt(i) - 'A'];
value &= 0xfffff;
if (i < 9) {
continue;
}
if (!word.add(value) && secondWord.add(value)) {
result.add(s.substring(i - 9, i + 1));
}
}
return result;
}