当前位置: 首页 > 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. 如何选择…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...