首页 > 试题广场 >

DNA序列

[编程题]DNA序列
  • 热度指数:11180 时间限制: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
#include<iostream>
#include<string>
#include<set>
#include<math.h>
using namespace std;
int main(){
    string x;
    cin>>x;
    int i,j,n=x.length();
    for(i=1;i<=n;i++){
        set<string> s;
        for(j=0;j<=n-i;j++) s.insert(x.substr(j,i));
        if(s.size()<(int)pow(4,i)){
            printf("%d",i); return 0;
        }
    }
}
编辑于 2017-12-01 10:46:13 回复(3)
import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        String input = scan.nextLine();
        int i,j,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;
            }
        }
        
    }
}

发表于 2018-02-22 11:06:27 回复(14)
悟空你太狠了!和前面悟空大佬学的方法,在这里做一下详解。
首先了解set容器的用法(键唯一)。
每种长度n都会有2^n种可能。例如长度为1时就有(A,C,G,T)这四种。n=2,时就16种。
接下来,寻找输入串中,长度为n的子串有多少种,如果数量不足2^n个,则输出n即可。代码如下:
#include<iostream>
#include<algorithm>
#include<string>
#include<set>
using namespace std;

int main() {

    string str;
    cin >> str;
    int length = str.size();
    for (int i = 1; i<=length; i++) {
        set<string> arr;
        for (int j = 0; j<length - i; j++) {
            arr.insert(str.substr(j, i));
        }
        if ((int)arr.size()<pow(4, i)){
            cout << i << endl;
            system("pause");
            return 0;            
        }
    }
}

编辑于 2019-01-24 10:42:19 回复(6)
CCATATCTCTATAATTAAGAGTGCACTAGGCACTTCCTAACTTAACTTGGGGAACACCCGCAACACGGAAACCTAAAAGTGACCGTACACGCAATATCTACTCATGTGGGCAATTTTCGGACTTTTAGTACGATGCCGTCGCTCGATAAAGTCATCAGTCCCTTGAATAACTCCTGCACGATCAAGAGATTGCAGTGCAACCCAGACATCAACGAGGTGAGGATAAACTTGACGCGTCCGTCGTTAGTCTGTCAATATTCCGCATAGTATACTGCTGCGATGGGACTCGCGGAACGGGAGCCTATGATCAGCCATGAGCCCAGAACCTCACGACAGACGGGCCCACCGCGTTCGATGACGTGATCTAGTACAATCTCATTTAAAGAGATAGGTGTTTGGCGTATTCCTATTGAAGGCTTTGTAAGTACAAAGTCCTCAAAGGCTTTCGATTTACAGGTGAAGGTTTTATAGCAGGCGTAACACATCGACTGAACGGCTTTACCCTATCAGGAATGTTTTTCTTGACAGGATCGCGACAACATCCCAAACATCGCATCCCCCGCGAGCCGGATTAAATTTGGCCAAGACGACAGATTTCTAGGGACGCACCACGAAAAGCCCGCCGACTAGCTACTCGACGGTTCCCTTCTGCTTGCCGAATGGCTATAATTAAAAACTTGCGAAGGACCATATGTGAACTGCACGCGAACTCTTCGGGTTTACGGCTATGCCGTGTATACTGCCTACTCCCGGATCTTATTTACTCAGTGCCGATGGCGTGACACTTTGGGCGTGCAGTTCCTAGGATTGCTGAGGCTTGTGATTTTGGCGTCAAGAGAGTGGTGCGCACGCACAATCCAAACCCAAGCGTTAGCCTCTGAACAGATATGTTGTGCTCATTCTGACAAAGGAACAAGGGGTGGTTGGAGAAATACACGATGTCAACACCCAGTATTTGGGCCCTAAAACTCGCCTTAGTGTCTAGGCGAAAGGATAAGCACCGCTTTCGGTCCTGGAGATTCCCTCGTGTCGGCACGAGTCCCACTATACCAAAATGCTAACTACAAAAATAATCAATGTACGTCCGGACAGTTTTCATTCTGGGCAAGGATGTAAACTTTTGTAATCTGCACCATGTAAGGGGTTGGACTGTTCGGACGGAGCAATCTTAATCTCCGCTGATAAACAAACGGGCCTTTTGGATGCGTTTGTCAAGCTACCAAGGGGAAAACCTGCCTGGATATGAACCTATACACTGCGAGGTAGCCTAAAAGGAAGCTGGAGTAGGGGGGAAGTAGGTTCGTAACAACTTTTAGAGGCTTCAACTTAAGTTTCACAAAGTGGCTGTTTAGACGCGAAGCTTGGATGCAAAAATCTGCGCTCTTTGGTAAATAGTTGTAAATTGCTCCCAGGAACTGATAAGTCCATTCCCAGTGCGACTAACAGACGCTGTCGTCGCTTGAGCTCAGGAAAGTCGTCGGGGACCCACAGTACGATCAATAGCACTATCAAGACCATTGGTTGCCTCCAGTTCAGAGGGAGTTTATCGTCCCATGATGTCTTAAAAGCAATATTATAACCCAGGTGTTTAGTCTCGTAGTCCGAGCAATGGCTTCAATCAGGGATCGTTATTCCATAGAAGTACCTGTATGTTTGCGGGCGAGTTGGGGCGTTCTCGCATATAGAGGACGAGCGGCTCGTATGGTATACACGCAGTTAGAATCGGCTTCAAGACGTGGACTGAACACGACGACACGGAACAATCCAGCCGTTTCGGTACGAATCTACCGATCAGCGTGAATTACGACCGGCCCGAGCCATTTCCCATGATTGGATGTACATGCAGCATAATACGAACCCCCGTGTGGCCCCGACTGCCCCCAAAGGTCCCACACCATCCGGAGCCATAGCCAAGATTCCGCACCCCCTACGGTAGCAGCGGATCCAGTTAGGCCTGGGACGAGATGGCCAATAGGGGGTGAGCGGCGTTTGGTCTCCAG
以下是我用python写的两种思路,一种是打表的方法,感觉有些复杂了,另一种是考虑既然求最短连续串的话,求每个字母的最长连续长度,求个最小值即可,时间复杂度是线性级
但是以上这个测例始终过不了,但是很明显这段基因中A、C、G、T都有出现连续五个的子字符串,所以结果应该是6,但是测例给出结果是5。整道题始终只正确80%,有哪位大佬能够指点一下哈,
#-*-coding:utf-8-*- while True: try:
        refer=['A','C','G','T']
        s=raw_input()
        n=len(s)
        tmp=s[0]
        i=0  d={} if 'A' in s:
            d[1]=1  if 'C' in s:
            d[2]=1  if 'G' in s:
            d[3]=1  if 'T' in s:
            d[4]=1  while(i<n):
            res=0  t=refer.index(tmp)+1  while(i<n and s[i]==tmp):
                i+=1  res+=1  if i<n:
                tmp=s[i] if 4*(res-1)+t in d:continue  else:d[4*(res-1)+t]=1  q=len(d)
        ans=-1  for j in range(1,q+1): if j in d: continue  else:
                ans=j break  t=ans%4  g=ans/4  if(t>0):
            g+=1  print d except: break 


#-*-coding:utf-8-*- while True: try:
        s=raw_input()
        n=len(s)
        t=0  la=0  lc=0  lg=0  lt=0  for i in range(n): if(s[i]=='A'):
                t+=1  else:
                la=max(la,t)
                t=0  la = max(la, t)
        t = 0  for i in range(n): if(s[i]=='C'):
                t+=1  else:
                lc=max(lc,t)
                t=0  lc = max(lc, t)
        t=0  for i in range(n): if(s[i]=='G'):
                t+=1  else:
                lg=max(lg,t)
                t=0  lg = max(lg, t)
        t = 0  for i in range(n): if(s[i]=='T'):
                t+=1  else:
                lt=max(lt,t)
                t=0  lt = max(lt, t)
        t = 0  ans=min(la,lc,lg,lt)+1  print ans except: break



发表于 2017-12-13 12:12:16 回复(9)
不需要讨论实际的序列,只要比较序列的个数就好了。从长度为1到长度为n分别进行讨论,将长度
为i的子串加入到set容器中去,set容器会自动除去重复的元素,这样set容器的大小size()就
表示长度为i的种类数量了。长度为i的序列总共有4的i次方个(排列组合:每个位置都有四种
选择),然后将set容器的size()与4的i次方进行比较,如果小于4的i次方,那肯定存在不包含的
序列。
import java.util.*;
public class Main {     public static void main(String[] args) {         Scanner SC = new Scanner(System.in);         String str = SC.next();         System.out.println(fun(str));     }     static int fun(String str) {         for (int i = 1; i <= str.length(); i++) {             Set<String> rq = new TreeSet<>();             for (int j = 0; j < str.length() - i; j++) {                 rq.add(str.substring(j, j+i));             }             if (rq.size() < Math.pow(4, i)) {                 return i;             }         }         return 1;     }
}

发表于 2019-03-05 13:44:36 回复(0)
难道就我一个人读不懂题目么?
发表于 2019-03-22 16:29:37 回复(0)
#include<iostream>
#include<string>
#include<unordered_set>
#include<algorithm>
using namespace std;

int main(){
    string s;
    cin>>s;
    unordered_set<string> ss;//保存每次可能的值
    int k=0;
    while(1){
    for(int i=0;i<s.size()-k;i++){
        ss.insert(s.substr(i,k+1));//加入可能值
    }
    if(ss.size()<pow(4,k+1)){cout<<k+1;return 0;}//判断可能值数量是否满足4^n的条件
     k++;
     ss.clear();
    }
}

编辑于 2019-08-15 14:20:13 回复(0)
//利用set自动过滤相同元素的性质
#include<iostream>
#include<set>
#include<string>
#include<cmath>
using namespace std;
//start为起始位置,返回str[start]到str[start+length-1]之间的字符串
string SecString(int start, int length, string str){
    string m = "";
    int i = 0;
    while (i < length){
        m += str[start + i];
        i++;
    }
    return m;
}
int main(){
    string str;
    cin >> str;
    int m = str.size();
    set<string> s;
    int c = 0,rec=0;
    for (int i = 0; i < m; i++){
        c++;
        for (int j = 0; j < m-c+1; j++){
            s.insert(SecString(j, c, str));
        }
        //rec为最长片段不为c时s理论上应该有的元素个数
        rec += pow(4, c);
        //s.size()<rec即表示s的元素个数小于最长片段不为c时s理论上的元素个数
        //即最长片段为c
        if (s.size() < rec){
            cout << c << endl;
            return 0;
        }
    }
    return 0;
}
编辑于 2019-04-20 16:00:59 回复(0)
s = input()
count = 0
ls = ['A', 'C', 'G', 'T']
for k in ls:
    if k not in s:
        break
else:
    count += 1
    a = ls[:]
    active = True
    while active:
        b = []
        for i in range(len(a)):
            for j in range(len(ls)):
                s1 = a[i] + ls[j]
                b.append(s1)
        for v in b:
            if v not in s:
                active = False
                break
        else:
            a = b[:]
            count += 1
print(count + 1)
发表于 2019-04-16 11:54:33 回复(0)
import itertools  # itertools标准包,用于生成各种组合,非常方便

def dna(s):
    for i in range(1, len(s)+1):
        for j in itertools.product('ACGT', repeat = i):  # 生成i长度的所有可能组合,结果是tuple形式
            if ''.join(j) not in s:    # 将结果组合成字符串,并看s中是否存在串
                return i 
            
if __name__ == "__main__":
    s = input()
    print(dna(s))

发表于 2019-03-18 20:28:15 回复(0)
Python可以使用product直接列出组合,简直BUG

from itertools import product
s = input()
res = 0
while True:
    res += 1
    flag = 0
    for r in product('ACGT', repeat=res):
        r = ''.join(r)
        if r not in s:
            flag = 1
            break
    if flag:
        break
print(res)

发表于 2019-03-18 10:00:11 回复(0)
宽度优先遍历

    private static int solve(String s) {
        LinkedList<String> linkedList = new LinkedList<>();
        for (int i = 0; i < dns.length; i++) {
            String string = String.valueOf(dns[i]);
            if (s.contains(string)) {
                linkedList.add(String.valueOf(dns[i]));
            } else {
                return 1;
            }
        }
        return solve(s, linkedList);
    }

    private static int solve(String s, LinkedList<String> linkedList) {
        boolean find = false;
        int count = 0;
        while (!find) {
            String string = linkedList.poll();
            for (int i = 0; i < dns.length; i++) {
                String string2 = string + dns[i];
                if (!s.contains(string2)) {
                    find = true;
                    count = string2.length();
                    break;
                }
                linkedList.offer(string2);
            }
        }
        return count;
    }
编辑于 2019-03-21 18:39:18 回复(0)
 #include<bits/stdc++.h>
using namespace std;
struct Node
{
    vector<int>pos;
    int floor;
    Node(int x = 0)
    {
        floor = x;
    }
};


void bfs(string s)
{
    queue<Node*>myQue;
    Node* n1 = new Node(0);
    for(int i = 0,len = s.size(); i < len; i++)
    {
        n1->pos.push_back(i - 1);
    }
    myQue.push(n1);
    while(!myQue.empty())
    {
        Node* tmp = myQue.front();
        myQue.pop();
        Node *a1 = new Node(tmp->floor + 1);
        Node *c1 = new Node(tmp->floor + 1);
        Node *g1 = new Node(tmp->floor + 1);
        Node *t1 = new Node(tmp->floor + 1);
        // 表示上一个结束了
        for(int i = 0; i < (tmp->pos).size(); i++)
        {
            int t = tmp->pos[i] + 1;// 当前元素的下一位
            if(t >= s.size())
                continue;
            char c = s[t];
            if(c == 'A')
            {
                a1->pos.push_back(t);
            }else if(c == 'C')
            {
                c1->pos.push_back(t);
            }else if(c == 'G')
            {
                g1->pos.push_back(t);
            }else if(c == 'T')
            {
                t1->pos.push_back(t);
            }
        }
        if(a1->pos.empty() || c1->pos.empty() || g1->pos.empty() || t1->pos.empty())
        {
            cout << a1->floor << endl;
            return;
        }else
        {
            myQue.push(a1);
            myQue.push(c1);
            myQue.push(g1);
            myQue.push(t1);
        }
    }
    
}

int main()
{
    std::ios::sync_with_stdio(false);
    string s;
    cin >> s;
    bfs(s);
    
    return 0;
}







采用bfs的思维想法. 没想到用set列举...
















发表于 2019-02-24 14:01:05 回复(0)
#include <bits/stdc++.h>

using namespace std;

int main()
{     string s;     while(cin>>s){         int n = s.length();         for(int i=1;i<=n;i++){             set<string> S;             for(int j=0;j<=n-i;j++)                 S.insert(s.substr(j,i));             if(S.size()<pow(4,i)){                 cout<<i<<endl;                 break;             }         }     }     return 0;
}

发表于 2019-02-12 02:35:03 回复(0)
// 思路简单,拿走不谢
import java.util.Scanner;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            
            String str = sc.next();
            for(int i = 1; i < 1000; i++) {
                String strArr[] = getAllPermutation(i);
                boolean flag = true;
                for(int index = 0; index < strArr.length; index++) {
                    if(str.indexOf(strArr[index]) == -1) {
                        flag = false;
                        break;
                    }
                }
                if(!flag) {
                    System.out.println(i);
                    break;
                }
            }
        }  // end of while
    }  // end of main
    
    public static String[] getAllPermutation(int n) {
        int arr[] = new int[n + 1];  // n=2: [0,0,0]=>[0,3,3]=>[1,0,0]
        String strArr[] = new String[(int)Math.pow(4, n)];
        int index = 0;
        while(arr[0] == 0) {
            String curStr = "";
            for(int i = 1; i < n + 1; i++) {
                if(arr[i] == 0) curStr += "A";
                else if(arr[i] == 1) curStr += "C";
                else if(arr[i] == 2) curStr += "G";
                else if(arr[i] == 3) curStr += "T";
            }
            strArr[index] = curStr;
            index++;
            
            arr[n] = arr[n] + 1;
            for(int i = n; i >= 0; i--) {
                if(arr[i] == 4) {
                    arr[i] = 0;
                    arr[i - 1] += 1;
                }
            }
        }
        return strArr;
    }
    
    
}  // end of class



发表于 2019-01-20 11:26:13 回复(0)
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)

python解法

这道题目要理解清楚题意才行,不存在的最短DNA序列是什么?

例如,长度为2的序列包括:(AA, AG, AC, AT, CA, CC, CG, CT ……..),要全部判断一遍才可以。并不是判断(AA, CC, GG TT)就可以了。

所以,要一层一层的判断,长度为1的所有子序列,长度为2的所有子序列……长度为n的所有子序列。有点像二叉树的层序遍历。

def calc(string):
    arr = ['']
    for i in range(0, len(string) + 1):
        tmpArr = []   # 下一层要判断的子序列。
        for item in arr:
            for char in ['A', 'C', 'G', 'T']:
                if item + char not in string:
                    return i + 1
                tmpArr.append(item + char)
        arr = tmpArr


print(calc(input()))
发表于 2019-03-15 21:46:50 回复(2)
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)
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        ArrayList<String> list = new ArrayList<>();
        list.add("A");
        list.add("G");
        list.add("C");
        list.add("T");
        String s="123";
        for(int i=0;i<list.size();i++){
            s = list.get(i);
            if(!str.contains(s)){
                break;
            }
            list.add(s+"A");
            list.add(s+"G");
            list.add(s+"C");
            list.add(s+"T");
        }
        System.out.print(s.length());
    }
}
该题的解题思路,你可以最开始给集合list放入A C G T三个字符串,之后遍历集合,A+A A+C A+G A+T B+A B+C.......

发表于 2022-10-25 10:43:57 回复(0)
s = input()
n = 0
if len(s) < 4:
    print(1)
else:
    while True:
        result = []
        for i in range(len(s) - n):
            test = s[i : i + n + 1]
            result.append(test)
        if len(set(result)) < 4 ** (n + 1):
            print(n + 1)
            break
        else:
            n += 1

发表于 2022-06-23 20:12:39 回复(0)