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. 貌似見(jiàn)過(guò)。找重復(fù)，一般少不了hash。連續(xù)十個(gè)字母用hash即可，然后每次往右邊移動(dòng)，移動(dòng)一次就從左邊刪一個(gè)，保證隨時(shí)都是10個(gè)數(shù)，然后查表看是否在hash里。 2. 剛開(kāi)始確實(shí)想到用unordered_map，但是寫(xiě)的時(shí)候，發(fā)現(xiàn)沒(méi)必要就改用unordered_set，只需要查詢之前是否保存這個(gè)string,如果有，就push_back進(jìn)入res。高高興興寫(xiě)完，發(fā)現(xiàn)思考的不細(xì)致，如果一個(gè)string出現(xiàn)多次，那么第2次、第3次…第n次出現(xiàn)時(shí)都會(huì)發(fā)現(xiàn)之前出現(xiàn)過(guò)，那么就會(huì)重復(fù)把這個(gè)string輸出到結(jié)果里，顯然這不是我們要得答案。怎么辦？必須使用unordered_map對(duì)出現(xiàn)次數(shù)計(jì)數(shù)就可以解決！ 3. 思維的盲點(diǎn)是，沒(méi)有把整個(gè)第一次遇到，第二次遇到，甚至第n次遇到相同string的情況在腦海里面情景再現(xiàn)，而是急忙開(kāi)始寫(xiě)了！下次寫(xiě)的時(shí)候，尤其是這種簡(jiǎn)單的情況，需要把整個(gè)情況都先dry run一遍再動(dòng)筆，其實(shí)更節(jié)約時(shí)間！ 4. 說(shuō)說(shuō)如何優(yōu)化。用到簡(jiǎn)單的編碼，以前學(xué)通信真是沒(méi)白學(xué)。首先，由于給的字符不是任意的，就只有4個(gè)不同的值，也就是說(shuō)可以編碼成兩比特，10個(gè)值最多20個(gè)比特就可以表示了，因此，完全你可以把10個(gè)字符打包塞進(jìn)一個(gè)int內(nèi)，然后查hash就用int，省很多時(shí)間和空間！ 5. 這里應(yīng)用了個(gè)小技巧，剛才說(shuō)10個(gè)說(shuō)壓縮成20bit就夠了，但是int可以裝32bit，那么還剩12bit空間。這個(gè)小技巧就是利用這個(gè)12bit空間。壓縮成20bit的話，就要每次手工用if-else把ACGT轉(zhuǎn)換成0,1,2,3，這樣做當(dāng)然是可以的。但是沒(méi)必要這么緊巴巴的花這么多力氣把10個(gè)數(shù)硬塞到20bit，可以relax，也就是利用多余的12bit，我們不是每個(gè)數(shù)編碼2bit,允許編碼3比特也可以的，所以，我們把ACGT的ascii碼對(duì)7取與，則得到四個(gè)不同的數(shù)，分別表示這四個(gè)數(shù)。這樣做，就避免了if-else丑陋繁瑣的寫(xiě)法，用一個(gè)相與就解決問(wèn)題！再次讓我看到數(shù)學(xué)成全了代碼之美！