固定长度窗口问题:题目给定子串长度为固定的 k,在所有长度为 k 的子串中寻找 GC-Ratio 最高者。由于窗口长度一致,比较比例等价于比较窗口内 G/C 的计数。
算法选择:使用滑动窗口。
[0, k-1] 内 G 和 C 的个数 cnt。G/C 则 cnt--,若新进入的是 G/C 则 cnt++。cnt 及其起始下标;若出现更大 cnt 则更新。若相等则保持原位置以满足“多个时输出第一个”的要求。核心实现要点:
一个 DNA 序列由 A/C/G/T 四个字母的排列组合组成。G 和 C 的比例(定义为 GC−Ratio )是序列中 G 和 C 两个字母的总的出现次数除以总的字母数目(也就是序列长度)。在基因工程中,这个比例非常重要。因为高的 GC−Ratio 可能是基因的起始点。
给定一个很长的 DNA 序列,以及要求的最小子序列长度,研究人员经常会需要在其中找出 GC−Ratio 最高的子序列。
DNA 序列为 ACGT 的子串有:ACG,CG,CGT 等等,但是没有 AGT,CT 等等
数据范围:字符串长度满足 1≤n≤1000,输入的字符串只包含 A/C/G/T 字母
输入一个 string 型基因序列,和 int 型子串的长度
找出 GC 比例最高的子串,如果有多个输出第一个的子串
输入
AACTGTGCACGACCTGA
5
输出
GCACG