精华内容
下载资源
问答
  • 滑动窗口算法 滑动窗口算法可以用以解决数组/字符串的子元素问题,它可以将嵌套的循环问题,转换为单循环问题,降低时间复杂度。 窗口可以是固定大小,起始和终止位置同时变化。 也可以是可变大小,起始和终止位置...

    题目

    给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。

    示例 1:

    输入: "abcabcbb"

    输出: 3

    解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

    示例 2:

    示例 2:

    输入: "bbbbb"

    输出: 1

    解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

    示例 3:

    示例 3:

    输入: "pwwkew"

    输出: 3

    解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。

    请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

    滑动窗口算法

    滑动窗口算法可以用以解决数组/字符串的子元素问题,它可以将嵌套的循环问题,转换为单循环问题,降低时间复杂度。

    窗口可以是固定大小,起始和终止位置同时变化。

    1604093-20200214230243040-2077867364.jpg

    也可以是可变大小,起始和终止位置不同时变化。

    1604093-20200214230250898-1459904665.jpg

    1604093-20200214230328411-500495356.jpg

    思路

    利用滑动窗口,从第一个字符开始向后查看,当找到重复字符k时,将字串k(包括k)之前的字符全部舍去,然后更新maxlen的大小,直至移动到结尾。

    python代码实现

    (注意获取长度的细节)

    def lengthOfLongestSubstring(s: str) -> int:

    i=1 #当前字符的位置

    begin=0

    maxlen=0

    dropedlen=0#记录舍去的字符串的长度

    if len(s)==0:

    return 0

    if len(s)==1:

    return 1

    for i in range(len(s)):

    if s[i] in s[begin:i]:

    # 先更新maxlen

    templ=len(s[begin:i])

    print("s[i]="+s[i])

    print("字串="+s[begin:i])

    print("templ = "+str(templ))

    maxlen=templ if(templ>maxlen) else maxlen

    # 舍去字串s[begin:i]中s[i]字符及前面的字符

    # 直接用s[begin:i].index(s[i])获得的是相对位置,不是在s中的位置,应该加上dropedlen

    relativelen=s[begin:i].index(s[i])#重复的字符串的相对位置

    begin=relativelen+dropedlen+1

    dropedlen=begin#更新删除的长度

    # 到字符串末再更新一次maxlen

    templ=len(s[begin:i])+1

    maxlen=templ if(templ>maxlen) else maxlen

    return maxlen

    s = "au"

    print("答案:"+str(lengthOfLongestSubstring(s)))

    展开全文
  • 题目给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。结果返回滑动窗口中的最大值。示例:输入: nums = [1,3,-1...

    题目

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

    结果返回滑动窗口中的最大值。

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

    输出: [3,3,5,5,6,7]

    解释:

    滑动窗口的位置???? 最大值

    [1 3 -1] -3 5 3 6 7 ? ?? 3

    1 [3 -1 -3] 5 3 6 7 ???? 3

    1 3 [-1 -3 5] 3 6 7 ?? ? 5

    1 3 -1 [-3 5 3] 6 7 ?? ? 5

    1 3 -1 -3 [5 3 6] 7 ?? ? 6

    1 3 -1 -3 5 [3 6 7] ?? ? 7

    提示:你可以假设k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。(但是在数组可以为空,这个时候k会等于0)(LeetCode都是骗人的233)

    除了暴力遍历方法,可以通过存储滑动窗口的数据结构入手,使用堆或者双向队列存储滑动窗口内的值。这里选择堆(双向队列貌似更简单更快)。

    "每次只找最大值"启发了我使用胜者树来解决问题。

    胜者树与败者树

    胜者树和败者树都是完全二叉树,是树形选择排序的一种变型。每个叶子结点相当于一个选手,每个中间结点相当于一场比赛,每一层相当于一轮比赛。

    不同的是,胜者树的中间结点记录的是胜者的标号;而败者树的中间结点记录的败者的标号。

    胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后,利用中间结点的信息,还是能够快速地找到最值。在k路归并排序中经常用到。

    思路

    使用胜者树有两个关键点:第一是如何初始化,第二是当滑动窗口移动时,胜者树如何重构。

    初始化

    首先确定树的实现方法。由于是完全二叉树,可以使用数组(列表)模拟树型结构。list[1]为根节点,对于任意节点list[i],list[i/2]为父节点,(python的整数除为//而不是/) list[i/2*2]和list[i/2*2+1]为左右子节点

    其次确定树的节点个数(数组的大小)。对于k个要比较的数据,创建一个2k-1大小的完全二叉树即可。(注意各个节点对应的数组下标)

    重构

    首先确定新加入的“选手”在树中叶子节点的位置。当滑动窗口移动时,每次替换的叶子节点位置也依次变化。

    根据胜者树逐层向上比较,最终找到最大值。

    实现步骤

    用数组nums的前k个元素构造胜者树并初始化

    逐渐向后遍历nums的每个元素,将其加入胜者树进行比较,找到当前滑动窗口的最大值并记录。

    python3实现

    def maxSlidingWindow(nums, k: int):

    result=[]

    if not nums:

    return result

    elif k==1:

    return nums

    # 确定胜者树的大小

    size=2*k

    tail=size-1

    # 初始化胜者树

    tree=[None]*size

    for i in range (k):

    tree[i+k]=nums[i]

    p=tail

    while(p!=1):

    if tree[p]>tree[p-1]:

    tree[p//2]=tree[p]

    else:

    tree[p//2]=tree[p-1]

    p-=2

    result.append(tree[1])

    # 重建胜者树

    extra=0

    for index in range(k,len(nums)):

    number=nums[index]

    # p为替换的"选手"的位置

    # 由于滑动窗口向前滑动,每次替换的叶子节点的位置不一样,因此重新计算p

    # extra用来决定替换位置,具体替换规律可通过画图观察得到

    p=tail-k+1+extra%k

    tree[p]=number

    while(p!=1):

    parent=p//2

    l_child=parent*2

    r_child=l_child+1

    if tree[l_child]>tree[r_child]:

    tree[parent]=tree[l_child]

    else:

    tree[parent]=tree[r_child]

    p=parent

    result.append(tree[1])

    extra+=1

    return result

    num=[1,3,-1,-3,5,3,6,7]

    print(maxSlidingWindow(num,3))

    心得体会

    本题借用了胜者树败者树的思路,但是跟“外部排序”略有不同,只能使用胜者树,不能使用败者树,因为排序的时候是找到最大(最小)值后就将根节点的值弹出不再使用(即每次重构根节点的值都会更新),而本题最大(最小)值可能会重复使用(即每次重构根节点的值不一定会更新)。败者树只存储了败者,重构时一定会更新根节点,所以会出现问题。

    另外当滑动窗口移动时,重构时每次替换的叶子节点位置也依次变化,如果没注意这点,也会导致bug。

    原文:https://www.cnblogs.com/zhoujiayingvana/p/12327229.html

    展开全文
  • 题目给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。结果返回滑动窗口中的最大值。示例:输入: nums = [1,3,-1...

    题目

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

    结果返回滑动窗口中的最大值。

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

    输出: [3,3,5,5,6,7]

    解释:

    滑动窗口的位置     最大值

    [1 3 -1] -3 5 3 6 7      3

    1 [3 -1 -3] 5 3 6 7     3

    1 3 [-1 -3 5] 3 6 7      5

    1 3 -1 [-3 5 3] 6 7      5

    1 3 -1 -3 [5 3 6] 7      6

    1 3 -1 -3 5 [3 6 7]      7

    提示:你可以假设k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。(但是在数组可以为空,这个时候k会等于0)(LeetCode都是骗人的233)

    除了暴力遍历方法,可以通过存储滑动窗口的数据结构入手,使用堆或者双向队列存储滑动窗口内的值。这里选择堆(双向队列貌似更简单更快)。

    "每次只找最大值"启发了我使用胜者树来解决问题。

    胜者树与败者树

    胜者树和败者树都是完全二叉树,是树形选择排序的一种变型。每个叶子结点相当于一个选手,每个中间结点相当于一场比赛,每一层相当于一轮比赛。

    不同的是,胜者树的中间结点记录的是胜者的标号;而败者树的中间结点记录的败者的标号。

    胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后,利用中间结点的信息,还是能够快速地找到最值。在k路归并排序中经常用到。

    思路

    使用胜者树有两个关键点:第一是如何初始化,第二是当滑动窗口移动时,胜者树如何重构。

    初始化

    首先确定树的实现方法。由于是完全二叉树,可以使用数组(列表)模拟树型结构。list[1]为根节点,对于任意节点list[i],list[i/2]为父节点,(python的整数除为//而不是/) list[i/2*2]和list[i/2*2+1]为左右子节点

    其次确定树的节点个数(数组的大小)。对于k个要比较的数据,创建一个2k-1大小的完全二叉树即可。(注意各个节点对应的数组下标)

    1604093-20200218175102291-159209743.jpg

    重构

    首先确定新加入的“选手”在树中叶子节点的位置。当滑动窗口移动时,每次替换的叶子节点位置也依次变化。

    根据胜者树逐层向上比较,最终找到最大值。

    实现步骤

    用数组nums的前k个元素构造胜者树并初始化

    逐渐向后遍历nums的每个元素,将其加入胜者树进行比较,找到当前滑动窗口的最大值并记录。

    python3实现

    def maxSlidingWindow(nums, k: int):

    result=[]

    if not nums:

    return result

    elif k==1:

    return nums

    # 确定胜者树的大小

    size=2*k

    tail=size-1

    # 初始化胜者树

    tree=[None]*size

    for i in range (k):

    tree[i+k]=nums[i]

    p=tail

    while(p!=1):

    if tree[p]>tree[p-1]:

    tree[p//2]=tree[p]

    else:

    tree[p//2]=tree[p-1]

    p-=2

    result.append(tree[1])

    # 重建胜者树

    extra=0

    for index in range(k,len(nums)):

    number=nums[index]

    # p为替换的"选手"的位置

    # 由于滑动窗口向前滑动,每次替换的叶子节点的位置不一样,因此重新计算p

    # extra用来决定替换位置,具体替换规律可通过画图观察得到

    p=tail-k+1+extra%k

    tree[p]=number

    while(p!=1):

    parent=p//2

    l_child=parent*2

    r_child=l_child+1

    if tree[l_child]>tree[r_child]:

    tree[parent]=tree[l_child]

    else:

    tree[parent]=tree[r_child]

    p=parent

    result.append(tree[1])

    extra+=1

    return result

    num=[1,3,-1,-3,5,3,6,7]

    print(maxSlidingWindow(num,3))

    心得体会

    本题借用了胜者树败者树的思路,但是跟“外部排序”略有不同,只能使用胜者树,不能使用败者树,因为排序的时候是找到最大(最小)值后就将根节点的值弹出不再使用(即每次重构根节点的值都会更新),而本题最大(最小)值可能会重复使用(即每次重构根节点的值不一定会更新)。败者树只存储了败者,重构时一定会更新根节点,所以会出现问题。

    另外当滑动窗口移动时,重构时每次替换的叶子节点位置也依次变化,如果没注意这点,也会导致bug。

    展开全文
  • 这篇文章通过几道题目来总结滑动窗口算法的解题模板与技巧。 直接给出滑动窗口解题的模板 left, right = 0, 0 win = [] while right < len(s): win.append(s[right]) right += 1 while isValid(win): win....

    这篇文章通过几道题目来总结滑动窗口算法的解题模板与技巧。滑动窗口算法是双指针技巧的最高境界,掌握了滑动窗口的解题模板可以轻松解决一系列字符串匹配的问题。
    文章开头直接给出滑动窗口解题的模板

    left, right = 0, 0
    win = []
    while right < len(s):
    	win.append(s[right])
    	right += 1
    	
    	while isValid(win):
    		win.pop(0)
    		left += 1
    	
    

    209. 长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组,并返回其长度。如果不存在符合条件的连续子数组,返回 0。

    输入:s = 7, nums = [2,3,1,2,4,3]
    输出:2
    解释:子数组 [4,3] 是该条件下的长度最小的连续子数组。

    用窗口win保存当前的子数组,当移动right进入win满足条件时,更新结果并缩小左边界left。注意这里是正整数数组,所以满足的条件应该为sum(win)>=s。如果把正整数条件去掉,就不能用这个滑动窗口算法模板做了,因为你不知道什么条件下(是大于?等于?还是小于)去滑动窗口。

        def minSubArrayLen(self, s, nums):
            """
            用滑动窗口的模板来解题, 时间复杂度o(n) 空间复杂度o(1)
            """
            left, right = 0, 0
            win = []
            ans = len(nums) + 1
            while right < len(nums):
                win.append(nums[right])
                right += 1
    
                while sum(win) >= s:  # 维护的滑动窗口需要满足的条件
                    ans = min(ans, right-left)
                    win.pop(0)
                    left += 1
    
            return 0 if ans == len(nums) + 1 else ans
    

    如果是求最短的和为定值的子数组,那么只需要把模板中的isValid改成sum(win) > s,然后再次进行判断。

        def minSubArrayEq(self, s, nums):
            """
            寻找子序列和为s的最短子序列
            """
            left, right = 0, 0
            win = []
            ans = 0x3f3f3f3f
    
            while right < len(nums):
                win.append(nums[right])
                right += 1
    
                while sum(win) > s:
                    win.pop(0)
                    left += 1
                if sum(win) == s:
                    ans = min(ans, len(win))
    
            return 0 if ans == 0x3f3f3f3f else ans
    

    3. 无重复字符的最长子串

    给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

    输入: “abcabcbb”
    输出: 3
    解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

    需要建立一个map保存当前窗口win的字符集,当加入right之后如果map中存在重复元素,那么缩小左边界直到right这个元素只出现了一次。

        def lengthOfLongestSubstring(self, s):
            """
            3. 无重复字符的最长子串
            """
            left, right = 0, 0
            win = []
            map = dict()
            res = 0
    
            while right < len(s):
                cur = s[right]
                win.append(s[right])
                if s[right] in map:
                    map[s[right]] += 1
                else:
                    map[s[right]] = 1
                right += 1
    
                # 如果map中存在重复字符,则缩小左边界,直到当前cur字符在map中仅出现一次
                while map[cur] > 1:
                    map[s[left]] -= 1
                    win.pop(0)
                    left += 1
                res = max(res, right - left)
            return res
    

    76. 最小覆盖子串

    给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。

    输入: S = “ADOBECODEBANC”, T = “ABC”
    输出: “BANC”
    说明:
    如果 S 中不存这样的子串,则返回空字符串 “”。
    如果 S 中存在这样的子串,我们保证它是唯一的答案。

    关键在于isValid的定义:当win包含t串的所有字符,left才左移。所以isValid应该是判断win是否包含t的所有字符。通过分别定义两个串的两个map即可实现,但是这边注意不需要在函数内部定义新map,直接定义关于当前窗口wint串的map,然后在滑动窗口的同时更新map即可。

        def minWindow(self, s, t):
            """
            76. 最小覆盖子串:在字符串 S 里面找出:包含 T 所有字符的最小子串。
            """
            left, right = 0, 0
            win = []
            ans = 0x3f3f3f3f
            ansleft, ansright = -1, -1
    
            # 两个map,来判断字符的覆盖情况
            map_t = dict()
            map_win = dict()
            for i in range(len(t)):
                if t[i] in map_t:
                    map_t[t[i]] += 1
                else:
                    map_t[t[i]] = 1
    
            def isValid(map_win, map_t):
                """
                判断win是否包含t的所有字符
                """
                for key, value in map_t.items():
                    if key not in map_win:
                        return False
                    if map_win[key] < value:
                        return False
                return True
    
            while right < len(s):
                win.append(s[right])
                # 多出来的这块是更新map_win
                if s[right] in map_win:
                    map_win[s[right]] += 1
                else:
                    map_win[s[right]] = 1
                right += 1
    
                while isValid(map_win, map_t):
                    if right - left < ans:
                        ans = right - left
                        ansleft = left
                        ansright = right - 1
                    # 删除left元素需要更新map_win
                    map_win[s[left]] -= 1
                    if map_win[s[left]] == 0:  # 删除这个键
                        del map_win[s[left]]
                    win.pop(0)
                    left += 1
    
            if ans == 0x3f3f3f3f:
                return ""
            else:
                return s[ansleft:ansright + 1]
    

    438. 找到字符串中所有字母异位词

    给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。
    字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 20100。

    说明:
    字母异位词指字母相同,但排列不同的字符串。
    不考虑答案输出的顺序。

    输入:
    s: “cbaebabacd” p: “abc”
    输出:
    [0, 6]
    解释:
    起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
    起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。

    这道题只需要在上面那道题的基础上改:将更新结果的判断条件改成len(win)==len(t)即可

        def findAnagrams(self, s, p):
            """
            438. 找到字符串中所有字母异位词
            """
            left, right = 0, 0
            win = []
            res = []
    
            # 两个map,来判断字符的覆盖情况
            map_p = dict()
            map_win = dict()
            for i in range(len(p)):
                if p[i] in map_p:
                    map_p[p[i]] += 1
                else:
                    map_p[p[i]] = 1
    
            def isValid(map_win, map_t):
                """
                判断win是否包含t的所有字符
                """
                for key, value in map_t.items():
                    if key not in map_win:
                        return False
                    if map_win[key] < value:
                        return False
                return True
    
            while right < len(s):
                win.append(s[right])
                # 多出来的这块是更新map_win
                if s[right] in map_win:
                    map_win[s[right]] += 1
                else:
                    map_win[s[right]] = 1
                right += 1
    
                while isValid(map_win, map_p):
                    if right - left == len(p):  # 长度相等时保存结果
                        res.append(left)
                    # 删除left元素需要更新map_win
                    map_win[s[left]] -= 1
                    if map_win[s[left]] == 0:  # 删除这个键
                        del map_win[s[left]]
                    win.pop(0)
                    left += 1
    
            return res
    
    展开全文
  • 我已经构建了一个封装匹配的模型,我无法弄清楚如何在滑动窗口中使用它来跨更长的序列应用它来查找序列中的匹配.我有2(20,4)个输入张量(查询和目标),我连接,添加,展平,然后应用一个简单的密集层.我在这个阶段有数据来...
  • Python滑动平均算法(Moving Average)方案:#!/usr/bin/env python# -*- coding: utf-8 -*-import numpy as np# 等同于MATLAB中的smooth函数,但是平滑窗口必须为奇数。# yy = smooth(y) smooths the data in the...
  • duration是滑动屏幕持续的时间,时间越短速度越快。默认为None可不填,一般设置500-1000毫秒比较合适。向下滑动实例封装滑动方法,代码如下:2、点击手机屏幕坐标-tap使用场景:有时候定位元素的时候,你...
  • 在从这个结果中,您可以简单地迭代现在派生的窗口并像以前一样输出文件,或者您也可以根据需要使用嵌套数据并获得单独的窗口进行处理。在输出示例如下。如果有什么需要更详细的信息请告诉我。。。在import pprint#.....
  • 题目链接:https://leetcode-cn.com/probl... 0x01:算法思路 想象一块在窗口滑动的玻璃窗,它的“左”边和“右”边都是可以移动的,也就是这个玻璃窗的位置可以移动,宽度也可以变化。这么一说好像更像窗帘…… ...
  • 基本认识滑动窗口算法的本质是双指针法中的左右指针法,滑动窗口算法是双指针法中的左右指针法更为形象的一种表达方式。滑动窗口算法可以用以解决数组、字符串的子元素问题。所谓滑动窗口,就像描述的那样,可以理解...
  • 滑动窗口(Sliding Windows)拿车辆识别举例,首先我们把图片切割成很多正方型,为了保证不丢失信息,每个正方形都与上一个正方形有重叠.因为我们不确定图片中目标的大小,所以可以使用不同大小的正方形对图片进行切割....
  • 滑动窗口算法求最大无重复子串长度: ** 1.维护一个起始长度为0的窗口,窗口内都是没有重复的字符。 2.逐个遍历接收到的字符串,如果新遍历到的字符没有在窗口中出现过,那么窗口就“吃掉”这个字符,窗口右边...
  • 滑动窗口Sliding Window原理代码设计基本模块代码实现LeetCode实例(待补充)3. 无重复字符的最长子串30. 串联所有单词的子串76. 最小覆盖子串159. 至多包含两个不同字符的最长子串209. 长度最小的子数组239. 滑动...
  • 注意:计算窗口内数据的时机很重要,是在while前还是while后要class Solution:def minWindow(self, s: str, t: str) -> str:needs = dict() # 需要的子串for t_char in t:if needs.get(t_char):needs[t_char] = ...
  • This is too slow in Python. I found many posts on stackoverflow about sliding windows but the computation takes for ever. I have an example shown below, it works but takes forever. I guess this must ...
  • 那么生成的图像就会少多少像素列,e负责计算视差为i时,两张图整体的差距 e2=np.zeros(img_size) #计算窗口内的和 for x in range((window_size),(img_size[0]-window_size)): for y in range((window_size),(img_...
  • class Solution: def lengthOfLongestSubstring(self, s: str) -> int: n = len(s) res = left = 0 counter = collections.Counter() for right in range(n): counter[s[right]] += 1 ...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 199
精华内容 79
关键字:

滑动窗口算法python

python 订阅