滑动窗口(2)_无重复字符的最长字串
个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创滑动窗口(2)_无重复字符的最长字串
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌
目录
1. 题目链接:
2. 题目描述 :
3. 解法 :
解法一(暴力枚举) :
算法思路 :
具体步骤 :
代码展示 :
结果分析 :
解法二(滑动窗口) :
算法思路 :
图解流程:
代码展示:
结果分析:
滑动窗口的正确性:
时间复杂度分析:
1. 题目链接:
OJ链接:无重复字符的最长字串
2. 题目描述 :
给定一个字符串 s
,请你找出其中不含有重复字符的 最长 子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"
,所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"
,所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"
,所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke"
是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s
由英文字母、数字、符号和空格组成
3. 解法 :
解法一(暴力枚举) :
算法思路 :
枚举[从每一个位置]开始往后,无重复字符的字串可以到达什么位置.找出其中长度最大的即可.
在往后寻找无重复字串能到达的位置时,可以利用[哈希标]统计出字符出现的频次,来判断什么时候字串出现了重复元素.
具体步骤 :
- 定义两个指针i,j遍历数组
- j++,向后移动寻找与i重复的数
- j找到与i相同的数,更新字串长度.
- 然后i++,j = i,重新重新寻找下一个数的最长无重复字串
代码展示 :
class Solution {
public:int lengthOfLongestSubstring(string s) {int len = 0, n = s.size();for(int i = 0; i < n; i++){int hash[128] = {0};for(int j = i; j < n; j++){hash[s[j]]++;if(hash[s[j]] > 1) break;len = max(len, j - i + 1); }}return len;}
};
结果分析 :
!!!!!!!!!!!!!!!!!!!!!!
居然过了?这已经是第二个算法题能直接用暴力通过了
还是老样子,分析一下题目的数据范围:
0 <= s.length <= 5 * 104
字符串的长度区间范围:[0, 5*10^4],没超过10^5就给了暴力枚举的机会
我们暴力枚举的时间复杂度为O(N^2),这样数据级别大于10^9小于10^10是有机会通过的.
如果这道题更狠的话,直接把数据修改为10^5之内的字符,那我们的暴力枚举直接退役了
解法二(滑动窗口) :
算法思路 :
我们发现暴力算法真的很无脑,比如:
研究的对象依旧是一段连续的区间,因此继续使用[滑动窗口]思想来优化.
让滑动窗口满足: 窗口内所有元素都是不重复的.
做法: 右端元素right进入窗口的时候,哈希表统计这个字符的频次:
如果这个字符出现的频次超过1,说明窗口内有重复元素,那么就从左侧开始划出窗口.直到right这个元素的频次变为1,然后更新结果.
如果没有超过1,说明当前窗口没有重复元素,可以直接更新结果
基本思路:
- left = 0, right = 0;
- 进窗口 ------> 让字符进入哈希表
- 循环判断
- 窗口内出现重复字符(提前结束循环)
- 出窗口 ------- > 从哈希表中删除该字符
- 更新结果
图解流程:
代码展示:
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0};int left = 0, right = 0, n = s.size();int ret = 0;while(right < n){hash[s[right]]++;while(hash[s[right]] > 1) hash[s[left++]]--;ret = max(ret, right - left + 1);right++;}return ret;}
};
结果分析:
滑动窗口的正确性:
我们这里使用滑动窗口解决了暴力枚举的重复遍历
时间复杂度分析:
时间复杂度: O(N)
空间复杂度: 我们开了一个hash数组,但只有128个空间,也就是常数级别,可以忽略不记,所以时间复杂度为O(1)
相关文章:

滑动窗口(2)_无重复字符的最长字串
个人主页:C忠实粉丝 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C忠实粉丝 原创 滑动窗口(2)_无重复字符的最长字串 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌 目…...
c语言 —— 结构变量
1.结构变量的定义 类型和变量是不同的概念,只能对变量进行赋值、存取或运算操作,而不能对一个类型进行这些操作。因此在声明了结构类型后,还需要定义结构变量,以便在程序中引用它。结构变量和其他变量一样,必须先定义后使用,定义方法有以下3种: (1)先定义结构类型,再定…...
一个py脚本,提供处理 GET 请求返回网站数据,处理 POST 请求接收并打印数据。支持跨域访问。
from flask import Flask, jsonify, request from flask_cors import CORSapp Flask(__name__)# 允许跨域请求 CORS(app)app.route(/getapi/getadate/test2, methods[GET]) def get_data():response_data {"sites": [{"name": "菜鸟教程", &qu…...

【Elasticsearch系列六】系统命令API
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
c++概念
C语言设计期末考试知识点 1. 基础语法 变量和数据类型: int, float, double, char, bool 等基本数据类型。常量:const 关键字。变量的作用域:局部变量、全局变量。 输入输出: cin 和 cout:标准输入输出流。格式化输出…...

Makefile 学习笔记(一)gcc编译过程
环境准备 .linux 系统(虚拟机) VS code linux 编译过程 预处理: 把.h .c 展开形成一个文件.宏定义直接替换 头文件 库文件 .i 汇编: .i 生成一个汇编代码文件 .S 编译: .S 生成一个 .o .obj 链接: .o 链接 .exe .elf gcc c语言 g c语言 gcc的使用 …...

mybatis的基本使用与配置
注释很详细,直接上代码 项目结构 源码 UserMapper package com.amoorzheyu.mapper;import com.amoorzheyu.pojo.User; import org.apache.ibatis.annotations.Mapper; import org.apache.ibatis.annotations.Select;import java.util.List;Mapper //在运行时生成代…...

2022高教社杯全国大学生数学建模竞赛C题 问题三问题四 Python代码
目录 问题33.1 对附件表单 3 中未知类别玻璃文物的化学成分进行分析,鉴别其所属类型3.2 对分类结果的敏感性进行分析 问题44.1 针对不同类别的玻璃文物样品,分析其化学成分之间的关联关系绘图散点图相关系数图 问题3 3.1 对附件表单 3 中未知类别玻璃文物…...
易于理解和实现的Python代码示例
一些示例代码段,但请注意,由于无法直接执行或访问特定环境,将提供一些通用的、易于理解和实现的Python代码示例。这些示例旨在展示编程的不同方面,从基础到稍微复杂一点的概念。 示例1:简单的Python函数 def greet(n…...

Visual Studio 2019/2022 IntelliCode(AI辅助IntelliSense)功能介绍
IntelliCode 不知在多久以前,我装上了Visual Studio 2019,写代码时,就注意到了下面这样的东西:带五角星的提示。 这个带五角星的提示功能叫做IntelliCode。 我们知道Visual Studio 有个强大的功能叫做Intellisense(智能感知)&am…...

mac安装swoole过程
1.很重要的是得根据自己环境的php版本来选择swoole版本!否则都是做无用功。 Swoole 文档 2.通常pecl install swoole是安装最新版本的,当然安装的方式很多种,这里选择编译安装,因为可以选择不同的swoole版本进行安装,…...
代码随想录算法训练营第三十二天 | 509. 斐波那契数,70. 爬楼梯,746. 使用最小花费爬楼梯
第三十二天打卡,动态规范第一天!今天比较简单,主要理解dp的概念 509.斐波那契数列 题目链接 解题过程 状态转移方程 dp[i] dp[i - 1] dp[i - 2]; 动态规划 class Solution { public:int fib(int n) {if (n < 2) return n;int dp[n …...

Oracle发送邮件功能:配置自动化发信指南?
Oracle发送邮件服务设置方法?怎么用Oracle数据库发信? Oracle数据库作为企业级应用的核心,其内置的发送邮件功能为企业提供了强大的自动化工具。AokSend将详细介绍如何配置Oracle发送邮件功能,以实现自动化发信,从而提…...

探索 InternLM 模型能力边界
Bad Case 1. 模型服务来源compassarea输入我刚才问了什么问题模型AInternLM2.5-20B-Chat (上海AILab书生浦语)模型BQwen2-72B-Instruct (阿里通义千问)模型A输出对不起,由于我无法访问之前的交互历史记录,我无法回答您刚才问的具体问题是什么。不过&am…...
Python 数学建模——Pearson/Spearman 相关系数
文章目录 前言原理关于 p p p 值Pearson 相关系数代码实例Spearman 相关系数代码实例求相关系数求相关系数矩阵 前言 相关系数尝尝用来衡量两个数值变量之间是否存在某种关系。我们常说的“正相关”“负相关”就是这种相关关系。而相关系数的绝对值大小体现了相关关系的强弱。…...

QUIC的loss detection学习
PTO backoff backoff 补偿 /ˈbkɒf/PTO backoff 是QUIC(Quick UDP Internet Connections)协议中的一种机制,用于处理探测超时(Probe Timeout, PTO)重传策略 它逐步增加探测超时的等待时间,以避免网络拥塞…...
【QT】使用QOpenGLWidget后,窗口全屏之后右键菜单出不来的问题
问题 QMainWindow全屏之后,发现右键菜单出不来了,后来排查到问题是和窗口中使用了QOpenGLWidget控件有关系。 解决方案 在QMainWindow构造函数末尾,添加这句话(作用是给窗口周围增加1像素线,实现伪全屏)…...
MySQL 8.0授权语法变更及解决方案
MySQL 8.0授权语法变更及解决方案 授权语法变更:MySQL 8.0更改了授权语法,无法直接在授权语句中使用IDENTIFIED BY来创建用户并设置密码。需要先创建用户,再单独授权。 创建用户并授权: 使用CREATE USER语句创…...

2024 VMpro 虚拟机中如何给Ubuntu Linux操作系统配置联网
现在这是一个联网的状态 可以在商店里面下载东西 也能ping成功 打开虚拟网络编辑器 放管理员权限 进行设置的更改 选择DNS设置 按提示修改即可 注意的是首选的DNS服务器必须是114.114.114.114 原因 这边刚刚去查了一下 114.114.114.114 是国内的IP地址 8.8.8.8 是国外的I…...

详解Diffusion扩散模型:理论、架构与实现
本文深入探讨了Diffusion扩散模型的概念、架构设计与算法实现,详细解析了模型的前向与逆向过程、编码器与解码器的设计、网络结构与训练过程,结合PyTorch代码示例,提供全面的技术指导。 关注TechLead,复旦AI博士,分享A…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...

基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...