所有的 DNA 序列都是由 'A' , ‘C’ , 'G' , 'T' 字符串组成的,例如 'ACTGGGC' 。
请你实现一个函数找出所有的目标子串,目标子串的定义是,长度等于 10 ,且在 DNA 序列中出现次数超过 1 次的子串(允许两个子串有重合的部分,如下面的示例2所示)。
(注:返回的所有目标子串的顺序必须与原DNA序列的顺序一致,如下面的示例1所示)
数据范围:DNA序列长度满足 ,保证序列中只出现 'A' , 'C' , 'G' , 'T'。
"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
["AAAAACCCCC","CCCCCAAAAA"]
"AAAAACCCCC"和"CCCCCAAAAA"长度等于 10 且在DNA序列中分别出现了 2 次。 不能返回["CCCCCAAAAA","AAAAACCCCC"],因为在原DNA序列中,"AAAAACCCCC"要比"CCCCCAAAAA"先出现。
"AAAAAAAAAAA"
["AAAAAAAAAA"]
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param DNA string字符串 1 * @return string字符串一维数组 * @return int* returnSize 返回数组行数 */ int str_num(char * p,int len){ int sum=0; for(int i=0;i<len;i++){ if(p[i]=='A'){ sum+=sum*4+0; } else if(p[i]=='G'){ sum+=sum*4+1; } else if(p[i]=='C'){ sum+=sum*4+2; } else{ sum+=sum*4+3; } } return sum;//将字符串转化为数字 } char** repeatedDNA(char* DNA, int* returnSize ) { // write code here int count=0; char **ans=(char **)malloc(sizeof(char *)*1000000); int *hash=(int *)calloc(1000000000,sizeof(int)); for(int i=0;i+9<strlen(DNA);i++){ char temp[11]={}; strncpy(temp, DNA+i, 10); int temp1=str_num(temp, 10); //if(hash[temp1]==0){ hash[temp1]+=1; if(hash[temp1]==1){ ans[count]=(char *)malloc(sizeof(int)*11); strcpy(ans[count],temp); count++; } } char **ans1=(char **)malloc(sizeof(char *)*1000000); int count1=0; for(int i=0;i<count;i++){ int temp1=str_num(ans[i], 10); if(hash[temp1]>1){ ans1[count1]=(char *)malloc(sizeof(int)*11); strcpy(ans1[count1],ans[i]); count1++; } } *returnSize=count1; return ans1; }