[LeetCode] Repeated DNA Sequences

这个是原题的链接
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,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

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

大概就是说给一个DNA字符串,找出重复的长度为10的重复DNA序列

第一眼看过去这应该不是直接Hash,可能会爆

看别人题解,发现有人用位操作,把一个10长度的字符串映射为一个int,这样省了许多内存,因为只有A、T、C、G四个字母,那么把他们对应成数字就好了

大家解法都不一样,大致思路都是映射成一个int,比如 ACCGT 如果映射为16进制,
就是T*16^0 + G*16^1 + C*16^2 + C*16*3 + A*16^4,当然16太大的时候比较容易爆

所以基本上就剩下2,8,10三个进制可以选择,我们先看看几种进制下ACGT的值再定论
binary octal digit hex
A 0b1000001 0101 65 0x41
C 0b1000011 0103 67 0x43
G 0b1000111 0107 71 0x47
T 0b1010100 0124 84 0x54

我们发现8,10,16进制最后一位是不一样的,2进制虽然不一样其实也能做,但后面还会再讨论他的情况

如果每位不一样,就相当于一个key,ACGT这个序列是不是就变成了1374
如果表示成int,这小很多,下面我们说怎么存这个int

10的二进制是1010,长度为10需要40为,这已经超32位爆了,16进制当然也爆了
然后我们看8是32位刚好(3 10 = 30 位),2进制需要(2 10 = 20 位)

8进制下,长度小于10其实也不会产生key的冲突
思路就不继续一步步详解了,和上面一样,那么我们来看一下2进制行不行

我们用2进制做的时候,第一下肯定想先把ACGT对应成不超过3的四个数字0,1,2,3
然后我们修改一下代码

unordered_map<char, int> val = { {'A',0},{'C',1},{'G',2},{'T',3} };
int allOne = 0x3ffff; // 20 len binary digit
// ...
for (int i = 0; i < s.length(); i++) {
    bi = (bi << 2 | val[ s[i] ] ) & allOne;
    // ...

发现没有问题

下午算了好几次把长度算错了,allOne的值也没算对…后来搞对了…
python的bin()函数返回的字符串包括前面两个‘0b’,所以要减掉2位…我一直忘了…测试好久

然后下面先给出3bit代表一个字符(就是8进制的)AC代码

vector<string> findRepeatedDnaSequences(string s) {
    unordered_map<int, int> m;
    vector<string> ans;
    int allOne = 0x3fffffff; // 32 len digit
    int bi = 0; // octal index
    for (int i = 0; i < s.length(); i++) {
        bi = (bi << 3 | (s[i] & 7) ) & allOne;
        if (i >= 9 && m[ bi ]++ == 1) {
            ans.push_back(s.substr(i - 9, 10));
        }
    }
    return ans;
}

所以这个题基本上就是提醒计算各种进制转换的时候一定要小心,注意,不要出一些眼睛很难看出来的小错误