目录
牛客_HJ63DNA序列_滑动窗口
题目解析
C++代码
Java代码
牛客_HJ63DNA序列_滑动窗口
孩子们的游戏(圆圈中最后剩下的数)_牛客题霸_牛客网
描述:
一个 DNA 序列由 A/C/G/T 四个字母的排列组合组成。 G 和 C 的比例(定义为 GC-Ratio )是序列中 G 和 C 两个字母的总的出现次数除以总的字母数目(也就是序列长度)。在基因工程中,这个比例非常重要。因为高的 GC-Ratio 可能是基因的起始点。
给定一个很长的 DNA 序列,以及限定的子串长度 N ,请帮助研究人员在给出的 DNA 序列中从左往右找出 GC-Ratio 最高且长度为 N 的第一个子串。
DNA序列为 ACGT 的子串有: ACG , CG , CGT 等等,但是没有 AGT , CT 等等
题目解析
用滑动窗口的思想,首先用一个长度为n的窗口覆盖字符串前n部分子串,统计这里的CG数量,并暂时作为最大值。然后窗口右移,如果左边出去的是CG那么窗口内的CG数量减少一个,如果右边进来的是CG那么窗口内的CG数量增加一个,每次滑动都统计窗口内的CG数量,与临时最大值比较,记录下最大窗口的起始下标。
窗口右端抵达字符串末尾时结束,根据下标用substr函数输出字符串含CG最高的子串。
C++代码
#include <climits>
#include <iostream>
using namespace std;int main()
{string str;int n = 0;cin >> str >> n;int sz = str.size();int cnt = 0; // 统计C和G数量int begin = 0, cur = 0, maxCnt = INT_MIN;while(cur < sz - n){cnt = 0;for(int i = cur; i < cur + n; ++i){if(str[i] == 'C' || str[i] == 'G')++cnt;}if(cnt > maxCnt){begin = cur;maxCnt = cnt;}++cur;}string res(str.begin() + begin, str.begin() + begin + n);cout << res << endl;return 0;
}
Java代码
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);char[] s = in.next().toCharArray();int x = in.nextInt();int begin = 0; // 标记结果的起始位置int maxCount = 0; // 统计以前窗⼝内 C + G 的最⼤值int left = 0, right = 0, n = s.length;int count = 0; // 统计窗⼝内 C + G while(right < n){if(s[right] == 'C' || s[right] == 'G') count++;while(right - left + 1 > x){if(s[left] == 'C' || s[left] == 'G') count--;left++;}if(right - left + 1 == x){if(count > maxCount){begin = left;maxCount = count;}}right++;}for(int i = begin; i < begin + x; i++){System.out.print(s[i]);}}
}