当前位置: 首页 > news >正文

滑动窗口用法

文章目录

  • 1. 长度最小的子数组(模板)
  • 2. 无重复字符的最长字串
  • 3. 最小覆盖字串
  • 4. 加油站
  • 5. 替换字串得到平衡字符串

1. 长度最小的子数组(模板)

image-20240310211503255

  1. 题目分析
直接用步骤分析示例1,[]表示窗口,min_length表示满足条件的最短子数组,sum表示窗口内元素的总值:- [2],3,1,2,4,3		min_length=100001,sum=2 < target=7- [2,3],1,2,4,3		min_length=100001,sum=5 < target=7- [2,3,1],2,4,3		min_length=100001,sum=6 < target=7- [2,3,1,2],4,3		min_length=4,     sum=8 >= target=7- PS:只要sum>=target,就尝试将左窗口向右移动,若仍满足条件,就更新min_length,不行就继续- [2,3,1,2,4],3		min_length=5,	  sum=12 >= target=7- 2,[3,1,2,4],3		min_length=4,	  sum=10 >= target=7- 2,3,[1,2,4],3		min_length=3,	  sum=7 >= target=7- 2,3,[1,2,4,3]		min_length=4,	  sum=10 >= target=7- 2,3,1,[2,4,3]		min_length=3,	  sum=9 >= target=7- 2,3,1,2,[4,3]		min_length=2,	  sum=7 >= target=7- 最后返回min_length=2
  1. 代码实现
def minSubArrayLen(target, nums):""":type target: int:type nums: List[int]:rtype: int"""n = len(nums)# l表示左窗口的位置,r表示右窗口的位置l = r = 0# sum表示窗口内的元素总值sum = nums[0]# 如果第一个元素的值就大于等于target,直接返回if sum >= target:   return 1# 设置成100001是因为测试用例的数组长度最长为100000min_length = 100001# 循环n - 1次for i in range(1, n):# 右窗口肯定是要一直移动的,不存在每次循环不移动的情况r += 1sum += nums[r]# 如果sum去掉靠近左窗口的那个元素后仍然大于sum,就该减小窗口的长度了while sum - nums[l] >= target:sum -= nums[l]l += 1# 经过上述步骤后,当来到右窗口此时的位置时,满足条件的窗口长度就得到了if sum >= target:min_length = min(min_length, r - l + 1)# 数组所有元素的总和加起来都小于target,min_length就返回0return 0 if min_length == 100001 else min_length

image-20240310215745912

  1. 精简版
def minSubArrayLen(target, nums):""":type target: int:type nums: List[int]:rtype: int"""n = len(nums)l = r = 0min_length = 100001sum = 0while r < n:sum += nums[r]while sum - nums[l] >= target:sum -= nums[l]l += 1if sum >= target:min_length = min(min_length, r - l + 1)r += 1return 0 if min_length == 100001 else min_length

image-20240310221133426

2. 无重复字符的最长字串

image-20240310222352348

注意s字符串包含:字母、数字、符号和空格

  1. 题目分析:
以abcabcbb为例,max_length表示最长无重复字串字串,l表示左窗口,r表示右窗口:- [a]bcabcbb		max_length=1- [ab]cabcbb		max_length=2- [abc]abcbb		max_length=3- [abca]bcbb- 下面这一步就很重要了,l=max(l,a上一次出现位置+1)- a[bca]bcbb		max_length=3- a[bcab]cbb		l=max(l,b上一次出现位置+1)- ab[cab]cbb		max_length=3- ab[cabc]bb		l=max(l,c上一次出现位置+1)- abc[abc]bb		max_length=3- abc[abcb]b		l=max(l,b上一次出现位置+1)- abcab[cb]b		max_length=3- abcab[cbb]		l=max(l,b上一次出现位置+1)- abcabcb[b]		max_length=3
  1. 代码实现
def lengthOfLongestSubstring(s):""":type s: str:rtype: int"""n = len(s)# 字母、数字、空格和一些符号的ascii码都在0~255之间pos = [-1] * 255l = 0max_length = 0for r in range(n):# 在r移动到下一个字符位置时,一定要先让l获取上次这个字符出现的位置并且加1l = max(l, pos[ord(s[r])] + 1)# 然后再更新这个字符出现的位置pos[ord(s[r])] = r# 最后通过比较获得wu'cmax_length = max(max_length, r - l + 1)return max_length

image-20240310230922966

3. 最小覆盖字串

image-20240311171925285

  1. 题目分析
1. 拿一个cnts数组统计t串中字符的出现次数,total记录t中每个字符出现次数的总和
2. 首先,t中字符每出现一次,cnts[ord(t[i])] -= 1
3. 然后开始循环s字符串
4. 如果遇到出现次数小于0的,total就减-1
5. 每循环一次,该字符的出现次数就加1(我们只关注t中的字符,s中其它字符正常加就行了,后面不会涉及到它们)
6. 当total == 0时,也就是说当前窗口中已经包含了t中所有字符
7. 开始判断,左窗口所指向的字符出现次数是否大于0,大于0左窗口就可以向右移动了
8. PS:当total第一次等于0时,表示窗口中恰好有t中每个字符,且它们的出现次数都为0,后续可能会有多余的,它们的出现次数就会大于0,s中其它字符最开始都是0,只要在窗口中,它们的出现次数就会大于0
9. 然后判断当前窗口的长度跟最小覆盖字串的长度比较,取较小的那个cnts是统计所有字符的出现次数,初始化为0- 首先是将t串中每个字符的出现次数减1,也就是说,除了t串中的字符出现次数是负数,其它字符的出现次数都是0- 然后就是只要有一个字符进窗口,出现次数加1- 当左窗口字符出现次数大于0时,就可以考虑将其删除了
  1. 代码实现
def minWindow(s, t):""":type s: str:type t: str:rtype: str"""n = len(s)m = len(t)# 如果s串长度小于m长度,s就不可能有长度大于等于m的字串if n < m:return ""total = m# 计数数组cnts = [0] * 255# 给t串中每种字符出现次数为负数for i in range(m):cnts[ord(t[i])] -= 1l = 0target = ''min_length = 100001# 开始遍历s串for r in range(n):# 能满足下面if语句条件的一定是t串中的字符if cnts[ord(s[r])] < 0:total -= 1# 不管是哪个串中的字符,次数都要加1cnts[ord(s[r])] += 1# total==0表示窗口中已经包含了t串所有字符if total == 0:# 开始判断左窗口可不可以移动while cnts[ord(s[l])] > 0:cnts[ord(s[l])] -= 1l += 1# 取最小覆盖字串的长度if r - l + 1 < min_length:min_length = r - l + 1target = s[l : r + 1]return target

image-20240311201530260

4. 加油站

image-20240311210500668

  1. 题目分析
用左窗口遍历一遍加油站即可,此时左窗口就相当于起点,右窗口就从左窗口开始向后遍历,只要出现油不够的情况,左窗口就向右移动。可以将gas和cost数组合并来看,例如:
gas 	= [1,2,3,4,5]
cost	= [3,4,5,1,2]
combine = [-2,-2,-2,3,3]
combine[0]表示从第0个加油站开到第1个加油站倒欠2升油,所以无法以第0个加油站为起点,开到第一个加油站
combine[3]表示从第4个加油站开到第5个加油站多出了3升油,所以能以第4个加油站为起点,开到第五个加油站
  1. 代码
def canCompleteCircuit(gas, cost):""":type gas: List[int]:type cost: List[int]:rtype: int"""n = len(gas)# sum表示路上的总油量,只要油量小于0了,就不能走sum = 0# len表示一共走了几个加油站length = 0for l in range(n):while sum >= 0:# 如果从某个加油站出发,能走完一圈,就返回那个加油站的位置if length == n:return lr = (l + length) % nlength += 1sum += gas[r] - cost[r]# 走到这说明sum<0了,那么左窗口就该移动了,且sum要减去左窗口移动之前所在位置的那个值,len也要减1sum -= gas[l] - cost[l]length -= 1# 如果以每个加油站为起点出发,sum最后都会小于0,就返回-1return -1

image-20240311212755937

5. 替换字串得到平衡字符串

image-20240311221316817

  1. 题目分析
思路:
1. 先统计每种字符的出现次数
2. 然后用窗口框柱一段字符,假设窗口外的每种字符出现次数不等于 n/4,判断只替换窗口内的字符能否使窗口外的每种字符字符出现次数都变成n/4
3. 如果该窗口不行,那么它的子窗口一定不行(这里没想出为什么)如果[l,r-1]不行,[l,r]行,那么[l+1,r]也有可能行,[l+1,r-1]就一定不行4. 那么怎么实现第二步?假如窗口长度为8,窗口外面字符出现次数为Q->18,W->19,E->16,R->19,要求是每种字符出现20次8-(20-18) = 66-(20-19) = 55-(20-16) = 11-(20-19) = 0最后剩余0,表示能行如果外面某种字符超过了平均出现次数,那么这个窗口一定不行
  1. 代码实现
def balancedString(s):""":type s: str:rtype: int"""# 这个函数就是实现上面分析的第四步# len表示窗口的大小,也就是有len个元素可以替换,看能不能使窗口外面的每种字符出现次数达到averdef ok(cnts, len, aver):for i in range(4):if cnts[i] > aver:return Falselen -= aver - cnts[i]return True if len == 0 else Falsen = len(s)aver = n // 4# 将Q映射成0,W映射成1,E映射成2,R映射成3data = ['Q', 'W', 'E', 'R']cnts = [0] * 4for i in range(n):cnts[data.index(s[i])] += 1# 作为替换字串的最小长度返回ans = nr = 0# 左窗口开始遍历sfor l in range(n):# l-r表示[l,r)范围# 如果当前窗口不行,右窗口jiwhile ok(cnts, r - l, aver) == False and r < n:# 右窗口每次向右移动都会在窗口内新加入一个字符,它在窗口外的出现次数要减1cnts[data.index(s[r])] -= 1r += 1# 这里是为了判断上面循环是因为第一个条件结束还是因为第二个条件结束的# 若是因为第二个条件结束的,就说明这个窗口是合法的,当然这里只能判断第一个条件# 因为第一个条件也有可能不符合if r != n:ans = min(ans, r - l)# 最后一次循环结束后,左窗口会向右移动,相当于会将它原来所在位置的字符排除到窗口外,所以在窗口外这个字符的出现次数要加1cnts[data.index(s[l])] += 1return ans

image-20240311230406213

相关文章:

滑动窗口用法

文章目录 1. 长度最小的子数组&#xff08;模板&#xff09;2. 无重复字符的最长字串3. 最小覆盖字串4. 加油站5. 替换字串得到平衡字符串 1. 长度最小的子数组&#xff08;模板&#xff09; 题目分析 直接用步骤分析示例1&#xff0c;[]表示窗口&#xff0c;min_length表示满…...

智慧港口整体解决方案(一)

前言 智慧港口建设对创新驱动、转型发展具有重要推动作用加快推动第五代港口发展进程,成为当今港口转变发展方式、 提升企业综合竞争力的主潮流。智慧港口是港口未来发展主要方向 物联网、云计算技术发展智慧港口是物联网、移动互联网、云计算、人工智能等高新 技术与港口功能的…...

ubuntu如何限制系统日志大小?

ubuntu中的系统日志文件件如不及时清理&#xff0c;时间长了会占用硬盘的空间&#xff0c;如下所示&#xff1a; /var/log/journal/4321d62ad63d44cbbc4dff3b6e282b26/system9f5b4d5081d24b319f8b4677cf673a97-0000000000184ca6-00061412655a5a79.journal: 128M /var/log/journ…...

【Linux】线程概念及线程互斥

目录 线程概念 线程优点 线程缺点 线程异常 线程系统编程接口 线程创建及终止 线程等待 使用线程系统接口封装一个小型的C线程库并实现一个抢票逻辑 线程互斥 互斥量的接口 线程互斥实现原理 使用系统加锁接口封装LockGuard 实现自动化加锁 线程安全和可重入函数 …...

测试需求分析

测试需求是什么&#xff1f; --需求文档 测试需求主要解决**“测什么”的问题&#xff0c;一般来自需求规格说明书中原始需求 测试需求应全部覆盖已定义的业务流程&#xff0c;以及功能和非功能**方面的需求 功能&#xff1a;基本用户需求–优先 非功能&#xff1a;界面&#…...

Qt 翻译工具:使用 tr() 函数实现多语言支持

引言 在开发跨平台应用程序时&#xff0c;支持多语言是一个常见需求。Qt 提供了一套完整的国际化工具&#xff0c;帮助开发者轻松实现应用程序的本地化。本文将介绍如何在 Qt 中使用 tr() 函数进行翻译&#xff0c;并总结一些常见的困难和解决方法。 使用 tr() 函数进行翻译 …...

使用 kustomize 对 kubernetes 对象进行声明式管理

补丁实战 策略合并补丁 基准文件&#xff1a;/test/bases/deploy.yml apiVersion: apps/v1 kind: Deployment metadata:namespace: sharkname: my-nginx spec:selector:matchLabels:run: my-nginxreplicas: 2template:metadata:labels:run: my-nginxspec:containers:- name:…...

Android Studio开发学习(六)———TableLayout(表格布局)、FrameLayout(帧布局)

目录 前言 一、Tablelayout &#xff08;一&#xff09;Tablelayout的相关简介 &#xff08;二&#xff09;TableLayout使用方法 1. 当TableLayout下面写控件、则控件占据一行的大小。(自适应一行&#xff0c;不留空白) 2.多个组件占据一行&#xff0c;则配合TableRow实现…...

c++ override关键字

在C11及之后的标准中&#xff0c;override是一个关键字&#xff0c;用于表示派生类中的成员函数覆盖了基类中的虚函数。 使用override关键字的好处在于它提供了一种明确的方式来指示编译器&#xff1a;该函数打算覆盖基类中的虚函数。如果使用了override关键字&#xff0c;但该…...

卫星影像联合无人机实现农业保险全生命周期监管监测

随着科技的进步&#xff0c;农业保险监管系统的发展日新月异。特别是近年来&#xff0c;随着卫星技术与无人机技术的结合&#xff0c;为农业保险监管系统带来了前所未有的革新。本文将深入探讨如何利用卫星与无人机方案构建高效的农业保险监管系统&#xff0c;并结合实例进行说…...

ChatGLM2-6B_ An Open Bilingual Chat LLM _ 开源双语对话语言模型

ChatGLM2-6B_ An Open Bilingual Chat LLM _ 开源双语对话语言模型 文章目录 ChatGLM2-6B_ An Open Bilingual Chat LLM _ 开源双语对话语言模型一、介绍二、使用方式1、环境安装2、代码调用3、从本地加载模型 4、API 部署 三、低成本部署1、模型量化2、CPU 部署3、Mac 部署4、…...

JAVA的学习日记DAY6

文章目录 数组例子数组的使用数组的注意事项和细节练习数组赋值机制数组拷贝数组反转数组添加 排序冒泡排序 查找多维数组 - 二维数组二维数组的使用二维数组的遍历杨辉三角二维数组的使用细节和注意事项练习 开始每日一更&#xff01;得加快速度了&#xff01; 数组 数组可以…...

Grafana告警(邮件)自定义模板配置

一年前给客户部署配置过grafana&#xff0c;告警配置也是用的原始的&#xff0c;客户在使用过程中只需要一些核心点信息&#xff0c;想要实现这个就需要用Grafana的自定义告警模板以及编辑邮件模板。 通知模板 模板信息的配置中查阅了相关资料&#xff0c;自己组装了一套&…...

大话设计模式——六大基本设计原则(SOLID原则)

设计模式 定义&#xff1a;软件开发中&#xff0c;在特定上下文中解决一类常见问题的被证明为有效的最佳实践。可供其他开发者重复使用解决相似问题。 好处&#xff1a; 提高代码的可重用性&#xff0c;减少重复代码。提高代码的可维护性&#xff0c;使代码更易于理解和修改。…...

Qt | Q_PROPERTY属性和QVariant 类

一、属性基础 1、属性与数据成员相似,但是属性可使用 Qt 元对象系统的功能。他们的主要差别在于存取方式不相同,比如属性值通常使用读取函数(即函数名通常以 get 开始的函数)和设置函数(即函数名通常以 set 开始的函数)来存取其值,除此种方法外,Qt 还有其他方式存取属性值…...

力扣207.课程表

你这个学期必须选修 numCourses 门课程&#xff0c;记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出&#xff0c;其中 prerequisites[i] [ai, bi] &#xff0c;表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如…...

十五届web模拟题整理

模拟赛一期 1.动态的Tab栏 请在 style.css 文件中补全代码。 当用户向下滚动的高度没有超过标题栏&#xff08;即 .heading 元素&#xff09;的高度时&#xff0c;保持 Tab 栏在其原有的位置。当滚动高度超过标题栏的高度时&#xff0c;固定显示 Tab 栏在网页顶部。 /* TODO…...

ubuntu20.04 安裝PX4 1.13

step1_install_depenences.sh #!/bin/bash #install gazebo 11 #install protobuf 3.19.6python3 -m pip install --upgrade pip python3 -m pip install --upgrade Pillow# 將 empy 的版本調整爲3.3.4 pip3 uninstall empy pip3 install empy3.3.4sudo apt-get update sudo ap…...

大型网站系统架构演化

大型网站质量属性优先级&#xff1a;高性能 高可用 可维护 应变 安全 一、单体架构 应用程序&#xff0c;数据库&#xff0c;文件等所有资源都在一台服务器上。 二、垂直架构 应用和数据分离&#xff0c;使用三台服务器&#xff1a;应用服务器、文件服务器、数据服务器 应用服…...

探索Java中的栈:Stack与Deque(ArrayDeque和LinkedList)

文章目录 1. 栈&#xff08;Stack&#xff09;1.1 定义方式1.2 特点1.3 栈的层次结构 2. 双端队列&#xff08;Deque&#xff09;2.1 定义方式及继承关系2.2 特点&#xff1a;2.3 ArrayDeque2.4 LinkedList2.5 Deque 的各种方法2.6 如何选择ArrayDeque和LinkedList 3. 如何选择…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...