C++怎么求重復(fù)的DNA序列

這篇文章主要介紹“C++怎么求重復(fù)的DNA序列”的相關(guān)知識(shí)，小編通過(guò)實(shí)際案例向大家展示操作過(guò)程，操作方法簡(jiǎn)單快捷，實(shí)用性強(qiáng)，希望這篇“C++怎么求重復(fù)的DNA序列”文章能幫助大家解決問(wèn)題。

公司主營(yíng)業(yè)務(wù)：做網(wǎng)站、網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。成都創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來(lái)驚喜。成都創(chuàng)新互聯(lián)推出前進(jìn)免費(fèi)做網(wǎng)站回饋大家。

求重復(fù)的DNA序列

Example:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: ["AAAAACCCCC", "CCCCCAAAAA"]

看到這道題想到這應(yīng)該屬于 CS 的一個(gè)重要分支生物信息 Bioinformatics 研究的內(nèi)容，研究 DNA 序列特征的重要意義自然不用多說(shuō)，但是對(duì)于我們廣大碼農(nóng)來(lái)說(shuō)，還是專注于算法吧，此題還是用位操作 Bit Manipulation 來(lái)求解，計(jì)算機(jī)由于其二進(jìn)制存儲(chǔ)的特點(diǎn)可以很巧妙的解決一些問(wèn)題，像之前的 Single Number 和 Single Number II 都是很巧妙利用位操作來(lái)求解。此題由于構(gòu)成輸入字符串的字符只有四種，分別是 A, C, G, T，下面來(lái)看下它們的 ASCII 碼用二進(jìn)制來(lái)表示：

A: 0100 0001　　C: 0100 0011　　G: 0100 0111　　T: 0101 0100

由于目的是利用位來(lái)區(qū)分字符，當(dāng)然是越少位越好，通過(guò)觀察發(fā)現(xiàn)，每個(gè)字符的后三位都不相同，故而可以用末尾三位來(lái)區(qū)分這四個(gè)字符。而題目要求是 10 個(gè)字符長(zhǎng)度的串，每個(gè)字符用三位來(lái)區(qū)分，10 個(gè)字符需要30位，在 32 位機(jī)上也 OK。為了提取出后 30 位，還需要用個(gè) mask，取值為 0x7ffffff，用此 mask 可取出后27位，再向左平移三位即可。算法的思想是，當(dāng)取出第十個(gè)字符時(shí)，將其存在 HashMap 里，和該字符串出現(xiàn)頻率映射，之后每向左移三位替換一個(gè)字符，查找新字符串在 HashMap 里出現(xiàn)次數(shù)，如果之前剛好出現(xiàn)過(guò)一次，則將當(dāng)前字符串存入返回值的數(shù)組并將其出現(xiàn)次數(shù)加一，如果從未出現(xiàn)過(guò)，則將其映射到1。為了能更清楚的闡述整個(gè)過(guò)程，就用題目中給的例子來(lái)分析整個(gè)過(guò)程：

首先取出前九個(gè)字符 AAAAACCCC，根據(jù)上面的分析，用三位來(lái)表示一個(gè)字符，所以這九個(gè)字符可以用二進(jìn)制表示為 001001001001001011011011011，然后繼續(xù)遍歷字符串，下一個(gè)進(jìn)來(lái)的是C，則當(dāng)前字符為 AAAAACCCCC，二進(jìn)制表示為 001001001001001011011011011011，然后將其存入 HashMap 中，用二進(jìn)制的好處是可以用一個(gè) int 變量來(lái)表示任意十個(gè)字符序列，比起直接存入字符串大大的節(jié)省了內(nèi)存空間，然后再讀入下一個(gè)字符C，則此時(shí)字符串為 AAAACCCCCA，還是存入其二進(jìn)制的表示形式，以此類推，當(dāng)某個(gè)序列之前已經(jīng)出現(xiàn)過(guò)了，將其存入結(jié)果 res 中即可，參見(jiàn)代碼如下：

解法一：

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        if (s.size() <= 10) return res;
        int mask = 0x7ffffff, cur = 0;
        unordered_map<int, int> m;
        for (int i = 0; i < 9; ++i) {
            cur = (cur << 3) | (s[i] & 7);
        }
        for (int i = 9; i < s.size(); ++i) {
            cur = ((cur & mask) << 3) | (s[i] & 7);
            if (m.count(cur)) {
                if (m[cur] == 1) res.push_back(s.substr(i - 9, 10));
                ++m[cur]; 
            } else {
                m[cur] = 1;
            }
        }
        return res;
    }
};

上面的方法可以寫的更簡(jiǎn)潔一些，這里可以用 HashSet 來(lái)代替 HashMap，只要當(dāng)前的數(shù)已經(jīng)在 HashSet 中存在了，就將其加入 res 中，這里 res 也定義成 HashSet，這樣就可以利用 HashSet 的不能有重復(fù)項(xiàng)的特點(diǎn)，從而得到正確的答案，最后將 HashSet 轉(zhuǎn)為 vector 即可，參見(jiàn)代碼如下

解法二：

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_set<string> res;
        unordered_set<int> st;
        int cur = 0;
        for (int i = 0; i < 9; ++i) cur = cur << 3 | (s[i] & 7);
        for (int i = 9; i < s.size(); ++i) {
            cur = ((cur & 0x7ffffff) << 3) | (s[i] & 7);
            if (st.count(cur)) res.insert(s.substr(i - 9, 10));
            else st.insert(cur);
        }
        return vector<string>(res.begin(), res.end());
    }
};

上面的方法都是用三位來(lái)表示一個(gè)字符，這里可以用兩位來(lái)表示一個(gè)字符，00 表示A，01 表示C，10 表示G，11 表示T，那么總共需要 20 位就可以表示十個(gè)字符流，其余的思路跟上面的方法完全相同，注意這里的 mask 只需要表示 18 位，所以變成了 0x3ffff，參見(jiàn)代碼如下：

解法三：

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_set<string> res;
        unordered_set<int> st;
        unordered_map<int, int> m{{"A", 0}, {"C", 1}, {"G", 2}, {"T", 3}};
        int cur = 0;
        for (int i = 0; i < 9; ++i) cur = cur << 2 | m[s[i]];
        for (int i = 9; i < s.size(); ++i) {
            cur = ((cur & 0x3ffff) << 2) | (m[s[i]]);
            if (st.count(cur)) res.insert(s.substr(i - 9, 10));
            else st.insert(cur);
        }
        return vector<string>(res.begin(), res.end());
    }
};

如果不需要考慮節(jié)省內(nèi)存空間，那可以直接將 10個(gè) 字符組成字符串存入 HashSet 中，那么也就不需要 mask 啥的了，但是思路還是跟上面的方法相同:

解法四：

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_set<string> res, st;
        for (int i = 0; i + 9 < s.size(); ++i) {
            string t = s.substr(i, 10);
            if (st.count(t)) res.insert(t);
            else st.insert(t);
        }
        return vector<string>{res.begin(), res.end()};
    }
};

關(guān)于“C++怎么求重復(fù)的DNA序列”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。

網(wǎng)站標(biāo)題：C++怎么求重復(fù)的DNA序列
網(wǎng)頁(yè)URL：http://www.muchs.cn/article28/gjggjp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營(yíng)銷推廣、網(wǎng)站改版、虛擬主機(jī)、網(wǎng)站制作、移動(dòng)網(wǎng)站建設(shè)、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)