草庐IT

LeetCode练习day5-滑动窗口

zhuxh 2023-09-17 原文

滑动窗口（Sliding Window）

滑动窗口指的是这样一类问题的求解方法，在数组上通过双指针同向移动而解决的一类问题。其实这样的问题我们可以不必为它们专门命名一个名字，它们的解法其实是很自然的。

使用滑动窗口解决的问题通常是暴力解法的优化，掌握这一类问题最好的办法就是练习，然后思考清楚为什么可以使用滑动窗口。

  • 滑动：窗口可以按照一定的方向移动。
  • 窗口：窗口大小可以固定，也可以不固定，此时可以向外或者向内，扩容或者缩小窗口直至满足条件。

介绍

滑动窗口是一种解决问题的思路和方法，通常用来解决一些连续问题。 比如 LeetCode 的 209. 长度最小的子数组。更多滑动窗口题目见下方题目列表。

常见套路

滑动窗口主要用来处理连续问题。比如题目求解“连续子串 xxxx”，“连续子数组 xxxx”，就应该可以想到滑动窗口。能不能解决另说，但是这种敏感性还是要有的。

从类型上说主要有：

  • 固定窗口大小
  • 窗口大小不固定，求解最大的满足条件的窗口
  • 窗口大小不固定，求解最小的满足条件的窗口（上面的 209 题就属于这种）

后面两种我们统称为可变窗口。当然不管是哪种类型基本的思路都是一样的，不一样的仅仅是代码细节。

解决滑动窗口问题的基本步骤

滑动窗口更像是一种技术而不是一种算法。这是一种可以在许多算法中使用的技术。以下是解决与滑动窗口技术相关的问题的基本步骤：使用 hashmap 或字典来计算特定的数组输入并坚持使用外部循环向右增加窗口。在外部循环下，使得滑动窗口左侧向右滑动来维持窗口大小。使用这种方式降低循环次数根据问题陈述存储当前的最大或最小窗口大小或计数。

固定窗口大小

对于固定窗口，我们只需要固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点，并且保证：

  1. l 初始化为 0
  2. 初始化 r，使得 r - l + 1 等于窗口大小
  3. 同时移动 l 和 r
  4. 判断窗口内的连续元素是否满足题目限定的条件
    • 4.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解
    • 4.2 如果不满足，则继续。

可变窗口大小

对于可变窗口，我们同样固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点。后面有所不同，我们需要保证：

  1. l 和 r 都初始化为 0
  2. r 指针移动一步
  3. 判断窗口内的连续元素是否满足题目限定的条件
    • 3.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解。并尝试通过移动 l 指针缩小窗口大小。循环执行 3.1
    • 3.2 如果不满足，则继续。

形象地来看的话，就是 r 指针不停向右移动，l 指针仅仅在窗口满足条件之后才会移动，起到窗口收缩的效果。

模板代码

伪代码

初始化慢指针 = 0
初始化 ans

for 快指针 in 可迭代集合
   更新窗口内信息
   while 窗口内不符合题意
      扩展或者收缩窗口
      慢指针移动
   更新答案
返回 ans
LeetCode练习li窗口的

有关LeetCode练习day5-滑动窗口的更多相关文章

  1. 牛客网专项练习30天Pytnon篇第02天 - 2

    1.在Python3中，下列关于数学运算结果正确的是:（B）a=10b=3print(a//b)print(a%b)print(a/b)A.3，3，3.3333...B.3，1，3.3333...C.3.3333...，3.3333...，3D.3.3333...，1，3.3333...解析：    在Python中，//表示地板除（向下取整），%表示取余，/表示除（Python2向下取整返回3）2.如下程序Python2会打印多少个数:（D）k=1000whilek>1:    print(k)k=k/2A.1000 B.10C.11D.9解析：    按照题意每次循环K/2，直到K值小于等

  2. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  3. ruby - (Ruby || Python) 窗口管理器 - 2

    我想用这两种语言中的任何一种(最好是ruby​​)制作一个窗口管理器。老实说，除了我需要加载某种X模块外，我不知道从哪里开始。因此，如果有人有线索，如果您能指出正确的方向，那就太好了。谢谢 最佳答案 XCB，X的下一代API使用XML格式定义X协议(protocol)，并使用脚本生成特定语言绑定(bind)。它在概念上与SWIG类似，只是它描述的不是CAPI，而是X协议(protocol)。目前，C和Python存在绑定(bind)。理论上，Ruby端口只是编写一个从XML协议(protocol)定义语言到Ruby的翻译器的问题。生

  4. ruby-on-rails - rails : Find tasks that were created on a certain day? - 2

    我有一个任务列表(名称、starts_at)，我试图在每日View中显示它们(就像iCal)。deftodays_tasks(day)Task.find(:all,:conditions=>["starts_atbetween?and?",day.beginning,day.ending]end我不知道如何将Time.now(例如“2009-04-1210:00:00”)动态转换为一天的开始(和结束)，以便进行比较。 最佳答案 deftodays_tasks(now=Time.now)Task.find(:all,:conditio

  5. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  6. 什么是0day漏洞？如何预防0day攻击？ - 2

    什么是0day漏洞？0day漏洞，是指已经被发现，但是还未被公开，同时官方还没有相关补丁的漏洞；通俗的讲，就是除了黑客，没人知道他的存在，其往往具有很大的突发性、破坏性、致命性。0day漏洞之所以称为0day，正是因为其补丁永远晚于攻击。所以攻击者利用0day漏洞攻击的成功率极高，往往可以达到目的并全身而退，而防守方却一无所知，只有在漏洞公布之后，才后知后觉，却为时已晚。“后知后觉、反应迟钝”就是当前安全防护面对0day攻击的真实写照！为了方便大家理解，中科三方为大家梳理当前安全防护模式下，一个漏洞从发现到解决的三个时间节点：T0：此时漏洞即0day漏洞，是已经被发现，还未被公开，官方还没有相

  7. ruby - Rails 比较 date.end_of_day.to_datetime 和 date.to_datetime.end_of_day 返回的日期对象值时返回 false - 2

    ruby1.9.3dev(2011-09-23修订版33323)[i686-linux]轨道3.0.20最近为什么在与DateTimeonRails相关的RSpecs项目上工作我发现在给定日期以下语句发出的值date.end_of_day.to_datetime和date.to_datetime.end_of_day虽然它们表示相同的日期时间，但比较时返回false。为了确认这一点，我打开了Rails控制台并尝试了以下操作1.9.3dev:053>monday=Time.now.monday=>2013-02-2500:00:00+05301.9.3dev:054>monday.cla

  8. ruby - 处理在 keyup 事件上发生的 javascript 弹出窗口 - 2

    我在HTML页面上有一个文本字段，用于检查您是否输入了1到365之间的值。如果用户输入了无效值，如非数字字符或不在范围内的值，它显示一个弹出窗口。我在watirwiki上看到有一个select_no_wait方法，用于在您从列表中选择无效值时关闭弹出窗口。处理键盘事件时出现的弹出窗口的好方法是什么？我是否需要按照select_no_wait方法的实现方式进行操作，或者我们是否可以启动一个不同的进程来消除调用set方法时可能出现的弹出窗口。带有Javascript验证函数的HTML文件示例如下:varnum=0functionvalidate(e){varcharPressed=Stri

  9. ruby - Watir Webdriver 如何关闭子窗口 - 2

    我正在将一些遗留的Watir脚本迁移到Watir-Webdriver。除了他们如何设计Watir-Webdriver来处理弹出窗口之外，迁移大部分进行得很顺利。他们没有使用久经考验的“附加”方法，而是用简化的“窗口”方法取而代之。语法非常简单，但是我很难理解如何在不关闭父窗口的情况下关闭单独的子窗口。目前我的代码是这样的-b.button(:xpath=>PREVIEWBUTTON).clickb.window(:title,POPUPWINDOW).useDOb.closeend目前正在发生的是b.close方法正在关闭子窗口和父窗口。我不确定为什么会这样，因为b.close方法包含

  10. ruby - 如何在 selenium-webdriver 中获取窗口标题、ID 和名称？ - 2

    我正在尝试从selenium-webdriver(ruby)实现以下方法get_all_window_idsget_all_window_titlesget_all_window_names我运行了SeleniumIDE并将我的脚本导出到RubyTest::Unit。另存为.rb使用AptanaStudio3打开我的脚本进行编辑初始代码片段如下:require"rubygems"require"selenium-webdriver"require"test/unit"classSwitchToPopup3我不断得到的错误是NoMethodError:undefinedmethod`ge

随机推荐