当前位置: 首页 > 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…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

Java并发编程实战 Day 11:并发设计模式

【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天&#xff0c;今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案&#xff0c;它们不仅提供了优雅的设计思路&#xff0c;还能显著提升系统的性能…...

Canal环境搭建并实现和ES数据同步

作者&#xff1a;田超凡 日期&#xff1a;2025年6月7日 Canal安装&#xff0c;启动端口11111、8082&#xff1a; 安装canal-deployer服务端&#xff1a; https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...