重复的DNA序列

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param DNA string字符串 1
# @return string字符串一维数组
#
class Solution:
    def repeatedDNA(self , DNA: str) -> List[str]:
        # write code here
        m = {}

        res = []
        for i in range(len(DNA)-9):
            tmp_s = DNA[i:i+10]

            if tmp_s in m:
                m[tmp_s].append(i)
            else:
                m[tmp_s] = [i]

        for i in range(len(DNA)-9):
            tmp_s = DNA[i:i+10]

            if tmp_s in m:
                if m[tmp_s][0] == i and len(m[tmp_s]) > 1:
                    res.append(tmp_s)

        return res

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param DNA string字符串 1
     * @return string字符串一维数组
     */
    public String[] repeatedDNA (String DNA) {
        // write code here
        // emmm...解法直接写在标签里了，建议牛客还是提供一下隐藏标签功能吧
        // 这题其实第一眼想到的是kmp，但是kmp需要动态维护next数组，比较困难
        HashMap<String, Integer> map = new LinkedHashMap<>();
        // substring的时间效率其实很高，是o(1)。因为jdk8后，它完整复制原数组，仅仅改变起始和结束索引
        List<String> res = new ArrayList<>();
        for (int i = 0; i <= DNA.length() - 10; i++) {
            String temp = DNA.substring(i, i + 10);
            map.put(temp, map.getOrDefault(temp, 0) + 1);
            
        }
        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if(entry.getValue() >= 2) res.add(entry.getKey());
        }
        return res.stream().toArray(String[]::new);
    }
}

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
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @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;

}

    vector<string> repeatedDNA(string DNA) {
        // write code here
        //map中的存储顺序是按key的升序排列，而不是按insert顺序
        //因此采用vector<pair<string,int>>来按顺序存储子串出现次数，同时用map存储子串对应的vector索引
        map<string,int> mp;
        vector<pair<string,int>> vc;
        int idx=0;
        for(int i=0;i<=DNA.size()-10;i++)
        {
            string cur=DNA.substr(i,10);
            if(mp.find(cur)==mp.end())
            {
                mp[cur]=idx;
                idx++;
                pair<string,int> tmp(cur,1);
                vc.push_back(tmp);
            }
            else
            {
                vc[mp[cur]].second++;
            }
        }
        vector<string> rt;
        for(int i=0;i<vc.size();i++)
        {
            auto curpair=vc[i];
            if(curpair.second>1)
            {
                rt.push_back(curpair.first);
            }
        }
        return rt;
    }

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];
        Map<String,Integer>map=new LinkedHashMap<>();
         ArrayList<String> res = new ArrayList<>();
        for(int start = 0; start < DNA.length() - 9; start++){
            String seq = DNA.substring(start, start + 10);
            map.put(seq,map.getOrDefault(seq,0)+1);
           
        }
        for(String key:map.keySet()){
            if(map.get(key)!=1){
                res.add(key);
            }
           
        }
        return res.toArray(new String[res.size()]);
    
    }
}

class Solution:
    def repeatedDNA(self , DNA: str) -> List[str]:
        # write code here
        res = []
        d = {}
        for i in range(len(DNA)-9):
            sub = DNA[i:i+10]
            d[sub] = d.get(sub,0)+1
        for sub in d:
            if d[sub] > 1:
                res.append(sub)
        return res