模块二——滑动窗口:3.无重复字符的最长子串

文章目录

  • 题目描述
  • 算法原理
    • 解法⼀:暴⼒求解(不会超时,可以通过)
    • 解法二:滑动窗口
  • 代码实现
    • 解法⼀:暴⼒求解(时间复杂度为O(N^2^),空间复杂度为O(1))
    • 解法二:滑动窗口(时间复杂度为O(N),空间复杂度为O(1))

题目描述

题目链接:3.无重复字符的最长子串
在这里插入图片描述

算法原理

解法⼀:暴⼒求解(不会超时,可以通过)

枚举从每⼀个位置开始往后,⽆重复字符的⼦串可以到达什么位置。找出其中⻓度最⼤的即可。
在往后寻找⽆重复⼦串能到达的位置时,可以利⽤哈希表统计出字符出现的频次,来判断什么时候⼦串出现了重复元素。

解法二:滑动窗口

研究的对象依旧是⼀段连续的区间,因此继续使⽤滑动窗⼝思想来优化。
让滑动窗⼝满⾜:窗⼝内所有元素都是不重复的。
做法:右端元素ch进⼊窗⼝的时候,哈希表统计这个字符的频次:

  • 如果这个字符出现的频次超过1 ,说明窗⼝内有重复元素,那么就从左侧开始划出窗⼝,直到ch 这个元素的频次变为1 ,然后再更新结果。
  • 如果没有超过1 ,说明当前窗⼝没有重复元素,可以直接更新结果。

代码实现

解法⼀:暴⼒求解(时间复杂度为O(N2),空间复杂度为O(1))

class Solution {
public:int lengthOfLongestSubstring(string s) {int res = 0;//记录结果for(int left = 0;left < s.size();left++){int hash[128] = { 0 };//记录每个字母的出现次数for(int right = left;right < s.size();right++){hash[s[right]]++;if( hash[s[right]] > 1){break;}res = max(res,right - left + 1);}}return res;}
};

解法二:滑动窗口(时间复杂度为O(N),空间复杂度为O(1))

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = { 0 };//记录每个字母的出现次数int res = 0;//记录结果for(int left = 0,right = 0;right < s.size();right++)//1.控制窗口的左右指针{hash[s[right]]++;//2.进窗口while(hash[s[right]] == 2)//3.判断{//出窗口hash[s[left]]--;left++;}res = max(res,right - left + 1);}return res;}
};

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

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

相关文章

LeetCode-合并有序链表问题

合并两个有序链表 题目描述&#xff1a; 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路&#xff1a; 首先建立一个头节点方便后续操作&#xff0c;然后开始循环将两个链表的节点值进行比较&#xff0c;如果list1节…

hbuiler中使用npm安装datav

注&#xff1a;datav边框样式目前使用时&#xff1a;适用于网页&#xff0c;不适用于app 1、先安装node 安装、配置Node路径 2、为Node配置环境变量 3、在hbuilder的设置中填写node的路径 配置 4、打开cmd输入npm install jiaminghi/data-view 安装dataV&#xff0c;&…

MicroSD 卡 使用读卡器 读取速度测试

设备 - - 电脑为m.2固态硬盘 usb口为USB3.2 gen2接口(即支持1GB/s的接口) cpu: amd3600 测试方案1 直接MicroSD卡放入读卡器测试 38MB/s 从sd卡复制到本地C盘 测试方案2 MicroSD卡使用闪迪的SD卡套套上之后一起插入读卡器 76MB/s 从sd卡复制到本地C盘

uni-app应用设置 可以根据手机屏幕旋转进行 (横/竖) 屏切换

首先 我们打开项目的 manifest.json 在左侧导航栏中找到 源码视图 然后找到 app-plus 配置 在下面加上 "orientation": [//竖屏正方向"portrait-primary",//竖屏反方向"portrait-secondary",//横屏正方向"landscape-primary",//横屏…

Mybatis核心配置文件加载流程详解

Mybatis核心配置文件加载流程详解 本文将介绍MyBatis在配置文件加载的过程中&#xff0c;如何加载核心配置文件、如何解析映射文件中的SQL语句以及每条SQL语句如何与映射接口的方法进行关联。 映射配置文件 在介绍核心配置文件加载流程前&#xff0c;先给出一个简单的MyBati…

ROS gazebo 机器人仿真,环境与robot建模,添加相机 lidar,控制robot运动

b站上有一个非常好的ros教程234仿真之URDF_link标签简介-机器人系统仿真_哔哩哔哩_bilibili&#xff0c;推荐去看原视频。 视频教程的相关文档见&#xff1a;6.7.1 机器人运动控制以及里程计信息显示 Autolabor-ROS机器人入门课程《ROS理论与实践》零基础教程 本文对视频教程…

Docker入门指南:从基础到实践

在当今软件开发领域&#xff0c;Docker已经成为一种不可或缺的工具。通过将应用程序及其依赖项打包成轻量级的容器&#xff0c;Docker实现了开发、测试和部署的高度一致性。本文将深入研究Docker的基本概念&#xff0c;并通过详细的示例代码演示如何应用这些概念于实际场景中。…

基于FPGA的视频接口之高速IO(光纤)

简介 对于高速IO口配置光纤,现在目前大部分开发板都有配置,且也有说明,在此根据自己的工作经验以及对于各开发板的说明归纳 通过高速IO接口,以及硬件配置,可以实现对于光纤的收发功能,由于GTX的速率在500Mbs到10Gbps之间,但通道高速io可配置光纤10G硬件,物理通完成,则…

掌握 Python sympy 库的高级计算技巧

更多资料获取 &#x1f4da; 个人网站&#xff1a;ipengtao.com Sympy是Python中一个强大的符号计算库&#xff0c;为数学和科学计算提供了丰富的功能。本文将深入介绍Sympy库的各项功能&#xff0c;并提供丰富的示例代码&#xff0c;以帮助大家更好地理解和应用这一工具。 S…

【论文精读】REACT: SYNERGIZING REASONING AND ACTING IN LANGUAGE MODELS

REACT: SYNERGIZING REASONING AND ACTING IN LANGUAGE MODELS 前言ABSTRACT1 INTRODUCTION2 REACT: SYNERGIZING REASONING ACTING3 KNOWLEDGE-INTENSIVE REASONING TASKS3.1 SETUP3.2 METHODS3.3 RESULTS AND OBSERVATIONS 4 DECISION MAKING TASKS5 RELATED WORK6 CONCLUSI…

SpringBoot整合ActiveMQ

SpringBoot整合ActiveMQ 文章目录 SpringBoot整合ActiveMQ下载与安装SpringBoot整合ActiveMQ导坐标改配置&#xff0c;默认的保存位置生产与消费消息实现监听类——实现消息自动消费监听器转发消息&#xff1a;流程性业务消息消费完转入下一个消息队列 下载与安装 https://act…

8、操作符重载

友元 可以通过friend关键字&#xff0c;把一个全局函数、另一个类的成员函数或者另一个类整体&#xff0c;声明为授权类的友元友元拥有访问授权类任何非公有成员的特权友元声明可以出现在授权类的公有、私有或者保护等任何区域且不受访问控制限定符的约束友元不是成员&#xf…

Qt + MySQL(简单的增删改查)

Qt编译MySql插件教程 帮助&#xff1a; SQL Programming QSqlDatabase 静态函数 1.drivers()&#xff0c;得到可以使用的数据库驱动名字的集合 [static] QStringList QSqlDatabase::drivers();2.addDatabase()&#xff0c;添加一个数据库实例 [static] QSqlDatabase QSql…

慢SQL诊断

最近经常遇到技术开发跑来问我慢SQL优化相关工作&#xff0c;所以干脆出几篇SQL相关优化技术月报&#xff0c;我这里就以公司mysql一致的5.7版本来说明下。 在企业中慢SQL问题进场会遇到&#xff0c;尤其像我们这种ERP行业。 成熟的公司企业都会有晚上的慢SQL监控和预警机制。…

Logstash输入Kafka输出Es配置

Logstash介绍 Logstash是一个开源的数据收集引擎&#xff0c;具有实时管道功能。它可以从各种数据源中动态地统一和标准化数据&#xff0c;并将其发送到你选择的目的地。Logstash的早期目标主要是用于收集日志&#xff0c;但现在的功能已经远远超出这个范围。任何事件类型都可…

FastAPI之响应模型

前言 响应模型我认为最主要的作用就是在自动化文档的显示时&#xff0c;可以直接给查看文档的小伙伴显示返回的数据格式。对于后端开发的伙伴来说&#xff0c;其编码的实际意义不大&#xff0c;但是为了可以不用再额外的提供文档&#xff0c;我们只需要添加一个 response_mod…

汽车服务行业分析:预计2028年将达到38亿元

在推进加快检验机构建设同时&#xff0c;综合评估检验机构数量、分布和检测能力&#xff0c;探索试点汽车 4S 店开展检验&#xff0c;提供维修、保养、车检一体化服务。汽车服务主要是指围绕汽车展开的一系列服务活动&#xff0c;包括维修、美容、金融等&#xff0c;除具有一般…

springboot3 liquibase SQL执行失败自动回滚,及自动打tag

一&#xff1a; 自动执行回滚&#xff0c; 已执行成功的忽略&#xff0c;新sql执行失败则执行新sql文件中的回滚sql pom.xml <dependency> <groupId>org.liquibase</groupId> <artifactId>liquibase-core</artifactId> <version>4.25.0&…

Appium 并行测试多个设备

一、前置说明 在自动化测试中&#xff0c;经常需要验证多台设备的兼容性&#xff0c;Appium可以用同一套测试运例并行测试多个设备&#xff0c;以达到验证兼容性的目的。 解决思路&#xff1a; 查找已连接的所有设备&#xff1b;为每台设备启动相应的Appium Server&#xff1b…

从手工测试进阶中高级测试?如何突破职业瓶颈...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、手工测试如何进…