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

LeetCode 热题 100——无重复字符的最长子串(滑动窗口)

题目链接

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目解析

从s字符串中,去找出连续的子串,使该子串中没有重复字符,返回它的最长长度。

暴力枚举

依次以第一个、第二个、第三个等等为起点去遍历字符串,并且找出不连续子串的最大长度。我们可以借助哈希来解决不重复这个操作。

代码如下

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int n=s.size();int ret = 0;for(int i=0;i<n;i++){// 每次换遍历起点的时候都重新创建一个新的哈希表int hash[128]={0};for(int j=i;j<n;j++){// 将该遍历字符插入哈希表hash[s[j]]++;// 如果该位置字符的次数>1 则存在重复元素 直接跳出if(hash[s[j]]>1)break;// 计算最大长度ret=max(ret,j-i+1);}}return ret;}
};

滑动窗口

暴力枚举的缺点

从我们暴力枚举画图的过程中我们能发现一个事情。如图所示:

注意五角星的位置,我们能发现当我们依次去使用第二个字符为起点的时候,依然是遍历到了此位置,那么是为什么呢?

原因是我们原字符串中的a并没有移走,因此,我们就算以第二个字符作为起点,等到遍历到第二个a的时候依然是重复的,那么我们能不能遍历的时候先把重复的元素给移除掉,然后再进行遍历呢?

那么我们就引出了我们的滑动窗口操作。 

滑动窗口步骤

我们滑动窗口分为几个简单的步骤:

1.定义两个边界的变量 -- left=0,right=0

2.进窗口 -- 让字符进入哈希表
3.判断 -- 窗口内出现重复字符
  出窗口 -- 从哈希表中删除该字符

4.更新结果

图解

代码如下:

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int hash[128]={0};int n=s.size();int ret =0 ;for(int left=0,right=0;right<n;right++){hash[s[right]]++;while(hash[s[right]]>1)hash[s[left++]]--;ret=max(right-left+1,ret);}return ret;}
};

相关文章:

LeetCode 热题 100——无重复字符的最长子串(滑动窗口)

题目链接 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 题目解析 从s字符串中&#xff0c;去找出连续的子串&#xff0c;使该子串中没有重复字符&#xff0c;返回它的最长长度。 暴力枚举 依次以第一个、第二个、第三个等等为起点去遍历字符串&a…...

【zookeeper】zookeeper的shell操作

Zookeeper的shell操作 本章节将分享一些zookeeper客服端的一些命令&#xff0c;实验操作有助于理解zookeeper的数据结构。 Zookeeper命令工具 在前一章的基础上&#xff0c;在启动Zookeeper服务之后&#xff0c;输入以下命令&#xff0c;连接到Zookeeper服务。连接成功之后&…...

R语言Meta分析核心技术

Meta分析是针对某一科研问题&#xff0c;根据明确的搜索策略、选择筛选文献标准、采用严格的评价方法&#xff0c;对来源不同的研究成果进行收集、合并及定量统计分析的方法&#xff0c;最早出现于“循证医学”&#xff0c;现已广泛应用于农林生态&#xff0c;资源环境等方面。…...

Oracle数据库尚硅谷学习笔记

文章目录 Oracle数据库体系结构简介补充SQL初步导入sql文件别名连接符distinct去重的坑 过滤和排序数据日期格式比较运算其它比较运算符逻辑运算优先级排序 单行函数SQL中不同类型的函数单行函数字符数值日期转换通用 使用条件表达式嵌套查询 多表查询等值连接非等值连接左外连…...

CG MAGIC进行实体渲染后!分析渲染器CR和VR的区别之处!

新手小白来说&#xff0c;如何选择渲染器&#xff0c;都会提出疑问&#xff1f; 渲染效果图究竟用CR渲染器还是VR渲染器呢&#xff1f; 今天&#xff0c;CG MAGIC小编通过一个真实的项目场景&#xff0c;实例渲染之后&#xff0c;CR渲染器和VR渲染器区别有哪几点&#xff1f; 1…...

Ubuntu下Python3与Python2相互切换

参考文章&#xff1a;https://blog.csdn.net/Nicolas_shen/article/details/124144931 设置优先级 sudo update-alternatives --install /usr/bin/python python /usr/bin/python2 100 sudo update-alternatives --install /usr/bin/python python /usr/bin/python3 200...

【深度学习】实验07 使用TensorFlow完成逻辑回归

文章目录 使用TensorFlow完成逻辑回归1. 环境设定2. 数据读取3. 准备好placeholder4. 准备好参数/权重5. 计算多分类softmax的loss function6. 准备好optimizer7. 在session里执行graph里定义的运算 附&#xff1a;系列文章 使用TensorFlow完成逻辑回归 TensorFlow是一种开源的…...

2023-09-04 Linux 让shell编译脚本里面设置的环境变量改变kernel里面驱动文件的宏定义值方法,我这里用来做修改固件版本

一、原生的读取版本接口是/proc/version&#xff0c;我这里需要提供获取固件版本号的api给app&#xff0c;因为版本号会经常需要修改&#xff0c;如果每次都到kernel下修改比较麻烦&#xff0c;我这里是想在编译脚本里面对版本号进行修改&#xff0c;这样方便一点。 二、主要修…...

Python操作Excel实战:Excel行转列

# 1、原始数据准备 样例数据准备 地区1m2-5m6-10m11-20m21-40m地区单价计费单位费用最小值费用最大值北京13012011010090     天津13012011010090     石家庄13012011010090     保定140130120110100     张家口170150130120110     邢台1401201101…...

java实现迭代器模式

迭代器模式&#xff08;Iterator Pattern&#xff09;是一种行为型设计模式&#xff0c;它提供一种方法来顺序访问一个聚合对象&#xff08;如列表、集合、数组等&#xff09;中的元素&#xff0c;而不暴露聚合对象的内部表示。迭代器模式通常包括以下角色&#xff1a;迭代器&a…...

C++day7模板、异常、auto关键字、lambda表达式、数据类型转换、STL、list、文件操作

作业 封装一个学生的类&#xff0c;定义一个学生这样类的vector容器, 里面存放学生对象&#xff08;至少3个&#xff09; 再把该容器中的对象&#xff0c;保存到文件中。 再把这些学生从文件中读取出来&#xff0c;放入另一个容器中并且遍历输出该容器里的学生。 #include …...

【校招VIP】产品分析之活动策划宣传

考点介绍&#xff1a; 产品的上线运营是非常重要的。应该来说好的产品都是运营出来的&#xff0c;在一运营过程中难免会依靠策划活动来提高产品知名度、用户数。用户粘度等等指标一&#xff0c;如何策划一个成功的活动就显得非常重要。 产品分析之活动策划宣传-相关题目及解析…...

node基础之一:fs 模块

概念&#xff1a;文件的创建、删除、重命名、移动、写入、读取等 const fs require("fs");// 写入 fs.writeFile("./demo.txt", "hello", (err) > {}); fs.writeFileSync();// 追加 fs.appendFile("./demo.txt", "hello&quo…...

如何快速搭建母婴行业的微信小程序?

如果你想为你的母婴行业打造一个独特的小程序&#xff0c;但没有任何编程经验&#xff0c;别担心&#xff01;现在有许多小程序制作平台提供了简单易用的工具&#xff0c;让你可以轻松地建立自己的小程序。接下来&#xff0c;我将为你详细介绍搭建母婴行业小程序的步骤。 首先&…...

【科普向】Jmeter 如何测试接口保姆式教程

现在对测试人员的要求越来越高&#xff0c;不仅仅要做好功能测试&#xff0c;对接口测试的需求也越来越多&#xff01;所以也越来越多的同学问&#xff0c;怎样才能做好接口测试&#xff1f; 要真正的做好接口测试&#xff0c;并且弄懂如何测试接口&#xff0c;需要从如下几个…...

阿里云2核4G服务器5M带宽5年费用价格明细表

阿里云2核4G服务器5M带宽可以选择轻量应用服务器或云服务器ECS&#xff0c;轻量2核4G4M带宽服务器297元一年&#xff0c;2核4G云服务器ECS可以选择计算型c7、c6或通用算力型u1实例等&#xff0c;买5年可以享受3折优惠&#xff0c;阿腾云分享阿里云服务器2核4G5M带宽五年费用表&…...

【图解RabbitMQ-2】图解JMS规范与AMQP协议是什么

&#x1f9d1;‍&#x1f4bb;作者名称&#xff1a;DaenCode &#x1f3a4;作者简介&#xff1a;CSDN实力新星&#xff0c;后端开发两年经验&#xff0c;曾担任甲方技术代表&#xff0c;业余独自创办智源恩创网络科技工作室。会点点Java相关技术栈、帆软报表、低代码平台快速开…...

springboot整合mybatis实现增删改查(xml)--项目阶段1

目录 一、前言 二、创建项目 创建MySQL数据库和表 创建springboot项目 本文总体代码结构图预览 三、编写代码 &#xff08;一&#xff09;新建实体层属性类 &#xff08;二&#xff09;新建数据层mapper接口 &#xff08;三&#xff09;新建mapper的映射SQL&#xff08…...

springboot文件上传异步报错

因为迁移的生产环境&#xff0c;在新的服务器发生了之前没有遇到的问题&#xff0c;这种问题是在异步文件上传的时候才会出现 错误信息如下 16:17:50.009 ERROR c.w.einv.minio.service.impl.MinioFileServiceImpl - 文件上传错误! java.io.FileNotFoundException: /applicati…...

error: unable to unlink old ‘.gitlab-ci.yml‘: Permission denied

#gitlab-runner 执行代码git pull origin xxx 更新时候报 error: unable to unlink old ‘.gitlab-ci.yml’: Permission denied 问题环境&#xff1a;centos 部署gitlab-runner 执行脚本方式 选的shell 产生问题的原因&#xff1a;gitlab-runner程序进程占用锁定了.gitlab-ci…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...