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

“滑动窗口”算法实例

1 问题

给定一个字符串“S”,找出其中不含有重复字符的最长子串的长度。例如:S=‘ABCABCBB’,则不含重复字符的最长字串长度为3.。S=‘ABCDFG’,则不含重复字符的最长字串长度为6。要求设计一个Python程序实现该功能?

2 方法

按照一般方法,可以采取暴力求解,即把所有不重复的字串全部找出来,再在其中找出最长的字串。可是该方法的时间复杂度和空间复杂度都十分大,面对较长的字符串则会浪费过多时间。

对于该现象,即可使用“滑动窗口”算法。滑动窗口算法也是一种思想,是双指针的拓展和延伸。滑动:指这个窗口是移动的,也就是移动是按照一定方向来的。窗口:窗口大小并不是固定的,可以不断扩容直到满足一定的条件;也可以不断缩小,直到找到一个满足条件的最小窗口;当然也可以是固定大小。

面对前面所提出的问题,使用“滑动窗口”算法,大致思路为:

  1. 设置两个指针和一个空列表

  2. 固定左指针,不断右移右指针,同时更新最长不重复字符串长度

  3. 如果出现重复字符,再右移左指针,如此重复,直到遍历完字符串的所有字符。

    最后输出最长不重复字符串长度即可。

这样就降低了问题的复杂度,也降低了循环的嵌套深度。

代码清单 1

'''
通过固定左端元素,再右端元素不断右移,算出左端和右端间的总数
然后左端再不断右移,不断计算之间的总数。最后算出最长长度
'''
s = input() # 输入字符串
max_length =float('-inf') # 定义一个初指为负无穷
start = 0 # 定义左指针为0
l = list() # 定义一个空列表,用于是否重复的判断
for end in range(len(s)): # 右指针通过for循环,逐步向右移动
   while s[end] in l: # 当右指针移到某个值时,且该值已经在前面出现过
       l.remove(s[start]) # 移除左指针对应的重复值
       start += 1 # 并且将左指针向右移动一个单位
   max_length = max(max_length, end-start+1) # 每次右指针移动后,统计不重复的字符串的最长长度
   l.append(s[end]) # 将右指针每次遍历过的值加入列表中,用于重复判断
if max_length == float('-inf'): # 如果最大值对于负无穷,则代表无最长不重复字符串
   print('0')
else:
   print(max_length) # 打印最大不重复字符串长度
'''
测试结果:
abcabcbb 输出:3
aaaaaaaa 输出:1
'''

3 结语

通过测试,发现“滑动窗口”算法可以很好的解决该问题,与此同时,相对于暴力求解,其时间复杂度和空间复杂度也得到了优化。总结发现,一般给出的数据结构是数组或者字符串,且求取某个子串或者子序列最长最短等最值问题或者求某个目标值时。都可以使用“滑动窗口”算法。

相关文章:

“滑动窗口”算法实例

1 问题 给定一个字符串“S”,找出其中不含有重复字符的最长子串的长度。例如:S‘ABCABCBB’,则不含重复字符的最长字串长度为3.。S‘ABCDFG’,则不含重复字符的最长字串长度为6。要求设计一个Python程序实现该功能? 2 方法 按照一…...

分布式搜索引擎elasticsearch(一)

5.1 初始elasticsearch elasticsearch是一款非常强大的开源搜索引擎,可以帮助我们从海量数据中快速找到需要的内容。 elasticsearch是elastic stack的核心,负责存储、搜索、分析数据。 5.1.1正向索引 5.1.2elasticsearch采用倒排索引: 文档(document):每条数据就是一个…...

PTA 7-236 验证哥德巴赫猜想

哥德巴赫猜想之一是指一个偶数(2除外)可以拆分为两个素数之和。请验证这个猜想。 因为同一个偶数可能可以拆分为不同的素数对之和,这里要求结果素数对彼此最接近。 输入格式: 首先输入一个正整数T,表示测试数据的组数&#xff0…...

微信小程序 纯css画仪表盘

刚看到设计稿的时候第一时间想到的就是用canvas来做这个仪表盘&#xff0c;虽然本人的画布用的不是很好但还可以写一写&#x1f600;。话不多说直接上代码。最后有纯css方法 <!--wxml--> <canvas canvas-id"circle" class"circle" >// js dat…...

成为AI产品经理——模型稳定性评估(PSI)

一、PSI作用 稳定性是指模型性能的稳定程度。 上线前需要进行模型的稳定性评估&#xff0c;是否达到上线标准。 上线后需要进行模型的稳定性的观测&#xff0c;判断模型是否需要迭代。 稳定度指标(population stability index ,PSI)。通过PSI指标&#xff0c;我们可以获得不…...

操作系统——进程同步

目录 一、信号量相关函数 1. 创建信号量集 2. 获取信号量集 3. 等待、通知信号量集 4. 控制信号量集 二、简单进程同步 1. 创建信号量集 2. P操作 3. V操作 4. 删除信号量集 5. 测试&#xff1a; 三、生产者与消费者 1. 创建、删除共享内存及信号量集 2. 单一生产…...

如何能够对使用ShaderGraph开发的Shader使用SetTextureOffset和SetTextureScale方法

假设在ShaderGraph中的纹理的引用名称为"_BaseMap"&#xff0c;同时对这个"_BaseMap"纹理使用了采样的节点"SampleTexture2D"&#xff0c;然后该采样节点的uv接入的TilingAndOffset节点&#xff0c;此时的关键步骤是新建一个Vector4属性&#xf…...

力扣572:另一棵树的子树

力扣572&#xff1a;另一棵树的子树 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所…...

Linux系统中进程间通信(Inter-Process Communication, IPC)

文章目录 进程间通信介绍进程间通信目的进程间通信发展 管道什么是管道 匿名管道用fork来共享管道原理站在文件描述符角度-深度理解管道站在内核角度-管道本质管道读写规则管道特点 命名管道创建一个命名管道匿名管道与命名管道的区别命名管道的打开规则 命名管道的删除用命名管…...

【React + Typescript】使用WebPack包管理、各种扩展插件组成的初始模板,开源协议:CC-BY-4.0

React Typescript Webpack 模板 模板展示项目结构使用的部分扩展包页面配置代码Layout 公共容器组件路由Jspackage.json 开源模板下载TIP 模板展示 项目结构 使用的部分扩展包 &#x1f4c2; System ├── &#x1f4c2; Plugin │ ├── &#x1f4c4; file-loader | 在处…...

python 制作3d立体隐藏图

生成文件的3d图&#xff0c;例子&#xff1a; 文字&#xff1a; 隐藏图&#xff1a; 使用建议&#xff1a; &#xff11;、建议不用中文&#xff0c;因为中文太复杂&#xff0c;生成立体图效果不好。 &#xff12;、需要指定FONT_PATH&#xff0c;为一个ttf文件&#xff0c;…...

layui+ssm实现数据批量删除

layuissm实现数据的批量删除 //数据表格table.render({id: adminList,elem: #adminList,url: ctx "/admin/getAdminList", //数据接口cellMinWidth: 80,even: true,toolbar: #toolbarDemo,//头部工具栏limit: 10,//每页条数limits: [10, 20, 30, 40],defaultToolba…...

国产AI边缘计算盒子,双核心A55丨2.5Tops算力

边缘计算盒子 双核心A55丨2.5Tops算力 ● 2.5TopsINT8算力&#xff0c;支持INT8/INT4/FP16多精度混合量化。 ● 4路以上1080p30fps视频编解码&#xff0c;IVE模块独立提供图像基础算子加速。 ● 支持Caffe、ONNX/PyTorch深度学习框架&#xff0c;提供resnet50、yolov5等AI算…...

C++作业4

代码整理&#xff0c; 将学过的三种运算符重载&#xff0c;每个至少实现一个运算符的重载 代码&#xff1a; #include <iostream>using namespace std;class Stu {friend const Stu operator*(const Stu &L,const Stu &R);friend bool operator<(const Stu …...

计算机网络(二)| 物理层上 | 数据通信基础知识 调制 频率范围 信噪比

文章目录 1 物理层基本概念2.数据通信基础知识2.1 数据通信基本概念2.2 信道基本概念2.2.1 基带调制&#xff08;编码&#xff09;方式2.2.2 带通调制方式 2.3 信道的极限速率影响因素2.3.1 **频率范围**2.3.2 **信噪比** 内容笔记来源于谢希任老师《计算机网络》 物理层重点 …...

[STM32-1.点灯大师上线】

学习了江协科技的前4课&#xff0c;除了打开套件的第一秒是开心的&#xff0c;后面的时间都是在骂娘。因为51的基础已经几乎忘干净&#xff0c;c语言已经还给谭浩强&#xff0c;模电数电还有点底子&#xff0c;硬着头皮上吧。 本篇主要是讲述学习点灯的过程和疑惑解释。 1.工…...

Web测试自动化工具Selenium的使用

Web测试自动化工具Selenium的使用 Selenium是一个Web应用测试的自动化工具&#xff0c;它通过模拟点击实现对Web应用的功能测试。测试时&#xff0c;除了Selenium&#xff0c;还需要对应的浏览器驱动&#xff0c;如在Chrome实现自动点击&#xff0c;则需要chromedriver。 Sel…...

VUE2+THREE.JS 按照行动轨迹移动人物模型并相机视角跟随人物

按照行动轨迹移动人物模型并相机视角跟随人物 1. 初始化加载模型2. 开始移动模型3. 人物模型启动4. 暂停模型移动5. 重置模型位置6. 切换区域动画7. 摄像机追踪模型8. 移动模型位置9.动画执行 人物按照上一篇博客所设定的关键点位置&#xff0c;匀速移动 1. 初始化加载模型 //…...

Hadoop YARN组件

1. 请解释Yarn的基本架构和工作原理。 YARN&#xff0c;也被称为"Yet Another Resource Negotiator"&#xff0c;是Apache HadoopYARN&#xff0c;也被称为"Yet Another Resource Negotiator"&#xff0c;是Apache Hadoop的一部分&#xff0c;它被设计为一…...

Java架构师技术架构路线

目录 1 概论2 如何规划短中长期的技术架构路线图3 如何规划面向未来的架构4 如何修订路线图执行过程中的偏差5 如何落地路线图-阿里系糙快猛之下的敏捷模式想学习架构师构建流程请跳转:Java架构师系统架构设计 1 概论 首先,规划一个短中长期的技术路线图是非常重要的。短中…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

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

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

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...