题解 | #DNA序列#

1 单调队列

#include <iostream>
#include <string>
#include <deque>
using namespace std;

class MyQue {
public:
    MyQue(deque<char> q, int gc) : m_que(q), m_gc(gc) {};

    void push(char c) {
        if (c == 'A' || c == 'T') m_que.push_back(c);
        else {
            while (!m_que.empty() && (m_que.back() == 'A' || m_que.back() == 'T')) {
                m_que.pop_back();
            }
            m_que.push_back(c);
            ++m_gc;
        }
    }

    void pop(char c) {
        if (!m_que.empty() && c == m_que.front()) {
            m_que.pop_front();
            if (c == 'G' || c == 'C') --m_gc;
        }
    }

    float gc() {
        return m_gc;
    }

private:
    deque<char> m_que;
    int m_gc;
};

int main() {
    string str;
    int n;
    cin >> str >> n;

    if (n > str.size()) {
        cout << str << endl;
    }
    else {
        deque<char> q;
        MyQue que(q, 0);
        for (int i = 0; i < n; ++i) {
          que.push(str[i]);
        }

        string result = str.substr(0, n);
        int gcNum = que.gc();

        for (int i = n; i < str.size(); ++i) {
            que.pop(str[i - n]);
            que.push(str[i]);
            if (que.gc() > gcNum) {
                result = str.substr(i - n + 1, n);
                gcNum = que.gc();
            }
        }

        cout << result << endl;
    }
    
}

2 双指针

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str;
    int n;
    cin >> str >> n;

    if (n > str.size()) {
        cout << str << endl;
    }
    else {
        string result = str.substr(0, n);
        int gc = 0;
        for (int i = 0; i < n; ++i) {
            if (str[i] == 'C' || str[i] == 'G') {
                ++gc;
            }
        }

        int gcMax = gc;
        for (int e = n; e < str.size(); ++e) {
            int b = e - n;
            if (str[b] == 'C' || str[b] == 'G') {
                --gc;
            }
            if (str[e] == 'C' || str[e] == 'G') {
                ++gc;
            }
            if (gc > gcMax) {
                result = str.substr(b + 1, n);
                gcMax = gc;
            }
        }
        cout << result << endl;
    }
}

3 暴力解法

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string str;
    int n;
    cin >> str >>n;

    if (n > str.size()) cout << str << endl;
    else {
        string result = str.substr(0, n);
        int gcMax = 0;
        for (int i = 0; i <= str.size() - n; ++i) {
            int gc = count_if(str.begin() + i, str.begin() + i + n, [](char c) {return (c == 'C' || c == 'G');});
            if (gc > gcMax) {
                gcMax = gc;
                result = str.substr(i, n);
            }
        }
        cout << result << endl;
    }
}