187. 重复的DNA序列

方法1：滑动窗口+map

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

class Solution {
    public:
        vector<string> findRepeatedDnaSequences(string s) {
            map<string,int>mymap;
            string tmp;
            vector<string> res;
            if(s.size()<=10)return res;

            for(int i=0; i<=s.length()-10; i++) {
                tmp=s.substr(i,10);
                if(mymap.find(tmp)!=mymap.end())
                    mymap[tmp]=1;
                else
                    mymap[tmp]=0;
            }
            for(auto it=mymap.begin();it!=mymap.end();it++){
                if(it->second==1){
                    res.push_back(it->first);
                }
            }
            return res;
        }
};
int main() {
    Solution s;
    string str("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
    vector<string> res;
    res=s.findRepeatedDnaSequences(str);
    for(int i=0; i<res.size(); i++) {
        cout<<res[i]<<endl;
    }
    return 0;
}

方法2：滑动窗口+位运算

S1是第一次出现就会被set，S2是第二次出现才会被set。
不要看bitset<1<<20> S1;开得很大，是，俩加起来也才

class Solution {
public:
    int returnChar(char c){
        switch(c){
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'G':
                return 2;
            case 'T':
                return 3;
        }
        return 0;
    }
    vector<string> findRepeatedDnaSequences(string s) {
        int n = s.length();
        vector<string> res;
        if(n<=10) return res;
        bitset<1<<20>S1;
        bitset<1<<20>S2;
        int val = 0;
        for(int i=0;i<10;++i)
            val = (val<<2)|returnChar(s[i]);
        S1.set(val);
        int mask = (1<<20)-1;
        for(int i=10;i<n;++i){
            val = ((val<<2)&mask)|returnChar(s[i]);
            if(S2[val])
                continue;
            if(S1[val]){
                res.push_back(s.substr(i-9,10));
                S2.set(val);
            }else{
                S1.set(val);
            }
        }
        
        return res;
    }
};