题解 | #DNA序列#
DNA序列
http://www.nowcoder.com/practice/e8480ed7501640709354db1cc4ffd42a
统计长度为n的滑动窗口内的cg数量。当我们统计好第一个滑动窗口后,向后滑动一个位置时只需要查看离开滑动窗口的一个字符以及进入滑动窗口的一个字符即可确定cg的数量,无需再次遍历整个滑动窗口。
#include <iostream> using namespace std; int main() { string line; int substr_len; while(getline(cin, line)) { cin >> substr_len; getchar(); int result_index = 0; int i = 0; int cg_num = 0; for(i=0; i<substr_len; i++) { if (line[i] == 'C' || line[i] == 'G') { cg_num++; } } int tmp_cg_num = cg_num; for(i=1; i <= line.size() - substr_len; i++) { // 检查离开滑动窗口的字符 if (line[i-1] == 'C' || line[i - 1] == 'G') { tmp_cg_num--; } // 检查进入滑动窗口的字符 if (line[i + substr_len - 1] == 'C' || line[i + substr_len - 1] == 'G') { tmp_cg_num++; } // 如果大于最大的cg数量则更新结果 if (tmp_cg_num > cg_num) { cg_num = tmp_cg_num; result_index = i; } } cout << line.substr(result_index, substr_len) << endl; } }