算法练习：最小覆盖子串 #滑动窗口

题目-最小覆盖子串：

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

过程

一开始企图用itertools来做个简单的索引笛卡儿积，算法复杂度略高。到某些很长的s时，本地可以算，但是服务器判断计算超时了OTZ。

class Solution:
    def findindex(self,y,s):
        index = []
        for i in range(len(s)):
            if s[i] == y:
                index.append(i) 
        return index
    def minWindow(self, s, t):
        import itertools
        PossiWindow = []
        result = ''
        min = len(s)
        for y in t:
            PossiWindow.append(self.findindex(y,s))
        for y in itertools.product(*(i for i in PossiWindow)) :
            if len(set(y)) != len(y):
                continue
            sy = sorted(y)
            leny = sy[-1]-sy[0]
            if leny < min:
                result = s[sy[0]:sy[-1]+1]
                min = leny
        print(result)

难受，搜了一下场外，看到关键词“滑动窗口”，sliding window ，适用于将嵌套for循环在少数问题中转换为单个for循环，减少算法复杂度。用中文翻译一下就是说对于寻找指定长度或最小的子串这种问题，可以直接搬来改改。
整理思路成：

统计t的字符出现数
按顺序读s,直到出现第一组包含t的子串。去掉左边无用的字符，记录此时的长度长度m，存result
保持长度为m-1的窗口，继续按顺序读s，直到下一组包含t的子串。去掉左边无用的字符，记录此时的长度m，存result
循环往右读长度为m-1的窗口,直到m==len(t)或者m长度找不到符合条件的字符串为止。

然后写成代码有

class Solution:
    def minWindow(self, s, t):
        tCount = {} #统计t的字符出现数
        for y in t:
            tCount[y]= t.count(y)  
        flag = len(tCount) #标记是否所有字符都满足条件
        head,m = 0,len(s)
        result = '' 
        for toe in range(len(s)):   #按顺序读s,直到出现第一组包含t的子串。去掉左边无用的字符，记录此时的长度长度m，存result
            if s[toe] in tCount:
                tCount[s[toe]] -= 1
                if tCount[s[toe]] == 0: flag -= 1 #有一个字符满足条件
                while flag == 0 : #所有字符都满足条件时，去掉左边多余字符
                    if (toe-head) < m :
                        result = s[head:toe+1]
                        m = toe-head
                    if s[head] in t:
                        tCount[s[head]] += 1
                        if tCount[s[head]] > 0:
                            flag += 1
                    head += 1
        return result

运行结果

补充练习-滑动窗口最大值：

为了巩固刚学会的滑动窗口，追加一道题。

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。
返回滑动窗口最大值。

示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

注意：
你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。

进阶：
你能在线性时间复杂度内解决此题吗？

过程：

因为电脑好（），第一反应还是直接一轮轮比较……然后被99%的代码鄙视了。

class Solution:
    def maxSlidingWindow(self, nums, k):
        step = 1
        result = []
        if nums:
            for head in range(len(nums)-k+1):
                m = nums[head]
                while step < k-1:
                    toe = head +step
                    if nums[toe] > m:
                        m = nums[toe]
                    step += 1
                if step == k-1:
                    toe = head +step
                    if nums[toe] > m:
                        m = nums[toe]
                    step = 1
                result.append(m)
        return result

好吧好吧我用window还不行吗！

class Solution:
    def maxSlidingWindow(self, nums, k):
        window, result = [], [] #window从大到小排列
        if nums:
            for head in range(len(nums)):
                #得到大于num[head]的有序列表
                while window and nums[window[-1]] <= nums[head]: 
                    window.pop(-1)
                window.append(head)
                #滑动时判断最左值是否是最大的，是则pop
                if head >= k and window[0] == head - k:
                    window.pop(0)
                if head >= k - 1:
                    result.append(nums[window[0]])
        return result

反正我就是中等水平了……

总结

对于寻找指定长度的最值条件，或符合条件的最小子串这种问题，试试滑动窗口，结合有序列表的pop。
数学不好的人脑壳疼，电脑好不行吗？（喂）

最后编辑于：2019.01.23 11:09:19