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,

代码语言：javascript复制

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

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

十个字符表示一个DNA序列，找出多次出现的序列。

移动头尾两个指针，用map存储已经探测过的序列，当该序列之前出现过一次的时候，则将它加入答案中。

在由前一个位置的序列得到下一个位置的序列时可以采用位运算的方式。

对AGCT四个字母编码，0，1，2，3，则两个bit可以表示一个字母，十个字符正好20bit，可以用int类型表示。

移动到下一位时用上一个位置的int值向高位移动2bit，然后或上新的2bit，在与0xfffff求与保留低20位。

代码语言：javascript复制

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        if(s.size() < 10) return res;
        unordered_map<int, int> mp;
        unordered_map<char, int> id;
        id['A'] = 0;
        id['C'] = 1;
        id['G'] = 2;
        id['T'] = 3;
        int temp = 0;
        for(int i = 0; i < s.size(); i  )
        {
            temp = (temp<<2| (id[s[i]] & 3)) & 0xfffff;
            if(i > 8)
            {
                if(mp[temp] == 1) res.push_back(s.substr(i - 9,10));
                mp[temp]  ;
            }
        }
        return res;
    }
};

bit function int map series

0 人点赞