题解 | #DNA序列#

滑动窗口问题
思路：
题目给定了固定长度范围内的问题，求字串的问题，可以使用滑动窗口来解决。

解：

• 计算出每个窗口中ATCG的分布情况，并记录当时窗口内的比例值。
• 最后求出最大比例，即可找到对应子串的位置。

#include <stdio.h>
#include <string.h>

//滑动窗口
static void windows_fun(char *str, int size, int N){
    int windowSize = N;
    int res = size - N;
    int index = 0;
    int n;
    int max = 0;
    int curLeft;
    int curRight;

    for (index = 0; index <= res; index++) {
        int num = 0;
        for (n = index; n < windowSize+index; n++) {
            if (str[n] == 'C' || str[n] == 'G') {
                num++;
            }
        }
        //如果最大的有多个，遇到最后相等的也不会刷新curindex的值，所以此处可以保证是第一个子串
        if (num > max) {
            max = num;
            curLeft = index;
            curRight = index+N;//记录当时窗口的最后一个元素
        }
    }
    for (index = curLeft; index < curRight; index++) {
        printf("%c", str[index]);
    }
    printf("\n");
}

int main() {
    char str[1002] = {0};
    scanf("%s",str);
    int size = strlen(str);
    int N;
    scanf("%d",&N);
    windows_fun(str, size, N);
    return 0;
}