题解 | #DNA序列#

DNA序列

https://www.nowcoder.com/practice/e8480ed7501640709354db1cc4ffd42a

def GC(n,s):
    gc = 0
    #pre是记录长度为n的子串的起始下标,初始为0
    pre = 0
    #算出第一个长度为n的字串里的gc值,作为初始滑动窗口
    for i in range(n):
        if s[i] == 'G' or s[i] == 'C':
            gc += 1
    max_gc = gc
    #如果gc值等于n代表整个字串都由gc组成,后续的gc值最多等于它,不会超过并且它也是第一个出现的,可以提前结束,直接返回,下面判断同理。
    if gc == n:
        return pre
    for i in range(n,len(s)):
        if s[i] == 'G' or s[i] == 'C':
            gc += 1
        if s[i-n] == 'G' or s[i-n] == 'C':
            gc -= 1
        if gc == n:
            return i-n +1
        if gc > max_gc:
            max_gc = gc
            pre = i-n+1
    return pre
s = input()
n = int(input())
pre = GC(n,s)
print(s[pre:pre+n])

原始一点点的解法 文章被收录于专栏

尽量不借助面向对象的思想,自己去实习具体过程

全部评论
时间复杂度为O(n),并且可以提前结束循环。空间复杂度O(1)
点赞 回复 分享
发布于 2023-07-03 22:21 四川

相关推荐

05-30 12:03
山西大学 C++
offer来了我跪着...:不是骗子,等到测评那一步就知道为啥这么高工资了
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务