leetcode 187 重复的DNA序列(哈希or+位运算解决)-白红宇

leetcode 187 重复的DNA序列(哈希or+位运算解决)

阅读量：2433 次

发布时间：2019-05-10

本文共 2769 字，大约阅读时间需要 9 分钟。

所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。

示例：

输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”

输出：[“AAAAACCCCC”, “CCCCCAAAAA”]

算法思路1：

枚举DNA字符串中所有长度为10的子串，将其插入到哈希map中，并记录子串的数量；遍历哈希map，将所有出现超过一次的子串储存到结果，算法复杂度为O(n)

class Solution {
   public:    vector
   
     findRepeatedDnaSequences(string s) {
           map
    
      word_map;        vector
     
       result;        for (int i = 0; i < s.length(); i++){
               string word = s.substr(i, 10);            if (word_map.find(word) != word_map.end()){
       //若word在哈希中出现                word_map[word] ++;            }            else{
                   word_map[word] = 1;            }        }        map
      
       ::iterator it;        for (it = word_map.begin(); it != word_map.end(); it++){
               if (it->second > 1){
                   result.push_back(it->first);            }        }        return result;    }};

算法思路2：

将字符串哈希变为整数的哈希

将长度为10的DNA序列进行整数编码：

A，C，G 和 T 4个字符分别用[0,1,2,3] (二进制(00,01,10,11))所表示，故长度为10的DNA序列可以用20个比特位的整数所表示，可以采用整数映射进行解决

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

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

（key = key >> 2）

3、从DNA的第11个字符串开始，按顺序遍历各个字符，遇到第1个字符即将key右移2位(去掉最低位)，并且将新的DNA字符s[i]转化为整数后，或到最高位(第19、20位)，hash_map[key]++

(需要滑动窗口，去掉最后一个字符，添加新的首字符)

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

int hash_map[1048576] = {
   0};   //哈希太大，需要全局数组class Solution {
   public:    vector
   
     findRepeatedDnaSequences(string s) {
           vector
    
      result;        if (s.length() < 10){
               return result;        }        for (int i = 0; i < 1048576; i++){
       //每次调用时需要更新全局数组            hash_map[i] = 0;        }        int char_map[128] = {
   0};        char_map['A'] = 0;        char_map['C'] = 1;        char_map['G'] = 2;        char_map['T'] = 3;        int key = 0;        for (int i = 9; i >= 0; i--){
               key = (key << 2) + char_map[s[i]];   //将DNA字符串的前10个字符转化为数值key        }        hash_map[key] = 1;        for (int i = 10; i < s.length(); i++){
               key = key >> 2;            key = key | (char_map[s[i]] << 18);            hash_map[key]++;        }        for (int i = 0; i < 1048576; i++){
               if (hash_map[i] > 1){
                   result.push_back(chang_into_DNA(i));            }        }        return result;    }    string chang_into_DNA(int DNA){
           static const char DNA_CHAR[] = {
   'A','C','G','T'};        string str;        for (int i = 0; i < 10; i++){
               str += DNA_CHAR[DNA & 3];     //将一个长度为10的片段，从整数转为字符串，&3将所有最高位都&没了，为0，只有可能00、01、10、11            DNA = DNA >> 2;     //向右移动2位，除以4        }        return str;    }};

转载地址：http://avxmb.baihongyu.com/

你可能感兴趣的文章