第一题:滑动窗口的最大值 来自:【剑指offer】
题目: 给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。
第二题:DNA序列 来自:【牛客网-华为机试】
题目: 输入描述: 输入一个string型基因序列,和int型子串的长度
输出描述: 找出GC比例最高的子串,如果有多个输出第一个的子串
示例1:
输入 AACTGTGCACGACCTGA 5
输出 GCACG
【总结】 这两道题都是用一个长度固定的滑动数组来遍历字符串 在遍历的过程中达到特定的结果并记录 最后输出所有结果中的最值
他们的框架简而言之分三步走: 一,for循环推动滑动数组移动 二,干活,得到特定结果,并找到最值进行存储 三,返回最值
注意第一步的遍历范围是range(len(s)-size+1) 保证滑动数组完整 例如第一题中字符串长度为8 8-3+1=6 range(6)=0,1,2,3,4,5 而我只需要让 i 走到5的位置上,就可以用滑动数组把最后两位的数字也包含进去了
对比一下