python算法与数据结构---滑动窗口双指针

学习目标

  • 了解滑动窗口的基本原理;
  • 学会用使用python语言解答滑动窗口经典题目;
  • 了解双指针的基本原理;
  • 学会使用python语言解答双指针经典题目;

滑动窗口

209. 长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/description/
在这里插入图片描述

暴力解法

  • 目标是找子数组,暴力遍历所有的子数组

  • 枚举子数组的下标i,对于每个开始下标i:

    • 枚举子数组的结束下标j(i<=j)
    • 使得nums[i]到nums[j]的元素和大于等于s
    • 更新子数组的最小长度(j-i+1)
  • 优化点:

    • 前提:nums数组中全是正整数
    • 枚举子数组的结束下标时,如果nums[i]到nums[j]的元素和大于等于s时,中断对结束下标的枚举
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:if not nums:return 0n = len(nums)ans = n + 1# 枚举子数组的开始下标i;for i in range(n):total = 0# 枚举子数组的结束下标jfor j in range(i, n):total += nums[j]# 更新子数组的最小长度(j-i+1)if total >= target:ans = min(ans, j - i + 1)breakif ans == n + 1:return 0else:return ans

滑动窗口

  • 定义两个指针start和end分别表示子数组(滑动窗口)的开始位置和结束位置,初始状态下都指向下标0;
  • 维护变量total存储子数组中的元素和(即从nums[start]到nums[end]的元素和)
  • 迭代:
    • 滑动窗口终止位置移动:在每一轮迭代的最后,将end右移,将nums[end]加到total
    • 滑动窗口起始位置移动:若total>=s,则更新子数组最小长度end-start+1,然后将nums[start]从total中减去并将start右移,直到total<s,同时不断更新子数组的最小长度
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:if not nums:return 0n = len(nums)ans = n + 1# 滑动窗口的开始位置和结束位置start, end = 0, 0total = 0 while end < n:total += nums[end]while total >= target:ans = min(ans, end - start + 1)total -= nums[start]# 滑动窗口起始位置移动start += 1# 滑动窗口终止位置移动end += 1if ans == n + 1:return 0else:return ans

滑动窗口图解

在这里插入图片描述

  • 扩张窗口:为了找到一个可行解,找到了就不再扩张,因为扩张不再有意义;
  • 收缩窗口:在长度上优化该可行解,直到条件被破坏;
  • 继续寻找下一个可行解,然后再优化到不能优化

567. 字符串的排列

https://leetcode.cn/problems/permutation-in-string/description/
在这里插入图片描述
题目建模:

  • 无需全排列:排列不会改变字符串中每个字符的个数,所以只有两个字符串每个字符的个数均相等时,一个字符串才是另一个字符串的排列
  • 建模:s1的每个字符出现的次数,与s2某个子串的每种字符出现次数相同。

滑动窗口解法

  • 维护两个数组dic1和dic2,其中dic1用于统计s1中各个字符的个数,dic2用于统计当前遍历子串中的各个字符的个数;
  • 由于需要遍历的子串长度均为m1,我们可以使用一个固定长度为m1的滑动窗口来维护dic2;
  • 滑动窗口每向右滑动一次,就多统计一次进入窗口的字符,少统计一次离开窗口的字符。然后,判断dic1是否与dic2相等,若相等则意味着当前窗口内的子串是s1的排列之一。
class Solution:def checkInclusion(self, s1: str, s2: str) -> bool:m1 = len(s1)m2 = len(s2)if m1 > m2:return False# 采用有序字典来比较,由于只包含小写字母,采用数组来模拟有序字典dic1 = [0] * 26dic2 = [0] * 26# 滑动窗口长度固定为m1for i in range(m1):dic1[ord(s1[i]) - ord('a')] += 1dic2[ord(s2[i]) - ord('a')] += 1if dic1 == dic2:return True# 滑动窗口每向右滑动一次,就多统计一次进入窗口的字符,少统计一次离开窗口的字符for i in range(m1, m2):dic2[ord(s2[i-m1]) - ord('a')] -= 1dic2[ord(s2[i]) - ord('a')] += 1if dic1 == dic2:return Truereturn False

双指针

  • 滑动窗口有本质上是双指针,窗口的开始位置和结束位置便是两个指针,窗口的滑动对应指针的移动;
  • 双指针有时也叫快慢指针,在数组里是用两个整型代表下标,在链表里面是两个指针,一般能将O(N^2)的时间复杂度降为O(N);
  • 两个指针的位置一般在第一个元素和第二个元素或者第一个元素和最后一个元素,快指针在前“探路”,当符合某种条件快慢指针向前挪动。
  • 同向双指针,在同向双指针套路中,两个指针朝相同方向移动,但是快慢不同。
  • 反向双指针, 反向双指针中的两个指针反向而行。

11. 盛最多水的容器

https://leetcode.cn/problems/container-with-most-water/description/
在这里插入图片描述

双指针解法

  • 指针每一次移动,都意味着排除掉一根柱子;
  • 如何确定排除哪一根柱子。
    在这里插入图片描述
class Solution:def maxArea(self, height: List[int]) -> int:#双指针"""1、设置两个指针,一个指向起始位置,一个指向末尾,则s = min(h[i],h[j])*(j-i);2、指针向内移动,移动高板,则面积肯定减少;3、移动矮板,面积可能增加4、直至指针相遇,返回面积最大值"""#coding i, j = 0, len(height)-1area = 0ans = 0while i < j:area = min(height[i],height[j]) * (j-i)ans = max(area,ans)if height[i] < height[j]:i += 1else:j -= 1return ans

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/247187.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

初识人工智能,一文读懂机器学习之逻辑回归知识文集(6)

&#x1f3c6;作者简介&#xff0c;普修罗双战士&#xff0c;一直追求不断学习和成长&#xff0c;在技术的道路上持续探索和实践。 &#x1f3c6;多年互联网行业从业经验&#xff0c;历任核心研发工程师&#xff0c;项目技术负责人。 &#x1f389;欢迎 &#x1f44d;点赞✍评论…

深入理解TCP网络协议(1)

目录 1.TCP协议的段格式 2.TCP原理 2.1确认应答 2.2超时重传 3.三次握手(重点) 4.四次挥手 1.TCP协议的段格式 我们先来观察一下TCP协议的段格式图解: 源/目的端口号:标识数据从哪个进程来,到哪个进程去 32位序号/32位确认号:TCP会话的每一端都包含一个32位&#xff08…

linux 的nobody是什么用户? 对安全有没有影响?

目录 一、nobody是不是可疑用户&#xff1f; 二、Linux系统中的nobody用户&#xff1f; 三、有nobody用户存在&#xff0c;安全吗&#xff1f; 一、nobody是不是可疑用户&#xff1f; 在Linux系统中&#xff0c;nobody是一个特殊的用户账户&#xff0c;通常用于运行系统服务…

UE5在VisualStudio升级后产生C++无法编译的问题

往期的虚幻引擎项目在VS更新后&#xff0c;编译时会报错&#xff0c;这一般出现在VS升级之后&#xff0c;UE对于VC的编译器定位没有更新导致&#xff1b; 有出现如下问题&#xff1a; 问题1&#xff1a; Running I:/EPCI/Epic Games/UE_5.3/Engine/Build/BatchFiles/Build.ba…

C++设计模式介绍:优雅编程的艺术

物以类聚 人以群分 文章目录 简介为什么有设计模式&#xff1f; 设计模式七大原则单一职责原则&#xff08;Single Responsibility Principle - SRP&#xff09;开放封闭原则&#xff08;Open/Closed Principle - OCP&#xff09;里氏替换原则&#xff08;Liskov Substitution …

市场复盘总结 20240124

仅用于记录当天的市场情况&#xff0c;用于统计交易策略的适用情况&#xff0c;以便程序回测 短线核心&#xff1a;不参与任何级别的调整&#xff0c;采用龙空龙模式 昨日主题投资 连板进级率 19/43 28.2% 二进三&#xff1a; 进级率低 47% 最常用的二种方法&#xff1a; 方…

【数据结构四】栈与Stack详解

目录 栈与Stack 1.实现一个自己的栈 2.Stack的基本使用 3.栈的一些oj题训练 4.栈&#xff0c;虚拟机栈&#xff0c;栈帧的区别 栈与Stack 栈 &#xff1a;一种特殊的线性表&#xff0c;其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶…

【音视频原理】音频编解码原理 ③ ( 音频 比特率 / 码率 | 音频 帧 / 帧长 | 音频 帧 采样排列方式 - 交错模式 和 非交错模式 )

文章目录 一、音频 比特率 / 码率1、音频 比特率2、音频 比特率 案例3、音频 码率4、音频 码率相关因素5、常见的 音频 码率6、视频码率 - 仅做参考 二、音频 帧 / 帧长1、音频帧2、音频 帧长度 三、音频 帧 采样排列方式 - 交错模式 和 非交错模式1、交错模式2、非交错模式 一…

微信小程序-04

rpx&#xff08;responsive pixel&#xff09;是微信小程序独有的&#xff0c;用来解决屏适配的尺寸单位。 import 后跟需要导入的外联样式表的相对路径&#xff0c;用 ; 表示语句结束。 定义在 app.wxss 中的样式为全局样式&#xff0c;作用于每一个页面。 在页面的 .wxss 文…

薅运营商羊毛?封杀!

最近边小缘在蓝点网上看到一则消息 “浙江联通也开始严格排查PCDN和PT等大流量行为 被检测到可能会封停宽带”。 此前中国联通已经在四川和上海等多个省市严查家庭宽带 (部分企业宽带也被查) 使用 PCDN 或 PT&#xff0c;当用户的宽带账户存在大量上传数据的情况&#xff0c;中…

【USTC】verilog 习题练习 46-50

46 上升沿检测 题目描述 在实际应用中&#xff0c;我们经常需要对某个信号的边沿进行检测&#xff0c;并以此作为后续动作的触发信号&#xff08;例如电脑键盘的某个按键被按下或者被松开&#xff0c;在电路中则对应的是电平的变化&#xff09;。 设计一个电路&#xff0c;包…

幻兽帕鲁服务器价格,这个价格不够电费的

幻兽帕鲁服务器价格多少钱&#xff1f;4核16G服务器Palworld官方推荐配置&#xff0c;阿里云4核16G服务器32元1个月、96元3个月&#xff0c;腾讯云换手帕服务器服务器4核16G14M带宽66元一个月、277元3个月&#xff0c;8核32G22M配置115元1个月、345元3个月&#xff0c;16核64G3…

QT之 QDebug 调试(一)

在QT中&#xff0c;进行调试&#xff0c;则需要在头文件地方加上 #include <QDebug> 加上之后&#xff0c;在编译之后则其输出的信息则在应用程序输出那里显示信息。 其QDebug 信息调试则如&#xff1a; qDebug() << " 需要插入的信息 "…

2000-2022年上市公司全要素生产率测算固定效应FE法(含原始数据+测算代码do文档+计算结果)

2000-2022年上市公司全要素生产率测算固定效应FE法&#xff08;含原始数据测算代码do文档计算结果&#xff09; 1、时间&#xff1a;2000-2022年 2、范围&#xff1a;上市公司 3、指标&#xff1a;证券代码、证券简称、统计截止日期、固定资产净额、year、股票简称、报表类型…

C# RichTextBox常用属性、方法学习1

1 字体 Font font1 new Font("宋体", 18); richTextBox1.Font font1; Font font2 new Font("宋体", 10, FontStyle.Underline); richTextBox1.SelectionFont font2; 定义字体&#xff0c;可以带2个参数&#…

服务端开发小记03——vsftpd

这里写目录标题 vsftpd简介vsftpd在Linux下的安装vsftpd验证vsftpd常用命令 vsftpd简介 vsftpd是“very secure FTP daemon”的缩写&#xff0c;是一个用于Linux环境下的免费开源的ftp服务器软件。vsftpd在Linux发行版中最受推崇&#xff0c;小巧轻快&#xff0c;安全易用&…

(黑马出品_01)SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式

&#xff08;黑马出品_01&#xff09;SpringCloudRabbitMQDockerRedis搜索分布式 微服务技术栈导学 1.认识微服务1.1.学习目标1.2.单体架构1.3.分布式架构1.4.微服务1.5.SpringCloud1.6.总结 2.服务拆分和远程调用2.1.服务拆分原则2.2.服务拆分示…

深度强化学习(王树森)笔记07

深度强化学习&#xff08;DRL&#xff09; 本文是学习笔记&#xff0c;如有侵权&#xff0c;请联系删除。本文在ChatGPT辅助下完成。 参考链接 Deep Reinforcement Learning官方链接&#xff1a;https://github.com/wangshusen/DRL 源代码链接&#xff1a;https://github.c…

内部类 --java学习笔记

内部类 是类中的五大成分之一&#xff08;成员变量、方法、构造器、内部类、代码块&#xff09;&#xff0c;如果一个类定义在另一个类的内部&#xff0c;那么这个类就是内部类当一个类的内部包含了一个整体的事务&#xff0c;且这个事务没必要单独设计时&#xff0c;就可以把…

C51 单片机学习(二):定时器与中断系统

参考 51单片机入门教程 1. 定时器 1.1 定时器定义 51 单片机的定时器属于单片机的内部资源&#xff0c;其电路的连接和运转均在单片机内部完成 C51 单片机学习&#xff08;一&#xff09;&#xff1a;基础外设 讲的都是单片机的 IO 口控制的外设 1.2 定时器作用 用于计时系…