首页 > 代码库 > [LeetCode]Repeated DNA Sequences

[LeetCode]Repeated DNA Sequences

2024-09-17 16:28:44   217人阅读

题目：Repeated DNA Sequences

给定包含A、C、G、T四个字符的字符串找出其中十个字符的重复子串。

思路：

首先，string中只有ACGT四个字符，因此可以将string看成是1,3,7,20这三个数字的组合串；

并且可以发现{ACGT}%5={1,3,2,0};于是可以用两个位就能表示上面的四个字符；

同时，一个子序列有10个字符，一共需要20bit，即int型数据类型就能表示一个子序列；

这样可以使用计数排序的思想来统计重复子序列；

这个思路时间复杂度只有O(n)，但是空间复杂度2^20byte辅助空间；

vector<string> LeetCode::findRepeatedDnaSequences(string s){
    vector<string> ret;
    if (s.size() < 11)return ret;
    char count[1048576] = {0};//0x000fffff = 1048575
    int index = 0;
    for (size_t i = 0; i < 9; ++i){//先求第一个子序列
        int value = http://www.mamicode.com/s[i] - ‘A‘ + 1;//char转成int
        value %= 5;//对5求余，转成2bit的大小
        index = index << 2 | value;//合并成一个值
    }
    for (size_t i = 9; i < s.size(); ++i){
        int value = http://www.mamicode.com/s[i] - ‘A‘ + 1;//char转成int
        value %= 5;//对5求余，转成2bit的大小
        index = index << 2 | value;//合并成一个值
        index = index & 0x000fffff;//清除前面移位的高位无效数字
        ++count[index];
        if (count[index] < 0)count[index] = 3;
        if (count[index] == 2){//防止重复加入
            ret.push_back(s.substr(i - 9, 10));
        }
    }
    return ret;
}

 

[LeetCode]Repeated DNA Sequences


联系
我们