首页 > 试题广场 >

DNA序列

[编程题]DNA序列
  • 热度指数：11238 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
牛牛又从生物科研工作者那里获得一个任务,这次牛牛需要帮助科研工作者从DNA序列s中找出最短没有出现在DNA序列s中的DNA片段的长度。
例如:s = AGGTCTA
序列中包含了所有长度为1的('A','C','G','T')片段,但是长度为2的没有全部包含,例如序列中不包含"AA",所以输出2。
注：长度为2的全部DNA片段有"AA"、"AC"、"AG"、"AT"、"CA"、"CC"、"CG"、"CT"、"GA"、"GC"、"GG"、"GT"、"TA"、"TC"、"TG"和"TT"，共16种。

输入描述:
输入包括一个字符串s,字符串长度length(1 ≤ length ≤ 2000),其中只包含'A','C','G','T'这四种字符。


输出描述:
输出一个正整数,即最短没有出现在DNA序列s中的DNA片段的长度。
示例1

输入

AGGTCTA

输出

2
示例2

输入

ACGT

输出

2
示例3

输入

AACAGATACCGCTGGTCTT

输出

3
算法知识视频讲解
添加回答
Java
海通和农发行的大孝子头像 海通和农发行的大孝子
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s=in.nextLine();
            Boolean findresult=false;
            HashMap<Integer,HashSet<String>> map=fullsort();
            //System.out.print(map);
            for(Integer i :map.keySet()){
                if(findresult==true) break;
                HashSet<String> set= map.get(i);
                for(String element: set){
                    if(!s.contains(element)){
                        System.out.println(i);
                        findresult=true;
                        break;
                    }
                }
            }
        }
    }
    public static HashMap<Integer,HashSet<String>> fullsort(){
        char[] s=new char[]{'A','C','G','T'};
        HashMap<Integer,HashSet<String>> map=new HashMap<>();
        //case 1
        for(int i=0;i<s.length;i++){
            String element=String.valueOf(s[i]);
            //System.out.print(element);
            HashSet set=map.getOrDefault(1,new HashSet<String>());
            set.add(element);
            map.put(1,set);
        }
        //case 2
        for(int i=0;i<s.length;i++){
            for(int j=0;j<s.length;j++){
                StringBuffer element=new StringBuffer(String.valueOf(s[i]));
                element.append(s[j]);
                HashSet set=map.getOrDefault(2,new HashSet<String>());
                set.add(new String(element));
                map.put(2,set);
            }
        }

        //case 3;
        for(int i=0;i<s.length;i++){
            for(int j=0;j<s.length;j++){
                for(int m=0;m<s.length;m++){
                    StringBuffer element=new StringBuffer(String.valueOf(s[i]));
                    element.append(s[j]);
                    element.append(s[m]);
                    HashSet set=map.getOrDefault(3,new HashSet<String>());
                    set.add(new String(element));
                    map.put(3,set);
                }
            }
        }
        //case4
        for(int i=0;i<s.length;i++){
            for(int j=0;j<s.length;j++){
                for(int m=0;m<s.length;m++){
                    for(int n=0;n<s.length;n++){
                        StringBuffer element=new StringBuffer(String.valueOf(s[i]));
                        element.append(s[j]);
                        element.append(s[m]);
                        element.append(s[n]);
                        HashSet set=map.getOrDefault(4,new HashSet<String>());
                        set.add(new String(element));
                        map.put(4,set);
                    }
                }
            }
        }
        return map;
    }
}
第六组用例未通过，map打印出来是对的，有大佬知道为什么吗
发表于 2023-04-06 15:29:27 回复(0)
Java
成程晨头像 成程晨
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;
public class Main{
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            String s = in.next();
            System.out.println(helper(s));
        }
    }
    public static int helper(String s){
        Set<String> set = new HashSet<>();
        int i = 0,j = 1,pow = 4;
        while(j < s.length()){
            i = 0;
            while(i + j <= s.length()){
                set.add(s.substring(i,i + j));
                if(set.size() >= pow) break;
                i++;
            }
            if(set.size() < pow) break;
            set.clear();
            j++;
            pow *= 4;
        }
        return j;
    }
}

发表于 2019-01-16 11:45:56 回复(0)
提交观点

问题信息

字符串 穷举 爱奇艺 2018 Java工程师
来自：爱奇艺2018秋季校招...
上传者：小小
难度：
2条回答 10327浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号