首页 > 试题广场 >

DNA序列

[编程题]DNA序列

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

牛牛又从生物科研工作者那里获得一个任务,这次牛牛需要帮助科研工作者从DNA序列s中找出最短没有出现在DNA序列s中的DNA片段的长度。
例如:s = AGGTCTA
序列中包含了所有长度为1的('A','C','G','T')片段,但是长度为2的没有全部包含,例如序列中不包含"AA",所以输出2。

输入描述:

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

输出描述:

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

示例1

输入

AGGTCTA

输出

算法知识视频讲解

Java

牛客499848474号

感谢@大傻1111的解法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        int i = 0;
        int j = 0;
        int n = input.length();
        for (i = 1; i <= n; i++) {
            HashSet<String> set = new HashSet<String>();
            for (j = 0; j <= n - i; j++)
                set.add(input.substring(j, j + i));
                if (set.size() < Math.pow(4, i)) {
                    System.out.println(i);
                    break;
                }
        }
    }
}

发表于 2024-11-06 20:41:38 回复(0)

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)