很重要的一道题

题型适合在面试的时候考

位操作和哈希表结合

public List findRepeatedDnaSequences(String s) {
/*
寻找出现过一次以上的十个字母长的子串
最简单的想法是把每个长度为10的子串存到hashtable中，但是这肯定不符合出题人的意思，要考察位操作
看了答案，使用位操作，第一次做bit manipulation的题
由于A\C\G\T的ASCII码，后三位各不相同，所以我们只要考虑字符的后三位就行
用一个int类型来代表遍历序列，每次把一个字符添加到序列末尾（添加方式是左移3位然后|上下一个字符的后三位）
这样每次用一个掩码提取后27位并|后一位字符代表当前子串，记录到hashtable中，这样用一个int数字代替一个子串，
会节省内存
这里不直接提取后30位的原因是，如果提取30位再向左移3位会超出int范围，而且32位计算机会溢出
所以先提取27位再左移再或
*/
int l = s.length();
List res = new ArrayList<>();
if(l<=10) { return res; } Map map = new HashMap<>();
//位操作序列
int cur = 0;
//掩码1,用来提取后27位
int mask = 0x7ffffff;
//先把前27位添加上，以后就可以循环实现了

    for (int i = 0; i < 9; i++) {  
        //每次左移3位，空出位置用于添加，&7是提取后三位  
        cur  = (cur<<3)|(s.charAt(i)&7);  
    }  
    //开始记录和查询  
    for (int i = 9; i < l; i++) {  
        cur = ((cur&mask)<<3)|(s.charAt(i)&7);  
        map.put(cur,map.getOrDefault(cur,0)+1);  
        //只在第二次出现时添加，第三次，第四次...不添加  
        //一开始想着全部添加到map中在遍历key来添加，但是发现那时候就没有字符index：i了，如果用key还原子串很麻烦  
        if (map.get(cur)==2)  
            res.add(s.substring(i-9,i+1));  
    }  
    return res;  
    }