Cinte's Leetcode Record
0%

187. 重复的DNA序列

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

187. 重复的DNA序列

暴力法(超时)
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int n = s.size();
        unordered_set<string> set;
        for(int i = 0; i < n - 10; ++i)
        {
            if(s.find(s.substr(i, 10), i + 1) != std::string::npos)
                set.insert(s.substr(i, 10));
        }
        return vector<string>(set.begin(), set.end());
    }
};
哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_map<string, int> map;
        vector<string> ret;
        int n = s.size();
        for(int i = 0; i <= n - 10; ++i)
        {
            string sub = s.substr(i, 10);
            if(++map[sub] == 2)
                ret.push_back(std::move(sub));
        }
        return ret;
    }
};
用位运算来实现hash

c++中一般使用int值本身作为hash值

这里在O(1)时间内计算出hash

具体看题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int n = s.size();
        if(n < 11)
            return {};
        unordered_map<char, int> bin{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        int x = 0;
        for(int i = 0; i < 10; ++i)
            x = (x << 2) | bin[s[i]];
        unordered_map<int, int> map{{x, 1}};
        vector<string> ret;
        for(int i = 1; i < n - 9; ++i)
        {
            x = ((x << 2) | bin[s[i + 9]]) & ((1 << 20) - 1);
            if(++map[x] == 2)
                ret.push_back(s.substr(i, 10));
        }
        return ret;
    }
};
字符串哈希

参考

字符串哈希

看不懂