滑动窗口类型题

    技术2022-07-12  76

    第一题:滑动窗口的最大值 来自:【剑指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的位置上,就可以用滑动数组把最后两位的数字也包含进去了

    对比一下

    Processed: 0.013, SQL: 9