重复的DNA序列

[编程题]重复的DNA序列

热度指数：2430 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

所有的 DNA 序列都是由 'A' , ‘C’ , 'G' , 'T' 字符串组成的，例如 'ACTGGGC' 。

请你实现一个函数找出所有的目标子串，目标子串的定义是，长度等于 10 ，且在 DNA 序列中出现次数超过 1 次的子串（允许两个子串有重合的部分，如下面的示例2所示）。

（注：返回的所有目标子串的顺序必须与原DNA序列的顺序一致，如下面的示例1所示）

数据范围：DNA序列长度满足 $1 \le n \le 10^5 \$ ，保证序列中只出现 'A' , 'C' , 'G' , 'T'。

示例1

输入

"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出

["AAAAACCCCC","CCCCCAAAAA"]

说明

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

示例2

输入

"AAAAAAAAAAA"

输出

["AAAAAAAAAA"]

算法知识视频讲解

查看答案及解析

小谷围做题家

package main
import "sort"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param DNA string字符串 1
 * @return string字符串一维数组
*/
func repeatedDNA( DNA string ) []string {
    cnt:=map[string]int{}
    loc:=map[string]int{}
    ans:=[]string{}
    for i:=0;i+10<=len(DNA);i++{
        key:=DNA[i:i+10]
        if cnt[key]==1{
            ans=append(ans,key)
        }
        cnt[key]++
        if _,ok:=loc[key];!ok{
            loc[key]=i
        }
    }
    sort.Slice(ans,func(i,j int)bool{
        return loc[ans[i]]<loc[ans[j]]
    })
    return ans
}

发表于 2023-03-10 21:27:34 回复(0)