[leetcode] 187 Repeated DNA Sequences

（一）最一开始的做法是使用 map<string,int> 记录每个10个字符的字符串的个数，超过2就push_back进ans。但是MLE了，说明采用string并不是一个好方法。

下面是MLE的代码：

class Solution {public:vector<string> findRepeatedDnaSequences(string s) {vector <string> ans;map<string,int> mp;if(s.length()<10)return ans;for(int i=0;i<s.length()-10;i++)mp[s.substr(i,10)]++;map<string,int>::iterator it;for(it=mp.begin();it!=mp.end();++it){if(it->second>1)ans.push_back(it->first);}return ans;}};（二）看了下Tags，，提示要用位操作，让我想到了霍夫曼编码的前缀码的唯一性，所以这里可以采用如下标记：

A: 00 T:01 C:10 G:11一共10个字符，共20位，而一个int有32位，所以采用map<int,int> 的处理可以减少很多空间的占用。

我们时钟维护这样一个20位的空间，遍历的时候，先左移14位去掉第一个字符，然后右移12位在进行或操作添加新的尾部的字符，这样又起到了节省时间的作用。

class Solution {public:vector<string> findRepeatedDnaSequences(string s) {vector <string> ans;map <int,int> mp;map <char,int> cur;set<string> st;cur['A']=0;cur['T']=1;cur['C']=2;cur['G']=3;if(s.length()<10)return ans;int temp;for(int i=0;i<9;i++){temp<<=2;temp|=cur[s[i]];}// mp[temp]++;for(int i=9;i<s.length();i++){temp<<=14;temp>>=12;temp|=cur[s[i]];mp[temp]++;if(mp[temp]>=2)st.insert(s.substr(i-9,10));}set<string>::iterator it;for(it=st.begin();it!=st.end();it++)ans.push_back(*it);return ans;}};

版权声明：本文为博主原创文章，未经博主允许不得转载。

所有的赏赐都只是被用来奖励工作成果的。