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”].
s思路： 1. 貌似見過。找重復，一般少不了hash。連續十個字母用hash即可，然后每次往右邊移動，移動一次就從左邊刪一個，保證隨時都是10個數，然后查表看是否在hash里。 2. 剛開始確實想到用unordered_map，但是寫的時候，發現沒必要就改用unordered_set，只需要查詢之前是否保存這個string,如果有，就push_back進入res。高高興興寫完，發現思考的不細致，如果一個string出現多次，那么第2次、第3次…第n次出現時都會發現之前出現過，那么就會重復把這個string輸出到結果里，顯然這不是我們要得答案。怎么辦？必須使用unordered_map對出現次數計數就可以解決！ 3. 思維的盲點是，沒有把整個第一次遇到，第二次遇到，甚至第n次遇到相同string的情況在腦海里面情景再現，而是急忙開始寫了！下次寫的時候，尤其是這種簡單的情況，需要把整個情況都先dry run一遍再動筆，其實更節約時間！ 4. 說說如何優化。用到簡單的編碼，以前學通信真是沒白學。首先，由于給的字符不是任意的，就只有4個不同的值，也就是說可以編碼成兩比特，10個值最多20個比特就可以表示了，因此，完全你可以把10個字符打包塞進一個int內，然后查hash就用int，省很多時間和空間！ 5. 這里應用了個小技巧，剛才說10個說壓縮成20bit就夠了，但是int可以裝32bit，那么還剩12bit空間。這個小技巧就是利用這個12bit空間。壓縮成20bit的話，就要每次手工用if-else把ACGT轉換成0,1,2,3，這樣做當然是可以的。但是沒必要這么緊巴巴的花這么多力氣把10個數硬塞到20bit，可以relax，也就是利用多余的12bit，我們不是每個數編碼2bit,允許編碼3比特也可以的，所以，我們把ACGT的ascii碼對7取與，則得到四個不同的數，分別表示這四個數。這樣做，就避免了if-else丑陋繁瑣的寫法，用一個相與就解決問題！再次讓我看到數學成全了代碼之美！
class Solution {public: vector<string> findRepeatedDnaSequences(string s) { // vector<string> res; if(s.size()<10) return res; //unordered_set<string> ss;//bug unordered_map<string,int> mm; for(int i=0;i<s.size()-9;i++){ string cur=s.substr(i,10); if(mm.count(cur)){ if(mm[cur]==1){ res.push_back(cur); mm[cur]=2; } }else mm[cur]=1; } return res; }};//優化：把10個字符打包裝入一個int內，查表快速，大幅提速！class Solution {public: vector<string> findRepeatedDnaSequences(string s) { // vector<string> res; if(s.size()<10) return res; unordered_map<int,int> mm; int encode=0; for(int i=0;i<s.size();i++){ encode=encode<<3|s[i]&7; encode=encode&0x3FFFFFFF; if(++mm[encode]==2) res.push_back(s.substr(i-9,10)); } return res; }};新聞熱點
疑難解答
