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; }};新闻热点
疑难解答
