[LeetCode 题3] 没有重复字符的最长的子字符串
问题描述
- 输入:一个字符串
s
。 - 输出:最长的无重复字符的子串的长度。
示例
-
输入:
s = "abcabcbb"
输出:3
解释: 最长的无重复字符的子串是"abc"
,长度为 3。 -
输入:
s = "bbbbb"
输出:1
解释: 最长的无重复字符的子串是"b"
,长度为 1。 -
输入:
s = "pwwkew"
输出:3
解释: 最长的无重复字符的子串是"wke"
,长度为 3。
约束条件
0 <= s.length <= 5 * 10^4
- 字符串
s
可以包含英文字符、数字、符号和空格。
解决方案
我们可以使用滑动窗口的方法来解决这个问题。滑动窗口是一种常用的算法技巧,用于处理数组或字符串中的子区间问题。具体步骤如下:
通过这种方法,我们可以高效地找到最长的无重复字符子串,时间复杂度为 O(n),其中 n 是字符串 s
的长度。空间复杂度为 O(min(n, m)),其中 m 是字符集的大小(对于 ASCII 字符集,m 为 128)。
- 使用两个指针
left
和right
来表示当前窗口的左右边界。 - 使用一个哈希集合(Set)来存储当前窗口内的字符,以便快速检查字符是否重复。
- 移动
right
指针扩展窗口,直到遇到重复字符。 - 当遇到重复字符时,移动
left
指针收缩窗口,直到窗口内没有重复字符。 - 在每次移动
right
指针时,更新最长子串的长度。function lengthOfLongestSubstring(s) {let left = 0;let right = 0;let maxLength = 0;const charSet = new Set();while (right < s.length) {if (!charSet.has(s[right])) {// 如果当前字符不在集合中,将其加入集合charSet.add(s[right]);// 更新最长子串的长度maxLength = Math.max(maxLength, right - left + 1);// 移动右指针right++;} else {// 如果当前字符在集合中,移除左指针指向的字符charSet.delete(s[left]);// 移动左指针left++;}}return maxLength; }// 示例用法 console.log(lengthOfLongestSubstring("abcabcbb")); // 输出: 3 console.log(lengthOfLongestSubstring("bbbbb")); // 输出: 1 console.log(lengthOfLongestSubstring("pwwkew")); // 输出: 3
详细解释
-
初始化变量:
left
和right
分别表示滑动窗口的左右边界,初始值都为 0。maxLength
用于记录最长无重复字符子串的长度,初始值为 0。charSet
是一个集合,用于存储当前窗口内的字符。
-
滑动窗口:
- 使用
while
循环遍历字符串s
,直到right
指针到达字符串末尾。 - 如果当前字符
s[right]
不在charSet
中:- 将该字符加入
charSet
。 - 更新
maxLength
为当前窗口的长度right - left + 1
。 - 移动
right
指针。
- 将该字符加入
- 如果当前字符
s[right]
已经在charSet
中:- 从
charSet
中移除s[left]
。 - 移动
left
指针。
- 从
- 使用
-
返回结果:
- 返回
maxLength
作为最长无重复字符子串的长度。
- 返回
相关文章:
[LeetCode 题3] 没有重复字符的最长的子字符串
问题描述 输入:一个字符串 s。输出:最长的无重复字符的子串的长度。 示例 输入: s "abcabcbb" 输出: 3 解释: 最长的无重复字符的子串是 "abc",长度为 3。 输入: s "bbbbb" 输出: 1 解释: 最长的无重复字…...
YoloDotNet 在工业检测中的应用详解
文章目录 一、数据收集与标注二、模型选择与训练三、检测流程设计四、结果评估与优化五、与工业生产线集成一、数据收集与标注 在工业检测中,首先需要收集大量的相关工业产品图像数据。这些数据应涵盖不同的产品类型、缺陷种类以及各种可能的生产状态。例如,对于电子产品的检…...

DataFrame增删改数据
目录 准备数据 DataFrame添加列 直接添加列数据 使用insert添加列数据 DataFrame删除行列 准备数据 删除行 删除列 DataFrame数据去重 准备数据 import pandas as pd df pd.read_csv("../data/b_LJdata.csv") df DataFrame添加列 直接添加列数据 1&…...

一站式解决App下载量统计,Xinstall引领新潮流
在移动应用市场中,App下载量是衡量应用受欢迎程度和市场表现的重要指标。然而,对于许多开发者而言,如何精准统计App下载量却是一个不小的挑战。幸运的是,如今有了一款专业的App全渠道统计服务商——Xinstall,它能够帮助…...
ijkMediaPlayer+ TextureView 等比全屏播放视频(避免拉伸)
TextureView默认以fitxy的方式加载surface数据,如果需要等比全屏播放视频,避免拉伸,可以采用Matrix对TextureView进行变换 废话不多说,直接上代码 public class BaseIjkPlayer implements TextureView.SurfaceTextureListener{/…...
【RS】GEE(Python):数据处理
在前面的章节中,我们已经学习了如何加载影像数据。现在,让我们进一步探讨如何在 Google Earth Engine (GEE) 中进行数据处理。数据处理通常包括图像预处理、裁剪、过滤、重采样等操作。 栅格影像的处理 栅格影像处理包括了裁剪、波段选择、重采样、合成…...

非线性磁链观测器推导
<div id"content_views" class"htmledit_views"><p id"main-toc"><strong>目录</strong></p> 电机方程 电压方程 磁链方程 定义状态变量和输出变量 非线性观测器方程 电角度的计算--锁相环 锁相环调参 电机…...
什么时机用mysql,什么时机用redis,什么时机用本地内存
mysql 的 buffer pool 也是存在内存中,redis 的数据也是存在内存中,为什么不直接存在 mysql 里? 1、数据结构和访问方式 Redis 是一个内存数据库,专门为高效的读写性能而设计。它支持多种数据结构(如字符串、列表、哈…...

Redis八股
缓存 缓存穿透 当查询一个不存在的数据,mysql查询不到数据,无法写入缓存,导致每次都请求数据库 解决方法 缓存空数据,当查询结果未空,将结果进行缓存。 简单但是会消耗内存,而且会出现不一致情况。布隆…...

vue3--通用 popover 气泡卡片组件实现
背景 在日常开发中,我们一般都是利用一些诸如:element-ui、element-plus、ant-design等组件库去做我们的页面或者系统 这些对于一些后台管理系统来说是最好的选择,因为后台管理系统其实都是大同小异的,包括功能、布局结构等 但是对于前台项目,比如官网、门户网站这些 …...

Bluetooth Channel Sounding中关于CS Step及Phase Based Ranging相应Mode介绍
目录 BLE CS中Step定义 BLE CS中交互的数据包/波形格式 BLE CS中Step的不同Mode BLE CS中Step的执行过程 Mode0介绍 Mode0 步骤的作用 Mode0步骤的执行过程 Mode0步骤的执行时间 Mode0步骤的时间精度要求 Mode2介绍 Mode2步骤的作用和执行过程 Mode2步骤的执行时间 B…...
简易STL实现 | Queue 的实现
封装: std::queue 在底层容器的基础上 提供了封装。默认情况下,std::queue 使用 std::deque 作为其底层容器,但也可以配置为使用 std::list 或 其他符合要求的容器 时间复杂度: 入队和出队操作 通常是 常数时间复杂度(…...

【hot100-java】LRU 缓存
链表篇 灵神题解 class LRUCache {private static class Node{int key,value;Node prev,next;Node (int k,int v){keyk;valuev;}}private final int capacity;//哨兵节点private final Node dummynew Node(0,0);private final Map<Integer,Node> keyToNode new HashMap&l…...

Centos7安装ZLMediaKit
一 获取代码 git clone https://gitee.com/xia-chu/ZLMediaKit cd ZLMediaKit git submodule update --init git submodule update --init 命令用于初始化和更新 Git 仓库中的子模块(submodules)。这个命令在 Git 仓库中包含对其他 Git 仓库作为依赖时…...

面试问我LLM中的RAG,咱就是说秒过!!!
前言 本篇文章涉及了 RAG 流程中的数据拆分、向量化、查询重写、查询路由等等,在做 RAG 的小伙伴一定知道这些技巧的重要性。推荐仔细阅读,建议收藏,多读几遍,好好实践。 本文是对检索增强生成(Retrieval Augmented …...
python程序操作pdf
python代码进行多个图片合并为pdf: #python代码进行多个图片合并为pdf: from PIL import Image from fpdf import FPDF import osdef images_to_pdf(image_paths, output_pdf, quality85):"""将多个图片合并为一个PDF文件,并…...

【Python报错】ImportError: DLL load failed while importing _network: 找不到指定的模块。
【Python报错】ImportError: DLL load failed while importing _network: 找不到指定的模块。 问题描述报错原因解决方案参考 问题描述 此段Python代码(在Conda环境下运行)昨天还能运行,但在我手痒更新conda(我有罪)之…...

外包干了5天,技术明显退步
我是一名本科生,自2019年起,我便在南京某软件公司担任功能测试的工作。这份工作虽然稳定,但日复一日的重复性工作让我逐渐陷入了舒适区,失去了前进的动力。两年的时光匆匆流逝,我却在原地踏步,技术没有丝毫…...

正则表达式 | Python、Julia 和 Shell 语法详解
正则表达式在网页爬虫、脚本编写等众多任务中都有重要的应用。为了系统梳理其语法,以及 Python、Julia 和 Shell 中与正则表达式相关的工具,本篇将进行详细介绍。 相关学习资源:编程胶囊。 基础语法 通用语法 在大多数支持正则表达式的语…...

JavaScript全面指南(一)
🌈个人主页:前端青山 🔥系列专栏:JavaScript篇 🔖人终将被年少不可得之物困其一生 依旧青山,本期给大家带来JavaScript篇专栏内容:JavaScript全面指南(一) 1、介绍一下JS的内置类型有哪些? 基本数据类型…...

IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...

微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...

有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...