题解 | #DNA序列#

DNA序列

http://www.nowcoder.com/practice/e8480ed7501640709354db1cc4ffd42a

题目分析

题目给出我们一个由A/G/C/T四种字母组成的字符串，并且给出了一个目标子串的固定长度值

题目希望我们在给定长度下锁定一个子串中，输出从左到右数G和C出现的比率最高的第一个给定长度的的子串

方法一：暴力截取子串并计数

实现思路
- 我们直接用python切片的方式，遍历给出的字符串来获得一个个目标子串
- 然后对目标字串进行G和C的计数
- 如果G和C的数量占比高，则更新可能的输出结果
- 直到遍历结束为止，输出第一个G和C含量最高的子串


def solution(s, k):
    if k >= len(s):                                # 处理特殊情况
        print(s)
        return
    mx = 0
    res = ""
    for i in range(len(s)-k):                      # 遍历字符串，找到子串的起点
        sub = s[i:i+k]                             # 获得子串
        count = sub.count('C') + sub.count('G')    # 计算CG的含量
        if count > mx:                             # 根据CG含量更新最大值
            mx = count
            res = sub
    print(res)
    return

while True:
    try:
        s = input()
        k = int(input())
        solution(s, k)
    except:
        break

复杂度分析

时间复杂度： $O (k (n - k))$ ，其中n是给出字符串的长度，k是截取的子字符串长度。由于只遍历一次字符串，且遍历的起点只有n-k个，所以代价为 $O (n - k)$ ，但是对于每个子串都需要遍历一轮数出所有的G和C的数量，因此最终代价为 $O (k (n - k))$
空间复杂度： $O (k)$ ，每轮存储子串长度的字符串变量空间开销

方法二：滑动窗口优化计数

实现思路
- 在方法一的基础上，我们在字串的G和C含量统计上进行优化
- 我们通过控制窗口访问的元素来调整计数结果
- 如果左侧的元素退出窗口，右侧有新的元素进入窗口，判断是否是C或G来调整计数的结果
- 这样优化了内层对于子串的遍历开销

alt


def solution(s, k):
    if k >= len(s):                                # 处理特殊情况
        print(s)
        return
    sub = s[:k]
    cur = mx = sub.count('C') + sub.count('G')
    res = sub
    for i in range(1, len(s)-k):                          # 遍历字符串，找到子串的起点
        sub = s[i:i+k]
        if s[i - 1] == 'C' or s[i - 1] == 'G':            # 如果左侧刚刚退出一个字符C或G，则计数器-1
            cur -= 1
        if s[i + k - 1] == 'C' or s[i + k - 1] == 'G':    # 如果右侧刚刚进入一个字符C或G，则计数器+1
            cur += 1
        # print(sub, cur, sub.count('G')+sub.count('C'))
        if cur > mx:                                      # 是否要更新新的结果
            res = sub
            mx = cur
    print(res)
    return

while True:
    try:
        s = input()
        k = int(input())
        solution(s, k)
    except:
        break