187. Repeated DNA Sequences重复的DNA序列

qlmx
qlmx
qlmx
54
文章
2
评论
2020年2月15日00:12:47 评论 858阅读3分55秒

187. Repeated DNA Sequences(重复的DNA序列)

1 问题描述

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.

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

Example:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: ["AAAAACCCCC", "CCCCCAAAAA"]

2 C++

int g_hash_map[1048576] = {0}; //2^10=1048576
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> result;
        if(s.length() < 10)
            return result;
        for(int i=0; i<1048576; i++)
            g_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 ] ];
        }
        g_hash_map[key] = 1;
        for(int i=10; i<s.length(); i++) {
            key = key>>2;
            key = key | (char_map[ s [ i ] ] << 18);
            g_hash_map[key]++;
        }
        for(int i=0; i<1048576; i++) {
            if(g_hash_map[i] > 1) {
                result.push_back(change_int_to_DNA(i));
            }
        }
        return result;
    }
private:
    string change_int_to_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];
            DNA = DNA >> 2;
        }
        return str;
    }
};
继续阅读
  • 我的微信小程序
  • 这是我的微信小程序扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin
qlmx
  • 本文由 发表于 2020年2月15日00:12:47
  • 除非特殊声明,本站文章均为原创,转载请务必保留本文链接
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: