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;      }  };