DNA序列

while True:
    try:
        str1=input()#记录字串
        n=int(input())#记录个数
        a=[]
        if len(str1) > n:#当n个数小于字符串长度时（可以移动框时）
            for i in range (len(str1)-n): #以步长为1移动框查找个数
                total=str1[i:i+n].count('G')+str1[i:i+n].count('C')
                a.append(total)#记录在list里
            index =a.index(max(a))#查找最大值index
            print(str1[index:(index+n)])#按长度打印
        elif len(str1) == n:#最后有个相等情况直接打印或者判断if ‘G’，‘C’ not in 返回空
            print(str1)
    except:
        break

while True:
    try:
        str = input()
        n = int(input())
        strings = []
        if n == len(str):
            print(str)
        else:
            for i in range(len(str) - n):
                    count = str[i:i+n].count('G') + str[i:i+n].count('C')
                    ratio = count / len(str[i:i+n])
                    if count > 0:
                        strings.append([str[i:i+n], ratio])
            ordered = sorted(strings, key= lambda x:x[1], reverse = True)
            print(ordered[0][0])
    except EOFError:
        break

给定一个很长的DNA序列，以及要求的最小子序列长度，不知道为什么，最近总是把问题做复杂，是我理解差了还是题目描述不严密呢？但始终觉得这句话的意思是子串长度不固定，给定一个最小长度要求而已，而实际是按固定考虑。

附python借助队列存储移动窗口内符合条件的下标，时间复杂度0（n）

while True:
    try:
        s = input().strip()
        k = int(input())
        queue = []
        for i in range(k):
            if s[i] in 'CG':
                queue.append(i)
        max_ratio = len(queue)
        res = s[:k]
        for i in range(k, len(s)):
            if s[i] in 'CG':
                queue.append(i)
            if queue[0] <= i-k:
                queue.pop(0)
            if len(queue) > max_ratio:
                max_ratio = len(queue)
                res = s[i-k+1:i+1]
        print(res)
    except:
        break

while True:
    try:
        string, num = input().strip(), int(input().strip())
        C_and_G_counts = []
        for i in range(0, len(string)-num+1):
            sub_str = string[i:i+num]
            C_and_G_counts.append(sub_str.count('C') + sub_str.count('G'))
        index = C_and_G_counts.index(max(C_and_G_counts))
        print(string[index:index+num])
    except:
        break
        

# 2020年11月14日10:21:15
# 寻找第一个GC比例最高的子串
def high_gc_substr(seq, num):
    ratio = []
    for i in range(len(seq) - num + 1):
        sub_seq = seq[i:i+num]
#       计算G、C字母个数之和
        cnt = sub_seq.count("G") + sub_seq.count("C")
#       计算GC比例
        ratio.append(cnt / len(seq))
#   返回第一个最大值索引
    idx = ratio.index(max(ratio))
    return seq[idx:idx+num]

while True:
    try:
        seq = input()
        num = int(input())
        print(high_gc_substr(seq, num))
    except:
        break
        

while True:
    try:
        a = input()
        b = int(input())
        char = a[:b]
        ra = char.count('C')+char.count('G')
        for i in range(1,len(a)-b+1):
            if a[i:i+b].count('C')+a[i:i+b].count('G') > ra:
                char = a[i:i+b]
                ra = char.count('C')+char.count('G')
        print(char)
    except:
        break

while True:
    try:
        s, n = input(), int(input())
        res = s[0:n]
        ratio = (res.count('C') + res.count('G')) / n
        for i in range(1, len(s) - n):
            sub_s = s[i:i+n]
            tmp = (sub_s.count('C') + sub_s.count('G')) / n
            if tmp > ratio:
                ratio = tmp
                res = sub_s
        print(res)
    except:
        break
        

while True:
    try:
        s, n = input(), int(input())
        c = 0
        out = ''
        for i in range(len(s)+1-n):
            count = s[i:i+n].count('G') + s[i:i+n].count('C')
            if count > c:
                c = count
                out = s[i:i+n]
        print(out)
    except:
        break

滑窗？ 复杂度O(N)

while True:
    try:
        string = str(raw_input())
        N = int(input())
        dp = [0]*(len(string))
        maxval = 0
        for i in range(len(string)):
            if string[i] == "G" or string[i] == "C":
                maxval += 1
            dp[i]  = maxval
        maxval = dp[N-1] #注意此时maxval的初始化，因为下面的loop从1开始
        p = 0
        CGcount = 0
        for i in range(1,len(string)-N+1):
            CGcount = dp[i+N-1]-dp[i-1]
            if CGcount > maxval:
                maxval = CGcount
                p = i
        print(string[p:p+N])
    except:
        break

while True:
    try:
        s,N= input(),eval(input())
        ls,a = [],len(s)
        for k in range(1,a+1):
            for i in range(a-k+1):
                if len(s[i:i+k]) == N:
                    ls.append(s[i:i+k])
        dic = {}
        for j in ls:
            num = 0
            for m in j:
                if m == 'G'&nbs***bsp;m == 'C':
                    num += 1
            dic[j] = num
        lst = []
        lst = list(dic.items())
        lst.sort(key = lambda x:x[1],reverse = True)
        print(lst[0][0])
    except:
        break

while 1:
    try:
        instr, strlen = input(), int(input())
        GCratio, flag, out = 0, 0, instr[0:strlen]
        for i in range(len(instr)-strlen):
            Substring = instr[i:i+strlen]
            if 'A' not in Substring and 'T' not in Substring:
                flag = 1
                print(Substring)
                break
            else:
                temp = Substring.count('G')+Substring.count('C')
                if temp>GCratio:
                    GCratio = temp
                    out = Substring
        if flag == 0:
            print(out)
    except:
        break