DNA序列

#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;
        }
    }
}

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;
            }
        }
        
    }
}

#-*-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

不需要讨论实际的序列，只要比较序列的个数就好了。从长度为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;     }
}

	

#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();
    }
}

//利用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;
}

	

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))

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)

    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;
    }

 #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列举...

#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;
}

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()))

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.......