力扣_字符串10—重复的DNA序列-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣_字符串10—重复的DNA序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

DNA序列由一系列核苷酸组成，缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’.。

例如，“ACGAATTCCG” 是一个 DNA序列。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列的字符串 s ，返回所有在 DNA 分子中出现不止一次的长度为 10 的序列(子字符串)。你可以按任意顺序返回答案。

示例 1：

输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
输出：[“AAAAACCCCC”,“CCCCCAAAAA”]文章来源地址https://www.toymoban.com/news/detail-827755.html

方法

哈希+滑动窗口
- 由于 s 中只含有 4 种字符，我们可以将每个字符用 2 个比特表示，即：
  - A 表示为二进制 00
  - C 表示为二进制 01
  - G 表示为二进制 10
  - T 表示为二进制 11
- 我们可以将 s 的每个长为 10 的子串用一个 int 整数表示（只用低 20 位），该 int 作为哈希表的key
- 窗口每次向右滑动一个字符，左边的两个 bit 滑出，右边滑入两个新的 bit

代码

class Solution {
public:
    // vector<string> findRepeatedDnaSequences(string s) {
    //     int n = s.size();
    //     map<string, int> maps;
    //     for(int i = 0; i <= n-10; i++){
    //         maps[s.substr(i, 10)]++;
    //     }
    //     vector<string> ret;
    //     for(auto it : maps){
    //         if(it.second > 1){
    //             ret.push_back(it.first);
    //         }
    //     }
    //     return ret;
    // }

    vector<string> findRepeatedDnaSequences(string s){
        int n = s.size();
        map<char, int> maps = {{'A', 0}, {'T', 1}, {'C', 2}, {'G', 3}};
        map<int, int> cnt;
        int x = 0;
        for(int i = 0; i < 10-1; i++){
            x = (x<<2) | maps[s[i]];
        }
        vector<string> ret;
        for(int i = 0; i <= n-10; i++){
            x = ((x << 2) | maps[s[i + 10 - 1]]) & ((1 << (10 * 2)) - 1);
            if(cnt[x] < 2){
                cnt[x]++;
                if(cnt[x] == 2){
                    ret.push_back(s.substr(i, 10));
                }
            }
        }
        return ret;
    }
};