重复的DNA序列

[编程题]重复的DNA序列

热度指数：2447 时间限制：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"]

算法知识视频讲解

Java

牛客250092340号

这个网站还有继续维护吗？这题费解

发表于 2022-01-07 15:25:54 回复(0)

Java

pein531

这个题我真的无语了，题目里说了长度大于等于10，结果只有找出长度等于10的才能AC。滑动长度为10的窗口遍历DNA序列，并用哈希表记录加入过的片段。如果遍历到某个片段时发现这个片段已经存在于哈希表中，说明这个片段出现次数超过一次，是目标片段，将其加入到结果集中（注意对结果集也要去重，并要保持在原始DNA序列中的相对出现次序）。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param DNA string字符串 1
     * @return string字符串一维数组
     */
    public String[] repeatedDNA (String DNA) {
        // write code here
        if(DNA.length() < 10) return new String[0];
        HashSet<String> set = new HashSet<>();
        ArrayList<String> res = new ArrayList<>();
        for(int start = 0; start < DNA.length() - 9; start++){
            String seq = DNA.substring(start, start + 10);
            if(set.contains(seq)){
                // set中加过，表示这个DN***段出现超过1次，添加进结果集
                if(!res.contains(seq)){
                    res.add(seq);
                }
            }else{
                set.add(seq);
            }
        }
        return res.toArray(new String[res.size()]);
    }
}

编辑于 2021-12-11 15:28:33 回复(1)