实现LeetCode(187。找到重复的DNA序列)，和智伯。com将带你了解更多的信息。

[leetcode] 187。重复的DNA序列找到重复的DNA序列AlldnaisComposedofasieresofnuel otides abbreviatedasa，c，g和t，例如：‘acgaattccg’。学习dna时，有时会在DNA内使用。

Writeafunctiontofindallthe10所有出现一次以上的10个字母长的序列(子字符串)。

示例： input :s=' aaaaacccccaaaaaaccccaaaaaggttt '

输出： ['AAAAA CCCCC '' ccccaaaa ']看到这个问题，我觉得应该属于生物信息学的研究，cs的一个重要分支。研究DNA序列特征的意义不用多说，自然是有的，但是对于我们码农来说，还是把重点放在算法上吧。这个问题还是通过BitManipulation来解决。由于二进制存储的特点，计算机可以巧妙的解决一些问题，比如SingleNumber和SingleNumberII，这些问题都是通过比特操作巧妙地解决的。因为组成输入字符串的只有四个字符，即A、C、G和T，所以我们先来看看它们的二进制ASCII码：

a :01000001 c :01000011g :01000111t :01010100

因为目的是用比特来区分字符，当然比特越少越好。通过观察发现每个字符的后三位是不一样的，所以可以用后三位来区分这四个字符。题目要求10个字符的字符串，每个字符用3位区分，10个字符需要30位，在32位的电脑上是可以的。为了提取后30位，需要使用值为0x7ffffff的掩码。使用这个掩码，您可以提取最后27位，然后将它们左移三位。算法的思想是，当取出第十个字符时，存储在HashMap中，与这个字符串发生频率映射。然后，每三位数向左移动以替换一个字符，并找到新字符串在HashMap中的出现次数。如果它以前只出现过一次，当前字符串被存储在返回值数组中，并且它的出现次数增加1。如果它从未出现，则映射到1。为了更清楚地解释整个过程，用题目中给出的例子来分析整个过程：

首先把前九个字AAAAACCCCC拿出来。根据上面的分析，用三位来表示一个字符，那么这九个字符可以用二进制表示为001001001001011011011，然后继续遍历字符串。下一个是C，现在的角色是AAAAACCCCC。二进制表示为001001001001001001011011011011011，然后存储在HashMap中。二进制表示的好处是可以用一个int变量表示任意十个字符序列，比直接存储字符串大大节省了内存空间，然后读入下一个字符C，所以无论字符串是AAAACCCCCA还是存储在其二进制表示中，以此类推。

解决方案1:

class solution { public : vectorstringfindprepeateddna sequences(strings){ vector stringres；if(s . size()=10)returnres；intmask=0x7ffffff，cur=0；unordered_mapint，intmfor(inti=0；i9；I){ cur=(cur 3)|(s[I]7)；} for(inti=9；is . size()；I){ cur=((cur mask)3)|(s[I]7)；if(m . count(cur)){ if(m[cur]==1)RES . push _ back(s . substr(I-9，10))；m[cur]；} else { m[cur]=1；} } returnres}};上面的【187.求重复的DNA序列C++实现LeetCode】's方法可以写得更简洁。这里可以用HashSet代替HashMap。只要当前的数字已经存在于HashSet中，就会添加到res中，这里res也被定义为HashSet，这样你就可以利用HashSet不能有重复的特性得到正确答案，最后将HashSet转换为vector。参见下面的代码。

解决方案2:

class solution { public : vectorstringfindprepeateddna sequences(strings){ unordered _ setstringres；unordered _ setintstint cur=0；for(inti=0；i9；I)cur=cur 3 |(s[I]7)；for(inti=9；is . size()；I){ cur=((cur0x 7 ffffff)3)|(s[I]7)；if(ST . count(cur))RES . insert(s . substr(I-9，10))；elsest . insert(cur)；}returnvectorstring(res.begin()、RES . end())；}};

以上方法都是用三位来表示一个字符。这里，可以用两个比特来表示一个字符，00表示a，01表示c，10表示g，11表示t，所以总共需要20个比特来表示十个字符流。剩下的思路和上面的方法完全一样。注意这里的掩码只需要表示18位，所以变成了0x3ffff。参见下面的代码：