這篇文章主要介紹“C++怎么求重復的DNA序列”的相關知識,小編通過實際案例向大家展示操作過程,操作方法簡單快捷,實用性強,希望這篇“C++怎么求重復的DNA序列”文章能幫助大家解決問題。
公司主營業務:做網站、網站建設、移動網站開發等業務。幫助企業客戶真正實現互聯網宣傳,提高企業的競爭能力。成都創新互聯是一支青春激揚、勤奮敬業、活力青春激揚、勤奮敬業、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業文化,感謝他們對我們的高要求,感謝他們從不同領域給我們帶來的挑戰,讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。成都創新互聯推出前進免費做網站回饋大家。
Example:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]
看到這道題想到這應該屬于 CS 的一個重要分支生物信息 Bioinformatics 研究的內容,研究 DNA 序列特征的重要意義自然不用多說,但是對于我們廣大碼農來說,還是專注于算法吧,此題還是用位操作 Bit Manipulation 來求解,計算機由于其二進制存儲的特點可以很巧妙的解決一些問題,像之前的 Single Number 和 Single Number II 都是很巧妙利用位操作來求解。此題由于構成輸入字符串的字符只有四種,分別是 A, C, G, T,下面來看下它們的 ASCII 碼用二進制來表示:
A: 0100 0001 C: 0100 0011 G: 0100 0111 T: 0101 0100
由于目的是利用位來區分字符,當然是越少位越好,通過觀察發現,每個字符的后三位都不相同,故而可以用末尾三位來區分這四個字符。而題目要求是 10 個字符長度的串,每個字符用三位來區分,10 個字符需要30位,在 32 位機上也 OK。為了提取出后 30 位,還需要用個 mask,取值為 0x7ffffff,用此 mask 可取出后27位,再向左平移三位即可。算法的思想是,當取出第十個字符時,將其存在 HashMap 里,和該字符串出現頻率映射,之后每向左移三位替換一個字符,查找新字符串在 HashMap 里出現次數,如果之前剛好出現過一次,則將當前字符串存入返回值的數組并將其出現次數加一,如果從未出現過,則將其映射到1。為了能更清楚的闡述整個過程,就用題目中給的例子來分析整個過程:
首先取出前九個字符 AAAAACCCC,根據上面的分析,用三位來表示一個字符,所以這九個字符可以用二進制表示為 001001001001001011011011011,然后繼續遍歷字符串,下一個進來的是C,則當前字符為 AAAAACCCCC,二進制表示為 001001001001001011011011011011,然后將其存入 HashMap 中,用二進制的好處是可以用一個 int 變量來表示任意十個字符序列,比起直接存入字符串大大的節省了內存空間,然后再讀入下一個字符C,則此時字符串為 AAAACCCCCA,還是存入其二進制的表示形式,以此類推,當某個序列之前已經出現過了,將其存入結果 res 中即可,參見代碼如下:
解法一:
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;
}
};
上面的方法可以寫的更簡潔一些,這里可以用 HashSet 來代替 HashMap,只要當前的數已經在 HashSet 中存在了,就將其加入 res 中,這里 res 也定義成 HashSet,這樣就可以利用 HashSet 的不能有重復項的特點,從而得到正確的答案,最后將 HashSet 轉為 vector 即可,參見代碼如下
解法二:
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());
}
};
上面的方法都是用三位來表示一個字符,這里可以用兩位來表示一個字符,00 表示A,01 表示C,10 表示G,11 表示T,那么總共需要 20 位就可以表示十個字符流,其余的思路跟上面的方法完全相同,注意這里的 mask 只需要表示 18 位,所以變成了 0x3ffff,參見代碼如下:
解法三:
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());
}
};
如果不需要考慮節省內存空間,那可以直接將 10個 字符組成字符串存入 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()};
}
};
關于“C++怎么求重復的DNA序列”的內容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業相關的知識,可以關注創新互聯行業資訊頻道,小編每天都會為大家更新不同的知識點。
網站標題:C++怎么求重復的DNA序列
網頁URL:http://vcdvsql.cn/article28/gjggjp.html
成都網站建設公司_創新互聯,為您提供全網營銷推廣、網站改版、虛擬主機、網站制作、移動網站建設、網站策劃
聲明:本網站發布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網站立場,如需處理請聯系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創新互聯