OD 算法题 B卷【DNA序列】

DNA序列

• 一个DNA序列由 A/C/G/T 四个字母的排列组合组成；
• G和C的比例是序列中G和C两个字母的总的出现次数除以序列中的总字母数；高的GC比例可能是基因的起始点；
• 给定一个DNA序列及限定的子串长度N，在该DNA序列中从左往右找出GC比例最高且长度为N的第一个子串；

输入描述：
第一行输出DNA序列；
第二行输入n的值，范围在【1， 1000】
输出描述:
找出GC比例最高的子串，如果有多个则输出第一个子串；

示例1
输入：
ACGT
2
输出：
CG
说明：ACGT长度为2的子串有AC/CG/GT，其中AC和GT 两个子串的GC比例都为0.5，CG的比例为1，故输出CG。

示例2
输入：
AACTGTGCACGACCTGA
5
输出：
GCACG

python实现

• 长度为n的滑动窗口；
• 统计每个窗口的GC比例，同时取最大ratio值，保存每个子串的ratio和子串内容到ratio_list；
• 最后按照max_ratio从ratio_list中找第一个最大GC比例的子串；

# 输入
dna = input().strip()
n = int(input().strip())# 存储每个窗口的GC比例
ratio_list = []# ACGT的字典，统计每个字符的个数
char_dict = {"A": 0,"C": 0,"G": 0,"T": 0
}def calc_gc_rate(char_dict):total = 0gc = 0for k, v in char_dict.items():if k in ["G", "C"]:gc += vtotal += vreturn gc / total# 初始化窗口的位置
pre = 0
cur = pre + n - 1
for idx in range(pre, pre + n):char_dict[dna[idx]] += 1# 计算GC比例
max_ratio = 0
cur_ratio = calc_gc_rate(char_dict)
max_ratio = max(max_ratio, cur_ratio)
ratio_list.append([cur_ratio, dna[pre:pre+n]])# 滑动窗口，并计算
while cur < len(dna) - 1:add_char = dna[cur + 1]del_char = dna[pre]char_dict[add_char] += 1char_dict[del_char] -= 1cur_ratio = calc_gc_rate(char_dict)max_ratio = max(max_ratio, cur_ratio)# 计算GC比例ratio_list.append([cur_ratio, dna[pre+1:pre+1+n]])# 移动指针 到已计算的窗口位置pre += 1cur += 1# 输出第一个最大GC比例的长度n的子串
for r, sub_str in ratio_list:if r == max_ratio:print(sub_str)break