LeetCode187. 重複的DNA序列 --哈希表+排序

1. 重複的DNA序列

所有 DNA 都由一系列縮寫為 ‘A’，‘C’，‘G’ 和 ‘T’ 的核苷酸組成，例如：“ACGAATTCCG”。在研究 DNA 時，識别 DNA 中的重複序列有時會對研究非常有幫助。

編寫一個函數來找出所有目标子串，目标子串的長度為 10，且在 DNA 字元串 s 中出現次數超過一次。

示例 1：

輸入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”

輸出：[“AAAAACCCCC”,“CCCCCAAAAA”]

示例 2：

輸入：s = “AAAAAAAAAAAAA”

輸出：[“AAAAAAAAAA”]

提示：

0 <= s.length <= 105
s[i] 為 'A'、'C'、'G' 或 'T'
           

題解

直接将字元串編碼哈希處理成數字，然後為了避免不同的字元串取模後數值一樣，是以采用雙重編碼，儲存到結構體中，并且保留每個字元串組成的數字的位置，然後排序，累計每個字元串出現的次數。

AC代碼

class Solution {
public:
    typedef long long ll;
    ll mod1=1000000007,mod2=1000000000000007;
    struct Node
    {
        ll ans1,ans2;//哈希值
        int pos;//表示位置
        int sum;//表示出現次數
    }q[100010],q2[100010];
    static int cmp(Node a1,Node a2)
    {
        if(a1.ans1<a2.ans1)return true;
        else if(a1.ans1==a2.ans1)
        {
            return a1.ans2<a2.ans2;
        }
        else
        return false;
    }
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string>res;
        if(s.length()<10)
        {
            return res;
        }
        ll ans1=0,ans2=0,base1=1,base2=1;
        for(int i=9;i>=0;i--)
        {
            ans1+=(s[i]-'A')*base1;
            ans1%=mod1;
            if(i>0)
            {
                base1*=26;
                base1%=mod1;                
            }
            ans2+=(s[i]-'A')*base2;
            ans2%=mod2;
            if(i>0)
            {
                base2*=26;
                base2%=mod2;                
            }
        }
        Node t;
        t.ans1=ans1,t.ans2=ans2,t.pos=0;
        t.sum=1;
        q[0]=t;
        int id=0;
        for(int i=10;i<s.length();i++)
        {
            ans1=(ans1+mod1- ((s[i-10]-'A')*base1%mod1))%mod1;
            ans1*=26;
            ans1%=mod1;
            ans1+=(s[i]-'A');
            ans1%=mod1;

            ans2=(ans2+mod2-((s[i-10]-'A')*base2%mod2))%mod2;
            ans2*=26;
            ans2%=mod2;
            ans2+=(s[i]-'A');
            ans2%=mod2;

            t.ans1=ans1,t.ans2=ans2,t.pos=i-10+1;
            t.sum=1;
            q[++id]=t;
        }
        sort(q,q+id+1,cmp);
        //for(int i=0;i<=id;i++)
        //cout<<q[i].ans1<<" "<<q[i].ans2<<endl;
        int id2=0;
        q2[id2]=q[0];
        for(int i=1;i<=id;i++)
        {
            if(q[i].ans1==q2[id2].ans1&&q[i].ans2==q2[id2].ans2)
            {
                q2[id2].sum++;
            }
            else
            {
                q2[++id2]=q[i];
            }
        }
        for(int i=0;i<=id2;i++)
        {
            if(q2[i].sum>1)
            {
                string t;
                for(int j=q2[i].pos;j<q2[i].pos+10;j++)
                t+=s[j];
                res.push_back(t);
            }
        }
        return res;
    }
};