LeetCode 187. Repeated DNA Sequences(位运算，hash)

• 2020 年 2 月 14 日
• 筆記

题目

题意：判断一个DNA序列中，长度为10的子序列，重复次数超过1次的序列！

题解：用一个map 就能搞定了，但是出于时间效率的优化，我们可以用位运算和数组代替map，首先只有四个字母，就可以用00,01,10,11 四个二进制表示，长度为10的序列，可以用长度为20的二进制序列表示。这样每中组合都对应一个数字，然后用数组表示每个数字出现的次数就好了。

class Solution {  public:      int m[1<<21];      int m3[1<<21];      int m2[127];      char m4[4];      vector<string> findRepeatedDnaSequences(string s) {            m2['A']=0;          m2['C']=1;          m2['G']=2;          m2['T']=3;            m4[0]='A';          m4[1]='C';          m4[2]='G';          m4[3]='T';            int x=0;          for(int i=0;i<10&&i<s.length();i++)          {              x<<=2;              x |= m2[s[i]];            }            m[x]=1;            int y = (1<<18)-1;            vector<string> ans;            for(int i=10;i<s.length();i++)          {              x &= y;                x <<= 2;                x |= m2[s[i]];                m[x]++;                if(m[x]>1 && m3[x]==0)              {                 ans.push_back(fun(x));                 m3[x]=1;              }            }            return ans;        }        string fun(int x)      {          string s="";          int y ;          for(int i=19;i>=1;i-=2)          {              y = (1 << i) | ( 1<<(i-1));              int z = x&y;              z >>= (i-1);              s+=m4[z];          }            return s;      }  };