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

【算法训练-字符串】一 最长无重复子串

废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是最长无重复子串或最长无重复子数组,这类题目出现频率还是很高的。
在这里插入图片描述

最长无重复子串【MID】

先来看字符串数据结构的题目

题干

在这里插入图片描述

解题思路

整体目标就是获取最大的无重复滑动窗口

  1. 双指针标识数组或字符串的位置,右指针可以理解为放大窗口指针,左指针可以理解为缩小窗口指针
  2. 定义一个set用来存储元素位置对应的值
  3. 右指针先行,如果一直无重复就一直开拓窗口并更新max值,否则移动左指针缩小窗口,直到将重复值缩到窗口以外。

如下图所示:
在这里插入图片描述

代码实现

基本数据结构字符串
辅助数据结构哈希表
算法迭代
技巧双指针、滑动窗口

class Solution {public int lengthOfLongestSubstring(String s) {// 1 判断入参是否为空列表if (s.length() == 0) {return 0;}// 2 定义返回结果最大值和左右指针以及滑动窗口集合int max = 0;int left = 0;int right = 0;Set<Character> set = new HashSet<>();// 3 滑动窗口移动并在无重复时计算最大值while (left < s.length() && right < s.length()) {// 1 无重复,右指针继续移动,重新计算最大值if (!set.contains(s.charAt(right))) {set.add(s.charAt(right++));max = Math.max(max, right - left);} else {// 2 有重复,左指针继续移动,直到将重复元素移出集合set.remove(s.charAt(left++));}}return max;}
}

复杂度分析

时间复杂度为O(N),因为遍历了字符串;空间复杂度为O(N),借助了HashSet的存储空间

相关文章:

【算法训练-字符串】一 最长无重复子串

废话不多说&#xff0c;喊一句号子鼓励自己&#xff1a;程序员永不失业&#xff0c;程序员走向架构&#xff01;本篇Blog的主题是最长无重复子串或最长无重复子数组&#xff0c;这类题目出现频率还是很高的。 最长无重复子串【MID】 先来看字符串数据结构的题目 题干 解题思…...

【数据结构】手撕顺序表

一&#xff0c;概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构&#xff0c;一般情况下采用数组存储&#xff1b; 在数组上完成数据的增删查改。 1&#xff0c; 静态顺序表&#xff1a;使用定长数组存储元素。 2.&#xff0c;动态顺序表&#xff1…...

景联文科技数据标注:人体关键点标注用途及各点的位置定义

人体关键点标注是一种计算机视觉任务&#xff0c;指通过人工的方式&#xff0c;在指定位置标注上关键点&#xff0c;例如人脸特征点、人体骨骼连接点等&#xff0c;常用来训练面部识别模型以及统计模型。这些关键点可以表示图像的各个方面&#xff0c;例如角、边或特定特征。在…...

typescript基础之never

TypeScript 的 never 类型是一种特殊的类型&#xff0c;它表示的是那些永远不存在的值的类型。例如&#xff0c;一个抛出异常或无限循环的函数的返回值类型就是 never&#xff0c;因为它们永远不会返回任何值。never 类型是所有类型的子类型&#xff0c;也就是说&#xff0c;任…...

电子电路学习笔记之NCP304LSQ37T1G ——超低电流电压检测器

超低电流电压检测器是一种专门用于检测极小电流值的设备。它们常用于电子元件或电路中&#xff0c;用于监测电流的存在和程度。这些检测器通常具有高灵敏度和高精度&#xff0c;能够测量微安级别或更小的电流。 超低电流电压检测器的应用领域广泛&#xff0c;例如电池管理系统…...

【计算机组成原理】一文快速入门,很适合JAVA后端看

作者简介&#xff1a; CSDN内容合伙人、CSDN新星计划导师、JAVA领域优质创作者、阿里云专家博主&#xff0c;计算机科班出身、多年IT从业经验、精通计算机核心理论、Java SE、Java EE、数据库、中间件、分布式技术&#xff0c;参加过国产中间件的核心研发&#xff0c;对后端有…...

10万字智慧政务大数据平台项目建设方案222页[Word]

导读:原文《10万字智慧政务大数据平台项目建设方案222页[Word]》(获取来源见文尾),本文精选其中精华及架构部分,逻辑清晰、内容完整,为快速形成售前方案提供参考。 1.1 项目建设目标 推进市一级政府搭建数字政府建设的规划要求,结合市一级政府“互联网+政务服务”建设…...

Python-主线程控制子线程-4

需求&#xff1a;在Python-主线程控制子线程-3的基础上&#xff0c;新增使用UDP接收指令功能&#xff0c;代替从键盘输入指令 # 修改后的程序&#xff0c;主线程可以获取子线程的结果 import threading import time import queue import tracebackfrom loguru import logger i…...

设计模式二十二:策略模式(Strategy Pattern)

定义一系列算法&#xff0c;将每个算法封装成独立的对象&#xff0c;并使这些对象可互相替换。这使得在运行时可以动态地选择算法&#xff0c;而不必改变使用算法的客户端代码。策略模式的主要目标是将算法的定义与使用分离&#xff0c;使得客户端可以根据需要灵活地选择和切换…...

【c语言】结构体内存对齐,位段,枚举,联合

之前学完结构体&#xff0c;有没有对结构体的大小会很疑惑呢&#xff1f;&#xff1f;其实结构体在内存中存储时会存在内存对齐&#xff0c;捎带讲讲位段&#xff0c;枚举&#xff0c;和联合&#xff0c;跟着小张一起学习吧 结构体内存对齐 结构体的对齐规则: 第一个成员在与结…...

干货丨软件测试行业迎来新时代,AI将成为主流技术?

随着科技日新月异的发展&#xff0c;人工智能正逐渐渗透到我们生活的各方各面&#xff0c;从智能语音助手到自动驾驶汽车、从智能家居到人脸识别技术&#xff0c;AI正以其卓越的智能和学习能力引领着新时代的发展方向。 在这个快速演进的时代中&#xff0c;软件测试领域也受到了…...

MacOS goland go1.21 debug问题

安装dlv brew install dlv 安装之后在终端会显示所在目录 类似/usr/local/Cellar/delve/1.21.0/bin 配置goland 在文件系统中找到goland 右击选择show package contents -> Contents -> plugins -> go 尝试替换 其中对应系统 的 dlv 结果还是不行 然后打开应用gol…...

python 笔记(1)——基础和常用部分

目录 1、print 输出不换行 2、格式化输出字符串 3、浮点数的处理 4、进制转换和ASCII与字符间的转换 5、随机数 6、字符串截取和内置方法 6-1&#xff09;字符串截取 6-2&#xff09;字符串内置方法 7、元组、列表&#xff0c;及其遍历方式 7-1&#xff09;列表常用内…...

kafka架构和原理详解

Apache Kafka 是一个分布式流数据平台,用于高吞吐量、持久性、可扩展的发布和订阅消息。它具有高度的可靠性,被广泛用于构建实时数据流处理、日志收集和数据管道等应用。 基本架构 1. 主题(Topic): 主题是消息的逻辑分类生产者将消息发布到特定的主题中,而消费者可以订阅…...

wsl Ubuntu中非root的普通用户怎么直接执行docker命令

docker需要root权限&#xff0c;如果希望非root用户直接使用docker命令&#xff0c;而不是使用sudo&#xff0c;可以选择将该用户加入到docker用户组。 sudo groupadd docker&#xff1a;添加到groupadd用户组&#xff08;已经有docker用户组&#xff0c;所以可以不用再新增do…...

Web开发模式、API接口、restful规范、序列化和反序列化、drf安装和快速使用、路由转换器(复习)

一 Web开发模式 1. 前后端混合开发模式 前后端混合开发模式是一种开发方式&#xff0c;将前端和后端的开发工作结合在一起&#xff0c;以加快项目的开发速度和 提高协作效率。这种模式通常用于快速原型开发、小型项目或敏捷开发中。在前后端混合开发模式中&#xff0c;前端和…...

<AMBA总线篇> AXI总线协议介绍

目录 01 AXI协议简介 AXI协议特性 AXI协议传输特性 02 AXI协议架构 AXI协议架构 write transaction(写传输) read tramsaction(读传输) Interface and interconnect 典型的AXI系统拓扑 03 文章总结 大家好&#xff0c;这里是程序员杰克。一名平平无奇的嵌入式软件工程…...

一个简单的Python网络爬虫教程

网络爬虫是一种自动获取网页内容的程序&#xff0c;它可以从互联网上的网站中提取数据并进行分析。本教程将带您逐步了解如何使用 Python 构建一个简单的网络爬虫。 注意&#xff1a;在进行网络爬虫时&#xff0c;请遵守网站的使用条款和法律法规&#xff0c;避免对目标网站造…...

YARN资源管理框架论述

一、简介 为了实现一个Hadoop集群的集群共享、可伸缩性和可靠性&#xff0c;并消除早期MapReduce框架中的JobTracker性能瓶颈&#xff0c;开源社区引入了统一的资源管理框架YARN。 YARN是将JobTracker的两个主要功能&#xff08;资源管理和作业调度/监控&#xff09;分离&…...

Unity查找资源依赖关系

这个方法主要是发现资源乱用的情况&#xff0c;对应的逻辑可能要改一个才能用到自己的项目里面 [MenuItem("Tools/Prefab/查找选中资源依赖关系", false, 0)] public static void FindDependencies() { foreach (var guid in Selection.assetGUIDs…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...