题解 | DNA序列
DNA序列
https://www.nowcoder.com/practice/e8480ed7501640709354db1cc4ffd42a
#include <iostream>
using namespace std;
int main() {
string gene;
int length;
cin >> gene >> length;
int count_CG = 0;
int start = 0, end = length - 1;
for(int i = start; i <= end; ++i) {
if(gene[i] == 'C' || gene[i] == 'G') {
++count_CG;
}
}
int max_idx = start;
int max_CG = count_CG;
while(++end < gene.size()) {
if(gene[start] == 'C' || gene[start] == 'G') {
--count_CG;
}
if(gene[end] == 'C' || gene[end] == 'G') {
++count_CG;
}
++start;
if(max_CG < count_CG) {
max_CG = count_CG;
max_idx = start;
}
}
cout << gene.substr(max_idx, length) << endl;
return 0;
}
滑动窗口，时间复杂度为O(n)
美团一面2240人在聊
