Leetcode 187 Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Solution: 
基本思路，每十个字符当成一个string扫描。map里面没有就存入map,map里有且之前没有存入result中就存入，如果已经存过就跳过。
难点：string存入map太占地方，每个字符一个byte，每个string要10个byte。解决方法用bit map：ACGT一共4种二进制编码：A:00,C:01,G:10,T:11,每个字符只需要2bit，每个string 20bit=3bytes就够了。

1.每十个字符当成一个string扫描，对每个字符转换成int。
转换方法：按字符扫描，原结果左移2位，然后最低两位按编码设定即可。
如：GTCA：
第一次扫描A： result=10b
第二次扫描T: result先左移2位：result=1000b，再设置最低2位为11：result=1011b
第三次赛秒C：result先左移2位(<<2)，再最低2位设置为二进制01 (和01b与)： result = result<<2 |01
注意：上面都是二进制数，但是c++没有直接二进制数的表达方法，所以要转换成10进制数进行与运算。

2. 如果map里面没有，就存入map，设置个数为1。
如果map里面已有，且个数为1，表示之前有且仅有一个，则记录在result里，改变个数为-1；如果map里面有，但是个数不为1，代表已经记录在result了，不操作。

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        if (s.size()<10)
            return res;
        unordered_map<int,int> mp;
        for (int i=0;i<(int)s.size()-9;i++)
        {
            string tmp_str = s.substr(i,10);
            int str_val = strToInt(tmp_str);
            if (mp.find(str_val)==mp.end())
            {
                mp[str_val]=1;
            }
            else
            {
                if (mp[str_val]==1)
                {
                    mp[str_val]=-1;
                    res.push_back(tmp_str);
                }
            }
        }
        return res;
    }
    int strToInt(string s)
    {
        int res=0;
        for (int i=0;i<s.size();i++)
        {
            if (s[i]=='A')
                res = res<<2;
            else if (s[i]=='C')
                res = res<<2|1;
            else if (s[i]=='G')
                res = res<<2 |2;//binary 10 = 2
            else
                res = res <<2 |3;//binary 11 = 3
        }
        return res;
    }
};