首页 > 试题广场 >

重复的DNA序列

[编程题]重复的DNA序列
  • 热度指数:2433 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
所有的 DNA 序列都是由 'A' , ‘C’ , 'G' , 'T' 字符串组成的,例如 'ACTGGGC' 。
请你实现一个函数找出所有的目标子串,目标子串的定义是,长度等于 10 ,且在 DNA 序列中出现次数超过 1 次的子串(允许两个子串有重合的部分,如下面的示例2所示)。
(注:返回的所有目标子串的顺序必须与原DNA序列的顺序一致,如下面的示例1所示
数据范围:DNA序列长度满足 ,保证序列中只出现 'A' , 'C' , 'G' , 'T'。
示例1

输入

"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出

["AAAAACCCCC","CCCCCAAAAA"]

说明

"AAAAACCCCC"和"CCCCCAAAAA"长度等于 10 且在DNA序列中分别出现了 2 次。 
不能返回["CCCCCAAAAA","AAAAACCCCC"],因为在原DNA序列中,"AAAAACCCCC"要比"CCCCCAAAAA"先出现。  
示例2

输入

"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;

}

发表于 2023-01-12 21:49:39 回复(0)