描述

题目描述

我们将繁琐的题意化简，其实本质上就是给了我们一个字符串里面只会含有，CGAT这四种字符，然后在给我们一个n 代表我们要寻找的子串的长度，我们要找到第一个CG比例最多的子串，然后输出这个子串

样例解释

ACGT
2

首先给了我们这么一个字符串 ACGT，然后要我们找到一个长度为 2 的子串，然后找到CG比例最高的，我们把这个问题化简一下 既然我们的长度固定，其实我们的比例就是 $\frac{CG\mathrm{数}\mathrm{量}}{\mathrm{总}\mathrm{体}\mathrm{长}\mathrm{度}}\backslash frac\{CG数量\}\{总体长度\}$，但是我们的长度已经是固定了，所以我们只是需要找到第一个 长度为 n 的CG数量最多的子串即可 那么我们这个ACGT子串为2的字符串有这么几种情况，AC，CG，GT，然后我们发现，AC有一个C，CG有一个C一个G，GT有一个G，所以我们最后输出为

CG

第二组输入

AACTGTGCACGACCTGA
5

其实我们长度为 5 的子串一共有这些种情况

AACTG
ACTGT
CTGTG
TGTGC
GTGCA
TGCAC
GCACG
CACGA
ACGAC
CGACC
GACCT
ACCTG
CCTGA

然后我们在这些子串里面判断，我们可以发现GCACG是CG的含量最多的，并且也是第一个出现的子串 所以我们最后的答案输出就是

GCACG

知识点： 尺取法（双指针） 难度： 两星

解题思路

解法一：暴力求解

思路分析：

首先给定了我们一个字符串，那我们只要分别从第一位开始，每次穷举出来长度为n的一个字符子串，然后我们在这个子串里面寻找我们所需要的CG的数量有多少，然后每次比较的时候，我们只需要判断，我们这次新产生的一个子串是否比我们之前一开始得到的那个答案是否CG的数量更多，如果更多的话，我们就是可以对我们最后的答案进行一个更新，然后我们就是穷举完所有的情况之后我们就是可以得到最后的答案了

时空复杂度分析

空间上，我们很容易看出来其实就是 O(n) 的，因为我们只有一开始的一个字符串，然后我们再开了一个新的字符串用于存储最后的那个的答案的字符串，复杂度中我们一般来讲是不会带常数的，所以我们空间复杂度是 O(n) 的。但是这种算法我们的时间复杂度，是O($n\ast mn\; *\; m$)的，这里的n代表的是我们一开始输入的字符串的长度，然后我们的m是我们要截取的子串的一个长度，我们可以发现这么一个问题，我们要对我们n的每一个位置都要向后枚举m位，那么我们就很容易算出来，我们的这个时间复杂度是 O($n\ast mn\; *\; m$) 的

C++代码实现

#include <bits/stdc++.h>
using namespace std;

void solve() {
    string s;
    cin >> s; // 输入我们的字符串
    int n, ans = -1; // 把我们最大值置为-1，这样可以保证后续答案可以正常更新
    cin >> n; // 这个n就是我们要截取的一个子串的长度
    string res = ""; // 这个是我们最后的一个答案字符串
    for (int i = 0; i < s.size(); i++) {
        int cnt = 0; // 这个是判断每一次的截取出来的子串有多少个CG
        string tmp = ""; // 这个是我们每一次截取出来的子串
        for (int j = i; j < s.size() && j < i + n; j++) { // 这个是截取子串的操作，要保证子串也要在我们的子串范围内
            tmp += s[j]; // 每次把原字符串的一位加到我们的子串之中
            if (s[j] == 'G' || s[j] == 'C') cnt++; // 这个记录这个子串有多少个CG
        }
        if (cnt > ans) res = tmp, ans = cnt; // 如果当前的子串中的CG的数量要是比我们的之前记录的大，我们更新答案字符串和最大的CG数量
    }
    cout << res << '\n'; // 输出我们最后的答案字符串
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}

解法二：尺取法（双指针）

思路分析

我们可以想一下，基于我们的暴力的做法，我们有没有一些操作其实是可以避免的，比如我们每次变换子串的时候，我们其实发现我们当前的子串和我们下一次的子串有什么相同点和什么不同点呢？ 我们不难发现其实，我们当前的这个子串和我们的下一个的子串唯一的不同其实就是在于子串的第一个元素和最后的一个元素上，那我们可不可以想一个办法，避免掉中间的那些重复没有必要的一个操作呢，每次我们都是只看第一个和最后一个，这个就好像是一把尺子，每次我们都是量取一段区间内的东西，那么我们每次移动的时候其实变化的就是第一个和最后一个，那我们就想到了，我们需要一种数据结构，它要满足什么条件呢？首先它要可以把最前面的元素删去，可以在他的后面插入新的元素，这里先进先出原则我们自然而然的想到了用队列来实现这个操作，这里队列我们可以使用STL里的，也可以自己手写一个简单的数组模拟的队列

时空复杂度分析

首先我们的空间复杂度，并为开辟什么新的空间，我们只是开辟了一个队列来存储我们的子串的下标，而且子串最长的长度也就是我们原字符串的一个长度，也就是说，空间最大也就是 O($2\ast n2\; *\; n$) 然后我们的复杂度不带常数，也就是空间复杂度就是 O(n)的 时间复杂度，因为我们其实只有一层的 for 循环，我们把双层for暴力的一些中间部分去掉了，我们没有往回走的一个操作，我们可以保证我们的for，是从头一直走到尾的，也就是说我们的时间复杂度，其实就是我们原字符串的一个长度，综上所述，我们可以得到，我们的时间复杂度是 O(n)的

图解算法

C++代码实现

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
#define int long long
#define endl '\n'

void solve() {
    string s; // 原字符串 
    cin >> s;
    int n, pos = 0, res = -1, tmp = 0;
    // n为要求取的子串的长度，pos为我们需要的子串的开头的位置
    // res是我们最后的答案, tmp是我们每次队列里面的子串的一个CG数量
    cin >> n;
    queue<int> q; 
    // 这个是用来存储我们的子串的，这里我使用了STl里的队列，其实这里可以手写队列
    // 这里注意一下，我们的队列里面存储的是我们的字符的下标
    for (int i = 0; i < s.size(); i++) {
        if (q.size() == n) { // 如果我们的队列里面已经有了n个下标了
            if (tmp > res) { // 如果我们现在队列里面的CG含量大于我们的之前的答案
                pos = q.front(); // 我们把这个子串的第一个下标存储下来
                res = tmp; // 然后更新我们的CG的最大值
            }
            if (s[q.front()] == 'C' || s[q.front()] == 'G') tmp--; // 如果我们要弹出的队首是CG之中的一个，我们要把这个子串的CG含量减去一个
            q.pop(); // 弹出队首的元素
        }
        if (s[i] == 'C' || s[i] == 'G') tmp++; // 如果当前的位置的队首元素是C或G那么我们这次的子串的CG含量要+1
        q.push(i); // 把当前的下标push到这个队列里面
    }
    for (int i = 0; i < n; i++) cout << s[pos + i]; // 从我们最大且第一个子串的下标开始遍历输出
    cout << "\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}