首页 > 试题广场 >

DNA序列

[编程题]DNA序列
  • 热度指数：11347 时间限制：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

输出

2
算法知识视频讲解
添加回答
Python
稳扎稳打的🐖头像 稳扎稳打的🐖
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)
Python
华科平凡头像 华科平凡

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)
Python
hts1头像 hts1 
简单一些的思路，遍历一遍整个字符串，得到每个字符连续出现的次数的集合，例如a出现了[1,2,3,4],b出现了[1,2,4],c出现了[1,2,3,4,5],d出现了[1,2,3,4,5]
这四个集合里，都包含了1,2，但是没有包含3，所以最终应该返回3
a,b,c,d=[],[],[],[]
dna = str(input("输入dna："))

def forward(dna,i):
    x= dna[i]
    # print(i,x)
    while dna[i]==x :
        i=i+1
        if i==len(dna)-1:
            return i+1
    return i

def not_all_in(i,a,b,c,d):
    if (not i in a) or (not i in b) or (not i in c) or (not i in d):
        return True
    return False
i=0

while i<len(dna)-1:
    j = forward(dna,i)
    # print("现在在：",i,"j==",j)
    if dna[i]=="a":
        if 1 not in a:
            a.append(1)
        if j-i not in a:
            a.append(j-i)
        i = j
        # print("现在a:",a)
    elif dna[i]=="b":
        if 1 not in b:
            b.append(1)
        if j-i not in b:
            b.append(j-i)
        i = j
        # print("现在b:", b)
    elif dna[i] == "c":
        if 1 not in c:
            c.append(1)
        if j-i not in c:
            c.append(j-i)
        i = j
        # print("现在c:", c)
    else:
        if 1 not in d:
            d.append(1)
        if j-i not in d:
            d.append(j-i)
        i = j
        # print("现在d:", d)

print(a,b,c,d)

for i in range(1,len(dna)):
    if not_all_in(i,a,b,c,d):  print(i)

编辑于 2019-03-06 13:21:47 回复(0)
Python
兰偷荀令香头像 兰偷荀令香
借鉴大神的思路，在set集合存档子串比较数量
DNA_string = input().strip()
if len(DNA_string) == 1:
    print(1)
else:
    for i in range(1, len(DNA_string)):
        # exact_num = len(list(permutations(['A', 'C', 'G', 'T'], i)))
        exact_num = pow(4, i)
        total_sub_string = set()
        for j in range(len(DNA_string) - i + 1):
            total_sub_string.add(DNA_string[j: j + i])
        if exact_num != len(total_sub_string):
            print(i)
            break

发表于 2019-02-18 15:24:06 回复(0)
Python
嘿哈嘿头像 嘿哈嘿
s = raw_input()
base = ['A','C','G','T']
char_list = ['A','C','G','T']
sig = 0
while True:
    for string in char_list:
        if string not in s:
            sig = 1
            break
    if sig == 1:
        break
    n = len(char_list)
    for _ in range(n):
        str1 = char_list.pop(0)
        for j in range(4):
            char_list.append(str1 + base[j])
            
print(len(char_list[0]))

发表于 2019-02-15 17:33:51 回复(0)
Python
雾顭花头像 雾顭花
import sys
s = sys.stdin.readline().strip()
def solution(s):
    stack1 = []
    stack2 = []
    l_s = len(s)
    res = 1
    pos_possible = list(range(len(s)))
    stack1 = [pos_possible]
    while stack1:
        stack1, stack2 = stack2, stack1
        while stack2:
            pos_get = {}
            pos = stack2.pop()
            for p in pos:
                try:
                    pos_get.setdefault(s[p + 1], []).append(p + 1)
                except:
                    pass
            for key in ('A', 'C', 'G', 'T'):
                if key not in pos_get:
                    return res
                else:
                    stack1.append(pos_get[key])
        res += 1
    return res
print(solution(s))

核心思想BFS。
Python的测试示例有误，上述程序正确率80%, 被误判示例在下方，其中ATCC后只出现了A,C,G，所以答案应为5，测试示例给出的答案为6
GCTGAAAAACAAAAGAAACCAAACGAAAGCAAAGGAAATAAAATCAAATGAACACAACAGAACCCAACCGAACGCAACGGAACTAAACTCAACTGACAAGACACCACACGACAGCACAGGACATAACATCACATGACCAGACCCCACCCGACCGCACCGGACCTAACCTCACCTGAGAAGAGACGAGAGCAGAGGAGATAAGATCAGATGAGCCAAGCCCAGCCGAGCGAAGCGCAGCGGAGCTAAGCTCAGCTGCAAGGCAATACAATCCAATGCACGCCACGGCACTACACTCCACTGCCAGGCCATACCATCCCATGCCCCCGCCCGGCCCTACCCTCCCCTGCGACGCGAGGCGATACGATCCGATGCGCCGCGCGGCGCTACGCTCCGCTGGAAGGGAATAGAATCGAATGGACGGGACTAGACTCGACTGGCAGGGCATAGCATCGCATGGCCGGGCCTAGCCTCGCCTGGGAGGGGATAGGATCGGATGGGCGGGGCTAGGCTCGGCTGTAAAGTAACGTAAGGTAATATAATCTAATGTACAGTACCGTACGGTACTATACTCTACTGTCAAGTCACGTCAGGTCATATCATCTCATGTCCAGTCCCGTCCGGTCCTATCCTCTCCTGTGAAGTGACGTGAGGTGATATGATCTGATGTGCAGTGCCGTGCGGTGCTATGCTCTGCTGCTTAAATTAACTTACATTACCTTAGAGTAGATTAGCGTAGCTTCAATTCACTTCCATTCCCTTCGAGTCGATTCGCGTCGCTTGAATTGACTTGCATTGCCTTGGAGTGGATTGGCGTGGCTTTAAGTTAATTTACGTTACTTTCAGTTCATTTCCGTTCCTTTGAGTTGATTTGCGTTGCTGTTAGGGTAGGTTATAGTATATTATCGTATCTTATGGTATGTTCGGGTCGGTTCTAGTCTATTCTCGTCTCTTCTGGTCTGTGGGGGTGGTGTAGTGTCGTGTGTTGGGTTGTATTGTCTTGTGTGGGGAATACACTGCAGTCTCGTTTAGTTTCGTGCGACATGCTGTTTGGTTTTATTTTCTTTTGTTAATGGGCTATGCTGTCAAGCGGGGAACGAGCGCTGCAGACATTCGTCATTGAGCGGTTCAGTTCGTAACAAGTCTGATCCGCCTCTCAGGATTCGGCTTCCATTATGGCAACTTAAGATATCCAATGGGATATTAGATTAGTATTGCTGCCGGCGCTGTACTCTGCGGAAGACGACGCGTTGAGTATTGCCGGTCGATGACTACCGACGCACCATCATAAATTGAAGCGCCGTTCGCATCACAGTCGGCATAGGCTGGATGAAGAACTAACAGTGCATAAATGCTTCAACAGCCCGAATGTAGCCTTTAGTCGGGTGCACTGAACGTAGTTAGAAGCATGACTTTACAGGGAGATATGGACTGCATTGCTTGGACATGTGATCAGTGTATCGGCGATGGAATCTCAAGAAAGCCGGTCTGAAAAATTTTTTAGTCCAGAATCTTCACATAAACCGACCAACCTACGTCCCGTTTACCCTGCCTATGGGCCCGAGCAGCAGTCATTTTCGTTCACGCCACCTCTCACTCTTATCACTGGTAAAATCATGAGTGCACCTCTTGAGTGCCCCATGCTCGTTCGGTGGCCACGGGTAAAGTAAGACAACGTAGTAGTGAGTAAGTGATGGGAGCATCCAGCAGAGTGGTAAGATGAGCCAATATTATACTGACATATAACAACCAACAGATCCTGGTCGACCGCAGGCGCGAATATGACCCAGATGCTGGAATGGGTTCTGGGTGGGTCAGGAGGTTCACCCGGTGTAGACCCCTGCCGTTCCTACTGTCAATCTCAGCAGCGAACCGACGCATTTTCGGATAGACGCAAGTCGACTGGGGATCAATATTGCTGTTTGTTAGGTTGGTGATCCTACGACTCACTCTAGTTCAATGGGGGACATGGATCGATACCGATCTACGTGAGACTTTTCACT
编辑于 2019-01-17 04:56:23 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

DNA序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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