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

[python 刷题] 3 Longest Substring Without Repeating Characters

[python 刷题] 3 Longest Substring Without Repeating Characters

题目:

Given a string s, find the length of the longest substring without repeating characters.

这到提要求找的是最长的,没有重复符号的子字符串

解题思路是用双指针+哈希表,左右指针指向子字符串的开始和结束的位置,哈希表存储每个字符串最后出现的下标+1,每次更新右侧指针时,如果当前字符是已经出现的字符,则将左指针移向最后出现的位置

最后更新一下最长子字符串的长度,按照案例过一遍:

开局的时候 dict 是空的,左右指针同时指向空

遇到没重复的字符串, r r r 指向下一个字符

在这里插入图片描述

b, c 没有遇到重复字符,所以持续更新 dict 和右侧指针位置:

在这里插入图片描述

这里存储的所有位置都是下标+1,主要是为了针对只出现 1 个字符的案例,如 " ",如果只是用 r − l r - l rl,得出的结果就是 0 − 0 0 - 0 00,所以针对这个情况,所有存储的位置都是下标+1,计算字符串长度时也用 r − l + 1 r - l + 1 rl+1 的方式补回

遇到了第二个 a:

在这里插入图片描述

这个时候左侧的指针从 0 移到了 1,res 的对比成了 res 3 − 1 + 1 3 - 1 + 1 31+1 的对比,自然长度还是一样的

这个时候同步更新 a 最后出现的坐标位置,移到下一个字符:

在这里插入图片描述

我标了一下,取值永远取的是 r r r l l l 之间的这个字符串长度

另外关于 l l l 的取值也需要做一点额外的对比,如考虑下面这个情况:

在这里插入图片描述

如果取 b b b 之前所在的下标位置,依旧会取到包含重复字符的字符串,因此需要取当前 l l l 和 当前字符上一个下标中的最大值

代码如下:

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:# use d to store the last appearance idxd = {}l, res = 0, 0for r, c in enumerate(s):l = max(l, d.get(c, 0))res = max(res, r - l + 1)print(res, l, r, c)d[c] = r + 1return res

相关文章:

[python 刷题] 3 Longest Substring Without Repeating Characters

[python 刷题] 3 Longest Substring Without Repeating Characters 题目: Given a string s, find the length of the longest substring without repeating characters. 这到提要求找的是最长的,没有重复符号的子字符串 解题思路是用双指针哈希表&…...

阿里云轻量应用服务器流量价格表(计费/免费说明)

阿里云轻量应用服务器套餐有的限制月流量,有的不限制月流量,限制每月流量的套餐,如果自带的免费月流量包用完了,流量超额部分需要另外支付流量费,阿里云百科aliyunbaike.com分享阿里云轻量应用服务器月流量超额收费价格…...

C++设计模式-装饰器(Decorator)

目录 C设计模式-装饰器(Decorator) 一、意图 二、适用性 三、结构 四、参与者 五、代码 C设计模式-装饰器(Decorator) 一、意图 动态地给一个对象添加一些额外的职责。就增加功能来说,Decorator模式相比生成子…...

【C语言】结构类型的定义和使用

目录 1.结构体(struct)类型 2.结构标记 3.typedef 4.定义结构数组的方法 5.调用结构数组的方法 6.将结构体传入函数 7.结构体使用实例 1.结构体(struct)类型 在C语言中,结构体(struct&#xf…...

C++内存管理:其二、数组内存管理

一、new一个对象数组 如果我们想在堆内存上创建一个对象数组,可以这么写: Complex * pca new Complex[3]; 主要做三件事: (1)申请一块内存,足够放置三个Complex对象。 (2)执行三次…...

No169.精选前端面试题,享受每天的挑战和学习

🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…...

Hadoop设置hdfs全局指令

在终端进入用户个人环境变量配置文件 vim ~/.bashrc 然后添加如下内容 export PATH$PATH:/usr/local/hadoop/bin 添加到你的hadoop下载目录的bin目录为止就可以了 重新激活一下配置文件 source ~/.bashrc hdfs有专属于自己的文件存储目录,加上特殊的指令就可以箱终端一…...

IDEA 2023.1.3图文安装教程及下载

IDEA 2023.1 最新变化是在 IDEA 2023.1 中,对新 UI 做出了大量改进。实现了性能增强,从而更快导入 Maven,以及在打开项目时更早提供 IDE 功能。 新版本通过后台提交检查提供了简化的提交流程。 IntelliJ IDEA Ultimate 现在支持 Spring Secur…...

【JVM】运行时数据区(内存区域划分)详解

文章目录 前言一、JVM 运行时数据区1, 堆2, Java 虚拟机栈3, 本地方法栈4, 程序计数器5, 元数据区 / 方法区 二、内存异常问题1, 栈溢出2, 内存溢出3, 内存泄露 总结 前言 📕各位读者好, 我是小陈, 这是我的个人主页 📗小陈还在持续努力学习编程, 努力通…...

Python-Scrapy框架(框架学习)

一、概述 Scrapy是一个用于爬取网站数据的Python框架,可以用来抓取web站点并从页面中提取结构化的数据。 基本组件: 引擎(Engine):负责控制整个爬虫的流程,包括调度请求、处理请求和响应等。 调度器(Scheduler):负责…...

flink生成水位线记录方式--基于特殊记录的水位线生成器

背景 在flink基于事件的时间处理中,水位线记录的生成是一个很重要的环节,本文就来记录下几种水位线记录的生成方式的其中一种:基于特殊记录的水位线生成器 基于特殊记录的水位线生成器 我们发送的事件中,如果带有某条特殊记录的…...

Arcgis日常天坑问题(1)——将Revit模型转为slpk数据卡住不前

这段时间碰到这么一个问题,revit模型在arcgis pro里导出slpk的时候,卡在98%一直不动,大约有两个小时。 首先想到的是revit模型过大,接近300M。然后各种减小模型测试,还是一样的问题,大概花了两天的时间&am…...

JavaWeb:上传文件

1.建普通maven项目,或者maven项目,这里以普通maven为例,区别的jar包的导入方式啦 到中央仓库下载哦 2.结构 3.写fileservlet public class FileServlet extends HttpServlet {Overrideprotected void doPost(HttpServletRequest req, HttpSe…...

STM32 大小端与字节对齐使用记录

大小端 串口数据包解析 MDK stm32 小段模式 接收到的数据包: DD 03 00 1B 11 59 00 00 00 00 17 70 00 00 2F 39 00 00 00 00 00 03 23 64 00 0E 02 0B 6E 0B 84 FC EA 77 其中数据内容为: DD 03 00 1B 11 59 //电压mV 00 00 00 00 17 70 …...

RabbitMQ中basic**方法汇总与参数解释

当使用RabbitMQ进行消息传递时,Channel对象提供了一组称为"basic方法"的方法,用于执行最基本的消息传递操作。在本篇博客中,我们将详细介绍这些方法,包括示例和参数解释。 1. basicPublish 方法 basicPublish 方法用于…...

linux之/etc/default/useradd文件

/etc/default/useradd文件是在使用useradd添加用户时,一个需要调用的默认的配置文件之一,可以使用命令"useradd -D"进行修改。 useradd用法: [rootcentos79-3 mail]# useradd --help Usage: useradd [options] LOGINuseradd -Dus…...

3.primitive主数据类型和引用 认识变量

3.1 声明变量 Java注重类型。它不会让你做出把长颈鹿类型变量装进兔子类型变量中这种诡异又危险的举动——如果有人对长颈鹿调用“跳跃”这个方法会发生什么样的悲剧?并且它也不会让你将浮点数类型变量放进整数类型的变量中,除非你先跟编译器确认过数字…...

【群智能算法改进】一种改进的光学显微镜算法 IOMA算法[1]【Matlab代码#60】

文章目录 【获取资源请见文章第5节:资源获取】1. 光学显微镜算法(OMA)1.1 物镜放大倍数1.2 目镜放大倍数 2. 改进后的IOMA算法2.1 透镜成像折射方向学习 3. 部分代码展示4. 仿真结果展示5. 资源获取说明 【获取资源请见文章第5节:…...

第三课-软件升级-Stable Diffusion教程

前言: 虽然第二课已经安装好了 SD,但你可能在其它地方课程中,会发现很多人用的和你的界面差距很大。这篇文章会讲一些容易忽略或者常常需要做的操作,不一定要完全照做,以后再回过头看看也可以。 1.控制类型 问题:为什么别人有“控制类型”部分,而我没有?如下红色方框…...

【C++】设计模式之——建造者

建造者模式概念模拟实现建造者模式代码实现 建造者模式 首先先大体了解一下,建造者模式是什么意思,它是怎么实现的? 首先,建造者模式是一种创建型设计模式再一个它是使用多个简单的对象一步一步的搭建出一个复杂的对象它可以将一个…...

【C++】基础语句(学习笔记)

一、分支 1、三种基本结构 顺序结构分支结构循环结构 2、if与switch对比 1)使用场景 switch只支持常量值固定相等的分支判断if可以判断区间范围用switch能做的,用if都能做 2)性能比较 分支少时,差别不是很大。分支多时&…...

大厂秋招真题【DP】米哈游20230924秋招T2-米小游与魔法少女-奇运

米哈游20230924秋招T2-米小游与魔法少女-奇运 题目描述与示例 题目描述 米小游都快保底了还没抽到希儿,好生气哦!只能打会活动再拿点水晶。 米小游和世界第一可爱的魔法少女 TeRiRi 正在打 BOSS,BOSS 的血量为h,当 BOSS 血量小…...

LVS+Keepalived 高可用集群负载均衡

一.keepalived介绍 1.1.Keepalived实现原理 由多台路由器组成一个热备组,通过共用的虚拟IP地址对外提供服务。 每个热备组内同时只有一台主路由器提供服务,其他路由器处于冗余状态。 若当前在线的路由器失效,则其他路由器会根据设置…...

Qt QList类和QLinkedList类 详解

一、QList 类 对于不同的数据类型&#xff0c;QList<T>采取不同的存储策略&#xff0c;存储策略如下&#xff1a; 如果T 是一个指针类型或指针大小的基本类型(该基本类型占有的字节数和指针类型占有的字节数相同)&#xff0c;QList<T>将数值直接存储在它的数组当…...

Mac安装GYM遇到的一些坑

以下是遇到的一些问题 安装GitHub上说的直接 pip install gym成功了&#xff0c;但是运行实例报错没安装gym[classic_control]&#xff0c;所以就全安装一下[all] 安装GitHub上说的直接 pip install gym成功了&#xff0c;但是运行实例报错没安装gym[classic_control]&#xff…...

【高级rabbitmq】

文章目录 1. 消息丢失问题1.1 发送者消息丢失1.2 MQ消息丢失1.3 消费者消息丢失1.3.1 消费失败重试机制 总结 2. 死信交换机2.1 TTL 3. 惰性队列3.1 总结&#xff1a; 4. MQ集群 消息队列在使用过程中&#xff0c;面临着很多实际问题需要思考&#xff1a; 1. 消息丢失问题 1.1…...

数百个下载能够传播 Rootkit 的恶意 NPM 软件包

供应链安全公司 ReversingLabs 警告称&#xff0c;最近观察到的一次恶意活动依靠拼写错误来诱骗用户下载恶意 NPM 软件包&#xff0c;该软件包会通过 rootkit 感染他们的系统。 该恶意软件包名为“node-hide-console-windows”&#xff0c;旨在模仿 NPM 存储库上合法的“node-…...

SpringBoot的error用全局异常去处理

记录一下使用SpringBoot2.0.5的error用全局异常去处理 在使用springboot时&#xff0c;当访问的http地址或者说是请求地址输错后&#xff0c;会返回一个页面&#xff0c;如下&#xff1a; 这是因为请求的地址不存在&#xff0c;默认会显示error页面 但我们实际需要一个接口&a…...

MyBatisPlus(十一)包含查询:in

说明 包含查询&#xff0c;对应SQL语句中的 in 语句&#xff0c;查询参数包含在入参列表之内的数据。 in Testvoid inNonEmptyList() {// 非空列表&#xff0c;作为参数List<Integer> ages Stream.of(18, 20, 22).collect(Collectors.toList());in(ages);}Testvoid in…...

Linux命令定位与查找:which、whereis和find的用法详解

文章目录 Linux命令的定位与查找1. 简介Linux路径环境变量命令行和Shell 2. which命令which命令的作用使用which命令定位可执行文件多个可执行文件的定位which命令的选项及其使用 3. whereis命令whereis命令的作用使用whereis命令查找二进制文件查找源代码文件whereis命令的选项…...

wordpress hook api/优化关键词的方法

笔记目录 线性方程组与矩阵 线性方程组列对齐后可以写成矩阵乘法的形式 求解$A\cdot xv $时&#xff0c; 即要求取向量x 经矩阵A变换后与向量v重合。 可以分为以下两种情况讨论 \(det(A)!0\) 如果A的行列式不为0&#xff0c;则可以对向量v进行逆变换求解x&#xff1b; 即对v左乘…...

专门做尿不湿的网站/常德网站建设公司

Web开发做得多了&#xff0c;总觉得是体力活&#xff0c;于是搞些代码让自己脱离无聊的Coding吧&#xff08;是脱离“无聊的”Coding&#xff0c;不是脱离无聊的“Coding”&#xff09;。初级阶段 为每个QueryString写转换的代码&#xff0c;针对不同的类型&#xff0c;进行转换…...

做外贸首先要做网站/seo最新

护士站的客户端采用windows moblie&#xff0c;后台数据通过web service提供&#xff0c;在这次护士站的开发中&#xff0c;我负责的工作就是web service的开发。 首先介绍下什么叫web service&#xff0c;简单来说&#xff0c;web service相当于一种远程的函数调用。我们可以将…...

湖南省造价管理站官网/微信引流被加软件

文章目录前言系列文章目录&#xff0c;Vue学习目录&#xff0c;每一章都有代码例子说明二、Vue组件初次使用2.1 创建组件的第一种方式&#xff1a; 使用Vue.component创建一个组件2.2 创建组件的第二种方式&#xff1a;在Vue实例里注册,先定义好对象&#xff0c;然后在实例的co…...

网站如何做视频的软件/南安seo

iCloud恢复是苹果设备非常好用的一个功能&#xff0c;也能帮助我们在意外时刻及时找回重要的手机信息。以微信资料为例&#xff0c;在开启了iCloud备份的情况下&#xff0c;即便你的手机丢失了微信数据&#xff0c;你还是有机会将微信数据从iCloud上恢复。因为iCloud一直在自动…...

wordpress 自定义栏目 删除/百度热线客服24小时

引用 1、什么是引用&#xff1a;引用就是取别名(外号) ​ 引用就是用一个新的标识符与另一个标识符的内存建立绑定关系&#xff0c;从而使一块内存对应多个标识符。 2、引用的基本特性 ​ 1、引用必须初始化&#xff0c;也就是必须有引用目标。 ​ 不存在空的引用&#xf…...