描述

题目描述

输入描述：

输入一个string型基因序列，和int型子串的长度

输出描述：

找出GC比例最高的子串,如果有多个则输出第一个的子串

示例

输入：
ACGT
2
输出：
CG
说明：
ACGT长度为2的子串有AC,CG,GT3个，其中AC和GT2个的GC-Ratio都为0.5，CG为1，故输出CG   

知识点：字符串

难度：⭐⭐⭐

题解

方法一：遍历统计

图解：

解题思路：

遍历str的所有长度为n的子串，过程中通过两个变量分别保存每次符合的子串的起始索引和CG个数

算法流程：

• 通过三个变量保存状态：maxSum记录GC字母个数，index保存结果子串的起始索引，gcSum记录每个子串中GC长度
• 从起点索引开始向后遍历n个字符
• 最后比较gcSum是否大于maxSum，符合则更新状态即可

Java 版本代码如下：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String str = scanner.next();
            int n = scanner.nextInt();
            System.out.println(Solution(str, n));
        }
    }
    
    public static String Solution(String str, int n) {
        // GC字母个数
        int maxSum = 0;
        // 结果子串的起始索引
        int index = 0;
        // 起始索引
        for(int i = 0; i <= str.length() - n; i++) {
            int gcSum = 0;
            // 从起点索引开始向后遍历n个字符
            for(int j = i; j < i + n; j++) {
                if(str.charAt(j) == 'C' || str.charAt(j) == 'G') {
                    gcSum++;
                }
            }
            if(gcSum > maxSum) {
                index = i;
                maxSum = gcSum;
                // 剪枝
                if(gcSum == n) {
                    return str.substring(index, index + n);
                }
            }
        }
        return str.substring(index, index + n);
    }
}

复杂度分析：

时间复杂度：$O(n)O(n)$, 需要遍历所有子串

空间复杂度：$O(1)O(1)$, 只用到了常数空间

方法二：滑动窗口

解题思路：

通过滑动窗口的机制实现子串中的统计处理

算法流程：

• 通过左右指针维护一个滑动窗口
• 每次右指针右移，并判断字符，更新状态变量
• 窗口缩小时，left左指针右移，同时更新count状态变量

Java 版本代码如下：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String str = scanner.next();
            int n = scanner.nextInt();
            System.out.println(Solution(str, n));
        }
    }
    
    public static String Solution(String str, int n) {
        int left = 0, right = 0;
        int start = 0, count = 0, max = 0;
        while(right < str.length()) {
            char c = str.charAt(right++);
            if(c == 'C' || c == 'G') {
                count++;
            }
            if(count > max){
                max = count;
                start = left;
                // 剪枝
                if(count == n) {
                    return str.substring(start, start + n);
                }
            }
            // 窗口缩小
            if(right - left >= n) {
                char d = str.charAt(left++);
                if(d == 'C' || d == 'G') {
                    count--;
                }
            }
        }
        return str.substring(start, start + n);
    }
}

复杂度分析：

时间复杂度：$O(n)O(n)$, 滑动窗口需要遍历所有字符

空间复杂度：$O(1)O(1)$, 只用到了常数空间