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