“滑动窗口”算法实例
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 概论 首先,规划一个短中长期的技术路线图是非常重要的。短中…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...
ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...
路由基础-路由表
本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中,往往存在多个不同的IP网段,数据在不同的IP网段之间交互是需要借助三层设备的,这些设备具备路由能力,能够实现数据的跨网段转发。 路由是数据通信网络中最基…...
C#最佳实践:为何优先使用as或is而非强制转换
C#最佳实践:为何优先使用as或is而非强制转换 在 C# 的编程世界里,类型转换是我们经常会遇到的操作。就像在现实生活中,我们可能需要把不同形状的物品重新整理归类一样,在代码里,我们也常常需要将一个数据类型转换为另…...
Vue3学习(接口,泛型,自定义类型,v-for,props)
一,前言 继续学习 二,TS接口泛型自定义类型 1.接口 TypeScript 接口(Interface)是一种定义对象形状的强大工具,它可以描述对象必须包含的属性、方法和它们的类型。接口不会被编译成 JavaScript 代码,仅…...
