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

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...