精华内容
下载资源
问答
  • 限流算法之滑动窗口(Java实现)上文简单介绍过限流中的计数器,详情参考:限流算法之计数器算法(Java实现)计数器有个缺点就是临界问题。举个例子,我们限制每分钟调用接口...临界问题解决上面问题可以用滑动...

    8943afcee5bec6c48046a13a58c6ebdd.png

    限流算法之滑动窗口法(Java实现)

    上文简单介绍过限流中的计数器法,详情参考:限流算法之计数器算法(Java实现)

    计数器法有个缺点就是临界问题。举个例子,我们限制每分钟调用接口不能超过1000次,用计数器法实现时,如果恶意用户在01:59秒一秒内发送1000次调用,又在02:01秒调用1000次,2秒内调用了2000次,这样就不能很好地限流了,也失去保护资源的作用。

    e57e0e972f8a11174e1da5cb2547100e.png

    临界问题

    解决上面问题可以用滑动窗口,令牌桶或者漏桶算法,今天先用滑动窗口算法实现。

    如果对滑动窗口不熟悉可以先了解下TCP的滑动窗口协议。限流中的滑动窗口可以简单理解为,设定的单位时间就是一个窗口,窗口可以分割多个更小的时间单元,随着时间的推移,窗口会向右移动。比如一个接口一分钟限制调用1000次,1分钟就可以理解为一个窗口,可以把1分钟分割为10个单元格,每个单元格就是6秒。

    79d2d6e14400d8e1b84835616d8e5cd3.png

    滑动窗口

    光说不练等不白干,下面就用一个简单的链表来简单实现,定义一个Node,Node中需要记录起始时间和调用计数器,并且有个指向下一个Node的变量,把所有的Node组成一个环

    用lastNode记录上次窗口的移动位置,再次访问时,先确定窗口滑动的位置,让窗口滑动到指定位置

    获取当前窗口的计数器的总数,如果不大于限制,当前的Node的计数器加一

    下面就是具体的实现代码,如果需要源码请私信。

    简单解释其中的几个变量的作用slot单位时间分割的数据

    limit单位时间限制的数量

    timeUnit自定义的枚举类,标识单位时间

    slotTime最小单元格的时间长度,单位是毫秒

    eef4c166adc1ccfd9c8ec490804a58a5.png

    Node

    dafba7944ad63adb6fa13c2ffb11e802.png

    Node

    6699c72e753217c6c62dc3b5eb5872b5.png

    主要业务逻辑

    ce373734473b4b6304789b67765b97d1.png

    初始化

    954d11606eba2954cfd398a7111be784.png

    定义的变量

    用滑动窗口来限流时,设置的单位时间越小,分割的时间越多,统计就会越准确。

    后续介绍令牌桶或者漏桶算法

    展开全文
  • 滑动窗口算法(matlab、java)

    千次阅读 2021-04-24 02:33:18
    import java.util.ArrayList;import java.util.Arrays;import java.util.Deque;import java.util.LinkedList;import java.util.List;/*** 返回一个n-w+1 长度的数组, 每个元素代表每个窗口中的最大值。...

    package cn.itcast_06;

    import java.util.ArrayList;

    import java.util.Arrays;

    import java.util.Deque;

    import java.util.LinkedList;

    import java.util.List;

    /**

    * 返回一个n-w+1 长度的数组, 每个元素代表每个窗口中的最大值。

    */

    public class SlideWindow {

    /**

    * array:源数组

    * w:窗口大小

    * 时间复杂度O(N*w)

    */

    public int[] moveWindow(int[] array, int w) {

    int[] result = new int[array.length - w + 1];

    for (int i = 0; (i + (w - 1)) < array.length; i++) {

    int[] newArr = Arrays.copyOfRange(array, i, i + w);

    Arrays.sort(newArr); // 左闭右开

    result[i] = newArr[w - 1];

    }

    return result;

    }

    /**

    * 最优解: 时间复杂度为O(N)

    * 利用双端队列

    */

    public Integer[] moveWindow1(Integer[] arr,int n, int w) {

    if(w == 1){

    return arr; //如果窗口大小为1, 直接返回数组即可

    }

    Deque deq = new LinkedList<>(); //双端队列

    List res = new ArrayList<>();

    for(int i=0; i

    //如果qmax为空,或者取出当前deque队尾存放的下标j 满足 arr[j] > array[i],

    //直接把下标i放进deque的队尾.

    if(deq.isEmpty() || arr[deq.getLast()] > arr[i]){

    deq.addLast(i);

    }else{

    //如果arr[j] <= array[i],则一直从deque的队尾弹出下标。

    //直到某个下标在deque中对应的值大于arr[i],就把i放入deque的队尾。

    while(!deq.isEmpty() && arr[deq.getLast()] <= arr[i]){

    deq.removeLast();

    }

    deq.addLast(i);

    }

    //如果deque队头的下标等于i-w,弹出deque当前队头下标.

    if(deq.getFirst() == i-w){

    deq.removeFirst();

    }

    //如果w窗口等于3的话,那么从i=2开始,产生的才是窗口的最大值。

    if(i < w-1){

    continue;

    }

    res.add(arr[deq.getFirst()]);

    }

    return (Integer[])res.toArray(new Integer[n-w+1]);

    }

    }

    展开全文
  • 由于区间是连续的,因此当整个区间发生变化时,可以通过对旧有的计算结果对搜索空间的剪枝(一般就是滑动窗口最左侧出的部分),从而减少了重复计算、降低了时间复杂度、避免了暴力的搜索。 往往类似于“请找到...

    简介

    所谓滑动窗口法,又称为“寸取法”,一般用来解决查找满足依一定条件的连续区间的特殊性质(长度等) 等一类问题。

    由于区间是连续的,因此当整个区间发生变化时,可以通过对旧有的计算结果对搜索空间的剪枝(一般就是滑动窗口最左侧滑出的部分),从而减少了重复计算、降低了时间复杂度、避免了暴力的搜索。

    往往类似于“请找到满足xx条件的最x区间/子串/子数组”这一类问题都可以使用滑动窗口法来进行解决。

    LeetCode滑动窗口问题专区

    涉及题目

    中等难度

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

    题目地址
    3. 无重复字符的最长子串

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

    示例 1:

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

    示例 2:

    输入: s = “bbbbb”
    输出: 1
    解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

    示例 3:

    输入: s = “pwwkew”
    输出: 3
    解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
    请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

    示例 4:

    输入: s = “”
    输出: 0

    提示:

    • 0 <= s.length <= 5 * 104
    • s 由英文字母、数字、符号和空格组成

    题目思路
    对于这道题,需要找到最长的连续、不重复字符的子串。

    经过之前的经验,我们可以得知,可以使用滑动窗口的方法来找到这样的满足条件的连续字符串。

    这里,条件是对应的子串中不能有重复的字符。因此,这里我们需要定义一个hash_map来保存最新的字符所对应的下标,并在right遍历字符串的过程中,定义left,表示左边界——即不存在重复字符的最左位置。

    对于遍历到的字符,判断该字符是否在对应的字符字典中,以及如果在其中,判断其出现的位置是否在left的范围内:

    • 如果该字符未曾出现过,或者出现的位置在left的左边,说明该字符是可以作为不含重复字符串的子串的,并计算最新的最长子串长度。
    • 否则,就需要更新left——注意这里需要跳过当前的字符,因此left = right + 1。
    • 每次,都需要更新字符出现的位置字典。

    最终,在right遍历到最后一个字符后,就可以得到这样最长的结果了。

    题目解法

    class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            letter_index_map = {}
            left, right = 0, 0
            res = 0
            while right < len(s):
                curr_letter_index = letter_index_map.get(s[right])
                if curr_letter_index is None or curr_letter_index < left:
                    res = max(res, right - left + 1)
                else:
                    left = curr_letter_index + 1
                letter_index_map[s[right]] = right
                right += 1
            return res
    

    LeetCode 209. 长度最小的子数组

    题目地址
    209. 长度最小的子数组

    题目描述
    给定一个含有 n 个正整数的数组和一个正整数 target 。

    找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

    示例 1:

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

    示例 2:

    输入:target = 4, nums = [1,4,4]
    输出:1

    示例 3:

    输入:target = 11, nums = [1,1,1,1,1,1,1,1]
    输出:0

    提示:

    • 1 <= target <= 109
    • 1 <= nums.length <= 105
    • 1 <= nums[i] <= 105

    题目思路
    对于这道题,首先需要注意的是,并不是说要求连续子序列的累加和等于target,而是要大于target。

    如果使用暴力求解的办法,自然也是可以做到的。但是,从题目的需求中我们可以看出,整体要求是满足“滑动窗口”的情景的。

    这里,整体的算法流程接口也类似,首先,外层有一个right指针,内层再做相关的数据判断和左侧边界的处理——由于这种处理是基于条件的,因此也是需要一个while循环来实现。

    因此,在算法的实现上,我们还是按照外层遍历、内层条件判断的策略,遍历整个数组,获得最终的结果。

    题目解法

    class Solution:
        def minSubArrayLen(self, target: int, nums: List[int]) -> int:
            left, right = 0, 0
            total_sum, res = 0, float('inf')
            while right < len(nums):
                total_sum += nums[right]
                while total_sum >= target:
                    res = min(res,right-left+1)
                    total_sum -= nums[left]
                    left += 1
                right += 1
            return 0 if res == float('inf') else res
    

    LeetCode 1004. 最大连续1的个数 III

    题目地址
    1004. 最大连续1的个数 III

    题目描述
    给定一个由若干 0 和 1 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。
    返回仅包含 1 的最长(连续)子数组的长度。

    示例 1:

    输入:A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
    输出:6
    解释:
    [1,1,1,0,0,1,1,1,1,1,1]
    粗体数字从 0 翻转到 1,最长的子数组长度为 6。

    示例 2:

    输入:A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
    输出:10
    解释:
    [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
    粗体数字从 0 翻转到 1,最长的子数组长度为 10。

    提示:

    1. 1 <= A.length <= 20000
    2. 0 <= K <= A.length
    3. A[i] 为 0 或 1

    题目思路
    对于这道题,就是一道较为经典的滑动窗口类问题。
    在这道题中,是最初的求最长连续1的长度的变形——中间有0,并且有替换的数量,进而求最长的1的长度。

    这里,我们定义一个滑动窗口 [left, right] 后,需要保证的窗口内全部都是1,这样最大的长度就是right - left + 1了。

    但是,由于有0,这样就需要right在向右滑动时,需要判断A[right]是否为0:

    • 如果是1,好说,直接向右滑动即可;
    • 如果是0,则需要记录curr_zero_num +=1,表示这一位我们置为了1——当然, 不可真的直接修改为1,否则后续left就无法得知A[left]原先到底是0还是1了。

    当curr_zero_num为K时,则说明所有的0置为1的机会、我们此时已经用完了,因此,下一步就需要left向右移动了:

    • 如果A[left]为1,也好说,直接继续右滑即可;
    • 如果是0,则说明可用的机会多了一个——原先为0的,目前我们已经不考虑了;

    通过left向右的滑动,知道curr_zero_num再次小于K即可。

    最后,不断计算right - left + 1的最大值即可。

    题目解法

    class Solution:
        def longestOnes(self, A: List[int], K: int) -> int:
            res = 0
            n = len(A)
            left = 0
            right = 0
            curr_zero_num = 0
            while right < n:
                if A[right] == 0:
                    curr_zero_num += 1
                while curr_zero_num > K:
                    if A[left] == 0:
                        curr_zero_num -= 1
                    left += 1
                res = max(res, right - left + 1)
                right += 1
            return res  
    
    展开全文
  • 博主在上一篇文章python影像裁剪并保存成tiff格式(规则网格)中介绍了将遥感影像按照网格切分,本章介绍滑动窗口的切分方法。 介绍 滑动窗口和规则网格的区别如下 规则网格: 滑动窗口: 此外,还有一种随机...

    博主在上一篇文章python影像裁剪并保存成tiff格式(规则网格法)中介绍了将遥感影像按照网格切分,本章介绍滑动窗口的切分方法。

    介绍

    滑动窗口和规则网格的区别如下

    规则网格:
    在这里插入图片描述
    滑动窗口:
    在这里插入图片描述
    此外,还有一种随机裁剪的方法
    在这里插入图片描述

    读取tiff文件数据,整理成我们需要的数组格式,将数组保存成tiff文件,和波段的叠加,mask矩阵的构建等等请参考博主之前的文章python影像裁剪并保存成tiff格式(规则网格法),内容不再重复,我们直接基于上篇文章开始修改,将规则网格升级为滑动窗口。当滑动窗口的重叠率为0时,就是规则网格法。

    定义函数

    裁剪

    def crop_img(img, cropsize, overlap):
        """
        裁剪图像为指定格式并保存成tiff
        输入为array形式的数组
        """
        num = 0
        height = img.shape[1]
        width = img.shape[2]
        print(height)
        print(width)
    
        # 从左上开始裁剪
        for i in range(int(height / (cropsize * (1 - overlap)))):  # 行裁剪次数
            for j in range(int(width / (cropsize * (1 - overlap)))):  # 列裁剪次数
                cropped = img[:,  # 通道不裁剪
                          int(i * cropsize * (1 - overlap)): int(i * cropsize * (1 - overlap) + cropsize),
                          int(j * cropsize * (1 - overlap)): int(j * cropsize * (1 - overlap) + cropsize),
                          ]  # max函数是为了防止i,j为0时索引为负数
    
                num = num + 1
                target = 'tiff_crop' + '/cropped{n}.tif'.format(n=num)
                gdal_array.SaveArray(cropped, target, format="GTiff")
    
        #  向前裁剪最后的列
        for i in range(int(height / (cropsize * (1 - overlap)))):
            cropped = img[:,  # 通道不裁剪
                      int(i * cropsize * (1 - overlap)): int(i * cropsize * (1 - overlap) + cropsize),  # 所有行
                      width - cropsize: width,  # 最后256列
                      ]
    
            num = num + 1
            target = 'tiff_crop' + '/cropped{n}.tif'.format(n=num)
            gdal_array.SaveArray(cropped, target, format="GTiff")
    
        # 向前裁剪最后的行
        for j in range(int(width / (cropsize * (1 - overlap)))):
            cropped = img[:,  # 通道不裁剪
                      height - cropsize: height,  # 最后256行
                      int(j * cropsize * (1 - overlap)): int(j * cropsize * (1 - overlap) + cropsize),  # 所有列
                      ]
    
            num = num + 1
            target = 'tiff_crop' + '/cropped{n}.tif'.format(n=num)
            gdal_array.SaveArray(cropped, target, format="GTiff")
    
    
        # 裁剪右下角
        cropped = img[:,  # 通道不裁剪
                  height - cropsize: height,
                  width - cropsize: width,
                  ]
    
        num = num + 1
        target = 'tiff_crop' + '/cropped{n}.tif'.format(n=num)
        gdal_array.SaveArray(cropped, target, format="GTiff")
    
    

    测试

    if __name__ == '__main__':
        base_path = 'data'
        img = get_img(base_path)
        cropsize = 256  # 裁剪尺寸
        overlap = 0.5 # 重叠率
        crop_img(img, cropsize, overlap)
        print('finish')
    

    这里用到的函数get_img是上篇文章介绍的函数。它的作用就是返回一个维度为(channels,height,width)的numpy数组。你也可以自己准备这样一个数组。

    out:

    (7301, 7341)
    (3, 7301, 7341)
    7301
    7341
    finish

    envi打开其中一张
    在这里插入图片描述

    展开全文
  • 例题: 思考:滑动窗口)先将特殊情况放在开头返回,定义两个指针start和end,初始都为0,分别表示子数组的开头和结尾,定义sum初始化为0,用来存储从start到end之间的子数组元素的和,每一轮迭代将nums[end]加到...
  • 滑动窗口

    2021-05-30 21:53:15
    滑动窗口用来解决一些查找满足一定条件的连续区间的性质(长度等)的问题。 由于区间连续,因此当区间发生变化时,可以通过旧有的计算结果对搜索空间进行剪枝,这样便减少了重复计算,降低了时间复杂度。 往往类似...
  • 标准滑窗法的模板题,先定义左右指针,右指针先移动直至不满足题目条件,再拖动左指针,直至找出最长的最多允许有 K 个 0 子数组。 滑窗python模板写法:...
  • 滑窗法

    2021-01-01 15:01:41
    # -*- coding: utf-8 -* import cv2 def imshow(imgname,img): h ,w = img.shape[:2] cv2.namedWindow(imgname, cv2.WINDOW_NORMAL) cv2.resizeWindow(imgname, int(w * 0.3), int(h * 0.3)) ...
  • 567. 字符串的排列 题目描述 给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例 1: 输入: s1 = “ab” s2 = “eidbaooo” ...
  • } } 相同字符组成的子串问题,立即推:滑动窗口 2.443. 压缩字符串 AC代码 class Solution { public int compress(char[] chars) { int right = 0, left = 0; int p = 0; // 原地修改输入数组 // [left, right) ...
  • 机器学习滑窗法

    2021-05-22 08:27:21
    AI开发平台ModelArtsModelArts是面向开发者的一站式AI开发平台,为机器学习与深度学习提供海量数据预处理及半自动化标注、大规模分布式Training、自动化模型生成,及端-边-云模型按需部署能力,帮助用户快速创建和...
  • , k = 2 输出:[4] Solution: 一开始的思路其实是将每个窗口的值遍历在栈中 同时每次max栈中的值返回在ans中 但是由于max函数运行效率太低,无法通过运算量过大的样例 所以利用滑动窗口对思路进行简化避免使用max...
  • 背景 分布式系统中,由于接口API无法控制上游调用方的行为,因此当瞬时请求量突增时,会导致服务器占用过多资源,发生响应速度降低、... 固定窗口计数 原理 特点 滑动窗口计数 原理 特点 参见 限流限速RateLimiter
  • 提示 1 , t.length  和 t 由英文字母组成 思路 解决这个题目,可以先看一道类似的简单一点的题:Leetcode-3:无重复字符的最长子串 这类题目,最优解应该就是滑动窗口。一开始打算用一个哈希表储存字符串t里...
  • 滑动窗口滤波算法

    千次阅读 2020-12-28 23:44:41
    该算法在常见的平均取值上,增加了滑动窗口的概念,以及阈值比较的想法,与平均取值相比,有了更坚实的理论基础。 方法2:维护一个奇数长度(5)的窗口,根据预测和众数(数据重复的次数或者误差在一定范围内...
  • 滑动窗口之最小覆盖子串常规解法代码待优化点代码参考 常规解法 先扩大窗口:从左往右找目标字符并记录出现次数。 再缩小窗口:每找到一次目标字符即尝试缩小,看目标字符是否都出现了一次,且记录的字符出现次数...
  • 长度最小的子数组——滑动窗口 LeetCode209 题目描述: 注意题目说的是连续的子数组,所以这道题最简单的做法应该是滑动窗口,时间复杂度O(n),空间复杂度O(1)。定义左右指针分别为left和right表示窗口的起始位置...
  • 滑动窗口一、滑动窗口二、滑动窗口相关题型1.leetcode 209 长度最小的子数组2.leetcode 1456 定长子串中元音的最大数目 一、滑动窗口 目的是为了减少 while 循环。 用于解决数组中定长问题 二、滑动窗口...
  • 3. 无重复字符的最长子串(Leetcode刷题 滑动窗口) 文章目录3. 无重复字符的最长子串(Leetcode刷题 滑动窗口)题目示例解题思路解题代码代码效率 题目 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 ...
  • 题目链接 https://leetcode-cn.com/problems/longest-substring-with-at-most-two-distinct-characters/ 题目 给定一个字符串s,找出至多包含两个不同字符的最长子串t,并返回该子串的长度。 ...用滑动...
  • 示例 2: 输入:target = 4, nums = [1,4,4] 输出:1 示例 3: 输入:target = 11, nums = [1,1,1,1,1,1,1,1] 输出:0 提示 暴力思路 假设子数组左边left,右边right,起始位置都为0. 固定left,right一直向右...
  • 一张图滑动预测后,会输出多个结果,需对输出结果做NMS(非极大值抑制),再作为最终输出结果。 2、卷积的滑动窗口实现 构建滑动窗口的卷积应用,首先要知道如何把神经网络的全连接层转化成卷积层。具体做法:使用...
  • 424. 替换后的最长重复字符 题目描述 给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。...
  • 图像分割相关技术之滑动窗口、RPN以及anchor box简介标签:##时间:2019/11/17 11:07:25作者:小木对象识别(object recognition)是计算机视觉(computer vision)中的一种任务。根据维基百科的定义,它的目的是为了...
  • Parzen窗法

    2021-09-20 20:18:23
    Parzen窗法 1. 方法综述 假设x∈Rdx \in R^dx∈Rd是ddd维特征向量,并假设每个小舱是一个超立方体,它在每一维的棱长都为hhh,则小舱的体积是: V=hd(1) V=h^d \tag 1 V=hd(1)
  • 滑窗法简单易于理解,但是不同窗口大小进行图像全局搜索导致效率低下,而且设计窗口大小时候还需要考虑物体的长宽比。所以,对于实时性要求较高的分类器,不推荐使用滑窗法。 这里在引用一种选择搜索的方法: 滑窗...
  • 常用的解题技巧:尺取 尺取:顾名思义,像尺子一样取一段,借用挑战书上面的话说,尺取通常是对数组保存一对下标,即所选取的区间的左右端点,然后根据实际情况不断地推进区间左右端点以得出答案。之所以需要...
  • %高效地使用Matlab加速滑动f=@(block_struct)imresize(block_struct.data,0.15);%注意处理函数的输入必须是结构体,其data域是我们的矩阵数据,这是由blockproc分块后的机制决定fun=@(block_struct)repmat(block_...
  • 本题解思想源于labuladond算法框架 public boolean checkInclusion(String s1, String s2) { HashMap <Character,Integer> window = new HashMap<Character,Integer>(); HashMap <...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,688
精华内容 11,875
关键字:

滑窗法