重复的DNA序列

方法一：

枚举所有长度为10的子串，插入到哈希表中，记录数量。遍历哈希表，存储出现次数超过1次的子串。复杂度O(N)

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        map<string,int> word_map;//<子串，子串数量>
        for(int i =0;i<s.size() ;++i)
        {
            string str = s.substr(i,10);
            if(word_map.find(str) != word_map.end())
            {
                word_map[str]++;
            }else{
                word_map[str] = 1;
            }
        }
        
        vector<string> res;
        for(auto p = word_map.begin();p!=word_map.end();++p)
        {
            if(p->second > 1)
                res.push_back(p->first);
        }
        
        return res;
    }
};

方法2：

将长度为10的DNA序列编码：A,C,G,T四个字符分别用0,1,2,3（00,01,10,11）表示，所以

AAAAACCCCT->最低位00 00 00 00 00 01 01 01 01 11最高位，表示成 11 01 01 01 01 00 00 00 00 00 = 873472

1.设置全局整数hash， int hash_map[1048576],1048576 = 2^20,表示所有长度为10的DNA序列

2.将DNA字符串的前10个字符使用左移位运算转换为整数key,hash_map[key]++

3.从第11个字符开始，按顺序遍历各个字符，遇到1个字符，就将key右移2位（就是去掉最低位的意思），然后将新的字符转为整数后，或运算 到最高位（19,20这两位），hash_map[key]++

key= key >> 2;

key = key |(A(00) << 18);

4.遍历哈希表，若hash_map[i]>1，将i从低位到高位转换为10个字符的DNA序列，push到结果。

int hash_map[1048576] = {0};//哈希太大，需要全局数组

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        if(s.size() < 10)
            return res;
        
        for(long i = 0;i<1048576;++i)////每次调用需要更新全局数组
            hash_map[i] = 0;
        
        long char_map[128] ={0};
        char_map['A'] = 0;
        char_map['C'] = 1;
        char_map['G'] = 2;
        char_map['T'] = 3;
        
        long key = 0;
        for(int i =9;i>=0;--i)//将前10个字符先转为key
            key = (key <<2) + char_map[s[i]];
        
        hash_map[key] = 1;
        
        for(int i =10;i<s.length();++i)//从第10个字符开始，先去掉最低位的字符，再把新的最高位的添加上去
        {
            key = key >> 2;
            key = key | (char_map[s[i]] << 18);
            hash_map[key]++;
        }
        
        for(long i =0;i<1048576;i++)
        {
            if(hash_map[i] > 1)
                res.push_back(change_int_to_DNA(i));
        }
        
        return res;
    }
    
    string change_int_to_DNA(long DNA)
    {
        const char DNA_CHAR[] = {'A','C','G','T'};
        string str;
        for(int i = 0;i<10;++i)//将编码还原成DNA序列
        {
            str += DNA_CHAR[DNA & 3];
            DNA = DNA >> 2;
        }
        return str;
    }
    
};