O(n)复杂度,一次遍历

DNA序列

http://www.nowcoder.com/questionTerminal/e8480ed7501640709354db1cc4ffd42a

#include<stdio.h>

int main(void){
    char cin[5000];
    while(scanf("%s", &cin) != EOF){
        int n;
        scanf("%d", &n);
        int num = 0, m = 0, pp = 0;
        for(int i=0; cin[i]!='\0'; i++){
            if(cin[i]=='G' || cin[i]=='C')
                num += 1;
            if(i>=n)
                if(cin[i-n]=='G' || cin[i-n]=='C')
                    num -= 1;
            if(num>m){
                pp = i - n + 1 > 0 ? i - n + 1 : 0;
                m = num;
            }
        }
        cin[pp+n] = '\0';
        printf("%s\n", &cin[pp]);
    }
}
全部评论

相关推荐

秋国🐮🐴:拿到你简历编号然后让你知道世间险恶
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务