注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex187 Repeated DNA Sequences  

2015-05-23 22:30:17|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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"].

开始用了最暴力的方法,给每个10大小的子串建一个hash,如果能找到的。很显然,超时了~~~代码如下

class Solution {
public:
vector<string>result;
map<string, int> myMap;
map<unsigned int, int> textMap;
vector<string> findRepeatedDnaSequences(string s) {
traverse1(s);
return result;
}
void traverse(string s)
{
//这个方法太暴力,超时了
//貌似是因为内存不够的原因
//网上就有牛逼闪闪的变换方法
//那个map的key里面不存string,直接存一个数字,这样就很节省了
int count = 10;
int len;
len = s.length();
int i,index;
string temp;
for (i = 0; i < len - count; i++)
{
temp = s.substr(i,count);
index = s.rfind(temp);
if (index > i)
{
//说明有重复
if (!myMap.count(temp))
{
myMap.insert(pair<string,int>(temp,i));
result.push_back(temp);
}
}
}

}
};


查看别人的思路,其实也是这样,只不过,人家没有用string作为key,而是用了小技巧,刚好10大小的子串可以用一个unsigned int型表示出来,就用int map int这样应该就很节省时间和内存了。代码如下

class Solution {
public:
vector<string>result;
map<string, int> myMap;
map<unsigned int, int> textMap;
vector<string> findRepeatedDnaSequences(string s) {
traverse1(s);
return result;
}
unsigned int ten2Num(string str)
{
//A C G T 0 1 2 3
int i = 0;
int count = 10;
unsigned int num = 0;
unsigned int a;
for (i = 0; i < count; i++)
{
switch (str[i])
{
case 'A': a = 0;
break;
case 'C': a = 1;
break;
case 'G': a = 2;
break;
case 'T': a = 3;
break;
default:
break;
}
num *= 10;
num += a;
}

return num;
}
void traverse1(string s)
{
//关键是如何把10个字符串压缩成一个整数呢???
//同样的思想,我把key变成unsigned int来存,可是时间上还是太慢了~~
//难道真的得用位操作才行????
int count = 10;
int len;
len = s.length();
int i, index, exist;
string temp;
unsigned int mark = 0;
for (i = 0; i < len - count+1; i++)
{
temp = s.substr(i, count);
mark = ten2Num(temp);
//没有这个东西
if (!textMap.count(mark))
{
textMap.insert(pair<unsigned int, int>(mark, i));
textMap[mark]=1;
}
else
{
if(textMap[mark]==1)
result.push_back(temp);
textMap[mark]++;

}
}
}
unsigned int line(char s)
{
unsigned int a = 0;
switch (s)
{
case 'A': a = 0;
break;
case 'C': a = 1;
break;
case 'G': a = 2;
break;
case 'T': a = 3;
break;
default:
break;
}
}
void traverse2(string s)
{
//关键是如何把10个字符串压缩成一个整数呢???
int count = 10;
int len;
len = s.length();
int i, index, exist;
string temp;
unsigned int mark = 0, preMark = 0;;
for (i = 0; i < len - count + 1; i++)
{
temp = s.substr(i, count);
//index = s.rfind(temp);
if (i == 0)
{
mark = ten2Num(temp);
}
else
{
unsigned int a = 0, b = 0;;
a = line(s[i-1]);
b = line(s[i+9]);
mark = 10 * (preMark - a*pow(10, 9)) + b;
}

//没有这个东西
if (!textMap.count(mark))
{
textMap.insert(pair<unsigned int, int>(mark, i));
textMap[mark] = 1;
}
else
{
if (textMap[mark] == 1)
result.push_back(temp);
textMap[mark]++;

}
preMark = mark;
}
}
};

然后每次string直接转为int,其实前一个串和后一个是有关系的,所以不用每次重新计算,可以递推。但是oj上大集合时间还是太长了~~网上有个牛逼的算法,全部用位操作,我表示我想不到。大意就是
A: 0100 0001  C: 0100 0011  G: 0100 0111  T: 0101 0100

可以看到他们字符之间用三位就能区别,每次取后三位,拼接,刚好10*3,普通计算机中32整数就够用了。代码如下

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




参考
http://www.cnblogs.com/grandyang/p/4284205.html
http://blog.csdn.net/u011108221/article/details/43581889
  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017