“滑动窗口”算法实例
1 问题
给定一个字符串“S”,找出其中不含有重复字符的最长子串的长度。例如:S=‘ABCABCBB’,则不含重复字符的最长字串长度为3.。S=‘ABCDFG’,则不含重复字符的最长字串长度为6。要求设计一个Python程序实现该功能?
2 方法
按照一般方法,可以采取暴力求解,即把所有不重复的字串全部找出来,再在其中找出最长的字串。可是该方法的时间复杂度和空间复杂度都十分大,面对较长的字符串则会浪费过多时间。
对于该现象,即可使用“滑动窗口”算法。滑动窗口算法也是一种思想,是双指针的拓展和延伸。滑动:指这个窗口是移动的,也就是移动是按照一定方向来的。窗口:窗口大小并不是固定的,可以不断扩容直到满足一定的条件;也可以不断缩小,直到找到一个满足条件的最小窗口;当然也可以是固定大小。
面对前面所提出的问题,使用“滑动窗口”算法,大致思路为:
设置两个指针和一个空列表
固定左指针,不断右移右指针,同时更新最长不重复字符串长度
如果出现重复字符,再右移左指针,如此重复,直到遍历完字符串的所有字符。
最后输出最长不重复字符串长度即可。
这样就降低了问题的复杂度,也降低了循环的嵌套深度。
代码清单 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,表示测试数据的组数࿰…...
微信小程序 纯css画仪表盘
刚看到设计稿的时候第一时间想到的就是用canvas来做这个仪表盘,虽然本人的画布用的不是很好但还可以写一写😀。话不多说直接上代码。最后有纯css方法 <!--wxml--> <canvas canvas-id"circle" class"circle" >// js dat…...
成为AI产品经理——模型稳定性评估(PSI)
一、PSI作用 稳定性是指模型性能的稳定程度。 上线前需要进行模型的稳定性评估,是否达到上线标准。 上线后需要进行模型的稳定性的观测,判断模型是否需要迭代。 稳定度指标(population stability index ,PSI)。通过PSI指标,我们可以获得不…...
操作系统——进程同步
目录 一、信号量相关函数 1. 创建信号量集 2. 获取信号量集 3. 等待、通知信号量集 4. 控制信号量集 二、简单进程同步 1. 创建信号量集 2. P操作 3. V操作 4. 删除信号量集 5. 测试: 三、生产者与消费者 1. 创建、删除共享内存及信号量集 2. 单一生产…...
如何能够对使用ShaderGraph开发的Shader使用SetTextureOffset和SetTextureScale方法
假设在ShaderGraph中的纹理的引用名称为"_BaseMap",同时对这个"_BaseMap"纹理使用了采样的节点"SampleTexture2D",然后该采样节点的uv接入的TilingAndOffset节点,此时的关键步骤是新建一个Vector4属性…...
力扣572:另一棵树的子树
力扣572:另一棵树的子树 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所…...
Linux系统中进程间通信(Inter-Process Communication, IPC)
文章目录 进程间通信介绍进程间通信目的进程间通信发展 管道什么是管道 匿名管道用fork来共享管道原理站在文件描述符角度-深度理解管道站在内核角度-管道本质管道读写规则管道特点 命名管道创建一个命名管道匿名管道与命名管道的区别命名管道的打开规则 命名管道的删除用命名管…...
【React + Typescript】使用WebPack包管理、各种扩展插件组成的初始模板,开源协议:CC-BY-4.0
React Typescript Webpack 模板 模板展示项目结构使用的部分扩展包页面配置代码Layout 公共容器组件路由Jspackage.json 开源模板下载TIP 模板展示 项目结构 使用的部分扩展包 📂 System ├── 📂 Plugin │ ├── 📄 file-loader | 在处…...
python 制作3d立体隐藏图
生成文件的3d图,例子: 文字: 隐藏图: 使用建议: 1、建议不用中文,因为中文太复杂,生成立体图效果不好。 2、需要指定FONT_PATH,为一个ttf文件,…...
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算力,支持INT8/INT4/FP16多精度混合量化。 ● 4路以上1080p30fps视频编解码,IVE模块独立提供图像基础算子加速。 ● 支持Caffe、ONNX/PyTorch深度学习框架,提供resnet50、yolov5等AI算…...
C++作业4
代码整理, 将学过的三种运算符重载,每个至少实现一个运算符的重载 代码: #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 基带调制(编码)方式2.2.2 带通调制方式 2.3 信道的极限速率影响因素2.3.1 **频率范围**2.3.2 **信噪比** 内容笔记来源于谢希任老师《计算机网络》 物理层重点 …...
[STM32-1.点灯大师上线】
学习了江协科技的前4课,除了打开套件的第一秒是开心的,后面的时间都是在骂娘。因为51的基础已经几乎忘干净,c语言已经还给谭浩强,模电数电还有点底子,硬着头皮上吧。 本篇主要是讲述学习点灯的过程和疑惑解释。 1.工…...
Web测试自动化工具Selenium的使用
Web测试自动化工具Selenium的使用 Selenium是一个Web应用测试的自动化工具,它通过模拟点击实现对Web应用的功能测试。测试时,除了Selenium,还需要对应的浏览器驱动,如在Chrome实现自动点击,则需要chromedriver。 Sel…...
VUE2+THREE.JS 按照行动轨迹移动人物模型并相机视角跟随人物
按照行动轨迹移动人物模型并相机视角跟随人物 1. 初始化加载模型2. 开始移动模型3. 人物模型启动4. 暂停模型移动5. 重置模型位置6. 切换区域动画7. 摄像机追踪模型8. 移动模型位置9.动画执行 人物按照上一篇博客所设定的关键点位置,匀速移动 1. 初始化加载模型 //…...
Hadoop YARN组件
1. 请解释Yarn的基本架构和工作原理。 YARN,也被称为"Yet Another Resource Negotiator",是Apache HadoopYARN,也被称为"Yet Another Resource Negotiator",是Apache Hadoop的一部分,它被设计为一…...
Java架构师技术架构路线
目录 1 概论2 如何规划短中长期的技术架构路线图3 如何规划面向未来的架构4 如何修订路线图执行过程中的偏差5 如何落地路线图-阿里系糙快猛之下的敏捷模式想学习架构师构建流程请跳转:Java架构师系统架构设计 1 概论 首先,规划一个短中长期的技术路线图是非常重要的。短中…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10pip3.10) 一:前言二:安装编译依赖二:安装Python3.10三:安装PIP3.10四:安装Paddlepaddle基础框架4.1…...
02-性能方案设计
需求分析与测试设计 根据具体的性能测试需求,确定测试类型,以及压测的模块(web/mysql/redis/系统整体)前期要与相关人员充分沟通,初步确定压测方案及具体的性能指标QA完成性能测试设计后,需产出测试方案文档发送邮件到项目组&…...
【Vue】scoped+组件通信+props校验
【scoped作用及原理】 【作用】 默认写在组件中style的样式会全局生效, 因此很容易造成多个组件之间的样式冲突问题 故而可以给组件加上scoped 属性, 令样式只作用于当前组件的标签 作用:防止不同vue组件样式污染 【原理】 给组件加上scoped 属性后…...
Centos 7 服务器部署多网站
一、准备工作 安装 Apache bash sudo yum install httpd -y sudo systemctl start httpd sudo systemctl enable httpd创建网站目录 假设部署 2 个网站,目录结构如下: bash sudo mkdir -p /var/www/site1/html sudo mkdir -p /var/www/site2/html添加测试…...
关于疲劳分析的各种方法
疲劳寿命预测方法很多。按疲劳裂纹形成寿命预测的基本假定和控制参数,可分为名义应力法、局部应力一应变法、能量法、场强法等。 1名义应力法 名义应力法是以结构的名义应力为试验和寿命估算的基础,采用雨流法取出一个个相互独立、互不相关的应力循环&…...
XXE漏洞知识
目录 1.XXE简介与危害 XML概念 XML与HTML的区别 1.pom.xml 主要作用 2.web.xml 3.mybatis 2.XXE概念与危害 案例:文件读取(需要Apache >5.4版本) 案例:内网探测(鸡肋) 案例:执行命…...
CCF 开源发展委员会 “开源高校行“ 暨红山开源 + OpenAtom openKylin 高校行活动在西安四所高校成功举办
点击蓝字 关注我们 CCF Opensource Development Committee CCF开源高校行 暨红山开源 openKylin 高校行 西安站 5 月 26 日至 28 日,CCF 开源发展委员会 "开源高校行" 暨红山开源 OpenAtom openKylin 高校行活动在西安四所高校(西安交通大学…...
可视化图解算法48:有效括号序列
牛客网 面试笔试 TOP101 | LeetCode 20. 有效的括号 1. 题目 描述 给出一个仅包含字符(,),{,},[和],的字符串,判断给出的字符串是否是合法的括号序列 括号必须以正确的顺序关闭,"()"和"()[]{}"都是合法的括号序列&…...
