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

算法系列之滑动窗口

算法系列之滑动窗口

题目

给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。

在这里插入图片描述

解题思路

使用滑动窗口算法
滑动窗口算法的核心思想是在一个给定的序列(如数组或字符串)上定义一个窗口,该窗口可以根据特定的条件进行动态调整。窗口的大小可以固定,也可以根据问题的需求动态变化。在滑动过程中,通过不断更新窗口的边界和内部元素的状态,我们能够高效地获取所需的信息,如最大、最小子序列和,满足特定条件的子序列等。​

想象一个在序列上滑动的窗口,就像一个移动的框,它可以从序列的起始位置开始,每次移动一个单位(或根据具体情况移动多个单位)。在每一步移动中,窗口会 “吸入” 新的元素,同时 “吐出” 离开窗口范围的元素。通过对窗口内元素的实时计算和记录,我们可以在不遍历整个序列的情况下,快速找到满足特定条件的子序列。

  • 算法原理
    • 初始化:设置左右指针left和right,通常都指向数据结构的起始位置。
    • 窗口滑动:
      • 扩展右边界:通常先移动right指针来扩展窗口的右边界,直到窗口内的元素不再满足特定条件或right指针到达数据结构的末尾。
      • 收缩左边界:在窗口不满足条件时,移动left指针来收缩窗口的左边界,直到窗口内的元素重新满足条件。
    • 记录结果:在窗口滑动的过程中,记录下满足条件的中间结果(如最大值、最小值、子串长度等)。
    • 重复步骤:重复步骤2和3,直到right指针遍历完整个数据结构。
获取某个字符串中不重复的字符长度,如abfhdasdrbch
//abfhdasdrbch//思路// 索引-字符-不重复字符串-重新开始//0-a-a  (开始位index=0即a)//1-b-ab//2-f-abf//3-h-abfh//4-d-abfhd//5-a-bfhda(a重复了,所以需要重新开始,新的开始位,index=1即b)//6-s-bfhdas//7-d-asd (又重复了,新的开始位,index=5即a)//8-r-asdr//9-b-asdrb

public static  int getBig(String s){//最大长度int max=0;//下一段不重复开始发起始索引号int startIndex=0;//字符对应最新的索引号HashMap<Character, Integer> characterHashMap = new HashMap<Character, Integer>();int length = s.length();for (int i = 0; i < length; i++) {Integer charIndex = characterHashMap.get(s.charAt(i));if (charIndex!=null){// 如果字符已经存在于哈希表中,并且其位置在窗口内,则移动左边界startIndex=Math.max(charIndex+1,startIndex);}characterHashMap.put(s.charAt(i),i);max=Math.max(max,i-startIndex+1);}return max;
}

相关文章:

算法系列之滑动窗口

算法系列之滑动窗口 题目 给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长 子串 的长度。 示例 1:输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"&#xff0c;所以其长度为 3。 示例 2:输入: s "bbbbb"…...

【C#】详解C#中的内存管理机制

文章目录 前言一、C#内存管理的基本机制&#xff08;1&#xff09;托管堆&#xff08;Managed Heap&#xff09;&#xff08;2&#xff09;垃圾回收&#xff08;Garbage Collection&#xff09;&#xff08;3&#xff09;栈内存 二、 开发者需要主动管理的场景&#xff08;1&am…...

C/S架构与B/S架构

一、定义与核心区别 C/S架构&#xff08;Client/Server&#xff0c;客户端/服务器&#xff09; 客户端需安装专用软件&#xff08;如QQ、企业ERP系统&#xff09;&#xff0c;直接与服务器通信。服务器端通常包括数据库和业务逻辑处理1。特点&#xff1a;客户端承担部分计算任务…...

《DeepSeek MoE架构下,动态专家路由优化全解析》

在人工智能飞速发展的当下&#xff0c;模型架构的创新与优化始终是推动技术进步的关键力量。DeepSeek的混合专家模型&#xff08;MoE&#xff09;架构&#xff0c;以其独特的设计理念和卓越的性能表现&#xff0c;在大模型领域崭露头角。而其中的动态专家路由优化技术&#xff…...

Android双亲委派

下面是一份 Android 类加载器双亲委派机制的时序图示例&#xff0c;描述了当应用调用 loadClass() 时&#xff0c;各个加载器之间的委派过程。 #mermaid-svg-rBdlhpD2uRjBPiG8 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mer…...

go语言因为前端跨域导致无法访问到后端解决方案

前端服务8080访问后端8081这端口显示跨域了 ERROR Network Error AxiosError: Network Error at XMLHttpRequest.handleError (webpack-internal:///./node_modules/axios/lib/adapters/xhr.js:116:14) at Axios.request (webpack-internal:///./node_modules/axios/lib/core/A…...

Jmeter使用介绍

文章目录 前言Jmeter简介安装与配置JDK安装与配置JMeter安装与配置 打开JMeter方式一方式二 设置Jmeter语言为中文方法一&#xff08;仅一次性&#xff09;方法二(永久设置成中文) Jmeter文件常用目录 元件与组件元件组件元件的作用域元件的执行顺序第一个案例添加线程组添加 H…...

【商城实战(13)】购物车价格与数量的奥秘

【商城实战】专栏重磅来袭&#xff01;这是一份专为开发者与电商从业者打造的超详细指南。从项目基础搭建&#xff0c;运用 uniapp、Element Plus、SpringBoot 搭建商城框架&#xff0c;到用户、商品、订单等核心模块开发&#xff0c;再到性能优化、安全加固、多端适配&#xf…...

Spring使用@Scheduled注解的参数详解

在现代Java开发中&#xff0c;定时任务是一个常见的需求。Spring框架提供了Scheduled注解&#xff0c;让我们能够以简单、直观的方式定义和管理这些定时任务。接下来&#xff0c;我们来深入探讨这个注解的使用&#xff0c;以及它的参数都有哪些含义和作用。 Scheduled注解可以…...

【网络】HTTP协议、HTTPS协议

HTTP与HTTPS HTTP协议概述 HTTP(超文本传输协议):工作在OSI顶层应用层,用于客户端(浏览器)与服务器之间的通信,B/S模式 无状态:每次请求独立,服务器不保存客户端状态(通过Cookie/Session扩展状态管理)。基于TCP:默认端口80(HTTP)、443(HTTPS),保证可靠传输。请…...

【Windows下Gitbook快速入门使用】

Windows下Gitbook快速入门使用 1 工具安装1.1 Node.js下载安装1.1 环境变量1.2 npm配置1.3 安装gitbook 2 gitbook使用2.1 gitbook 无法执行2.2 gitbook常用命令 Gitbook是一个软件&#xff0c;使用Git和Markdown来编排书本&#xff1b; GitBook helps you pushlish beautiful …...

创建Electron35 + vue3 + electron-builder项目,有很过坑,记录过程

环境&#xff1a; node v20.18.0 npm 11.1.0 用到的所有依赖&#xff1a; "dependencies": {"core-js": "^3.8.3","vue": "^3.2.13","vue-router": "^4.5.0"},"devDependencies": {"ba…...

FPGA 实验报告:四位全加器与三八译码器仿真实现

目录 安装Quartus软件 四位全加器 全加器、半加器 半加器&#xff1a; 全加器&#xff1a; 四位全加器电路图 创建项目 半加器 全加器 四位全加器 代码实现 半加器 全加器 四位全加器 三八译码器 创建项目 代码展示 modelsim仿真波形图 四位全加器 三八译码…...

动态规划详解(二):从暴力递归到动态规划的完整优化之路

目录 一、什么是动态规划&#xff1f;—— 从人类直觉到算法思维 二、暴力递归&#xff1a;最直观的问题分解方式 1. 示例&#xff1a;斐波那契数列 2. 递归树分析&#xff08;以n5为例&#xff09; 3. 问题暴露 三、第一次优化&#xff1a;记忆化搜索&#xff08;Memoiza…...

前端学习——HTML

HTML VSCode常用快捷键HTML标签文本标签列表标签表格Form表单表单元素 块元素与行内元素新增标签 VSCode常用快捷键 代码格式化&#xff1a;ShiftAltF 向上或向下移动一行&#xff1a;AltUp或AltDown 快速复制一行代码&#xff1a;ShiftAltUp或者ShiftAltDown 快速替换&#x…...

12.【线性代数】——图和网络

十二 图和网络&#xff08;线性代数的应用&#xff09; 图 g r a p h { n o d e s , e d g e s } graph\{nodes, edges\} graph{nodes,edges}1.关联矩阵2. A A A矩阵的零空间&#xff0c;求解 A x 0 Ax0 Ax0 电势3. A T A^T AT矩阵的零空间&#xff0c;电流总结电流图结论 …...

[环境搭建篇] Windows 环境下如何安装repo工具

Windows 环境下如何安装repo工具 1. 安装前置依赖2. 配置Repo引导脚本方法一&#xff1a;通过Gitee镜像安装&#xff08;推荐&#xff09;方法二&#xff1a;通过清华镜像安装 3. 解决依赖问题4. 初始化Repo仓库5. 常见问题解决 前言&#xff1a; 在Windows环境下安装Repo工具需…...

LeetCode 热题 100_字符串解码(71_394_中等_C++)(栈)

LeetCode 热题 100_字符串解码&#xff08;71_394&#xff09; 题目描述&#xff1a;输入输出样例&#xff1a;题解&#xff1a;解题思路&#xff1a;思路一&#xff08;栈&#xff09;&#xff1a; 代码实现代码实现&#xff08;栈&#xff09;&#xff1a;以思路一为例进行调…...

「DataX」数据迁移-IDEA运行DataX方法总结

背景 业务需求希望把Oracle数据库中的数据&#xff0c;迁移至MySql数据库中&#xff0c;因为需要迁移全量和增量的数据&#xff0c;所以希望想用数据迁移工具进行操作。 经过一些调研查询&#xff0c;最终打算使用DataX进行数据的迁移。 DataX简单介绍 DataX 是阿里云 DataW…...

【 <一> 炼丹初探:JavaWeb 的起源与基础】之 Servlet 过滤器:实现请求的预处理与后处理

<前文回顾> 点击此处查看 合集 https://blog.csdn.net/foyodesigner/category_12907601.html?fromshareblogcolumn&sharetypeblogcolumn&sharerId12907601&sharereferPC&sharesourceFoyoDesigner&sharefromfrom_link <今日更新> 一、过滤器&…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

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

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

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...