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

滑动窗口(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. 解法 :

    解法一(暴力枚举) :

    算法思路 :

枚举[从每一个位置]开始往后,无重复字符的字串可以到达什么位置.找出其中长度最大的即可.

在往后寻找无重复字串能到达的位置时,可以利用[哈希标]统计出字符出现的频次,来判断什么时候字串出现了重复元素.

    具体步骤 :

  1. 定义两个指针i,j遍历数组
  2. j++,向后移动寻找与i重复的数
  3. j找到与i相同的数,更新字串长度.
  4. 然后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,说明当前窗口没有重复元素,可以直接更新结果

基本思路:

  1. left = 0, right = 0;
  2. 进窗口 ------> 让字符进入哈希表
  3. 循环判断
    1. 窗口内出现重复字符(提前结束循环)
    2. 出窗口 ------- > 从哈希表中删除该字符
    3. 更新结果

    图解流程:

 

 

 

 

    代码展示:

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)_无重复字符的最长字串

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 滑动窗口(2)_无重复字符的最长字串 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记&#xff0c;欢迎大家在评论区交流讨论&#x1f48c; 目…...

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

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

c++概念

C语言设计期末考试知识点 1. 基础语法 变量和数据类型&#xff1a; int, float, double, char, bool 等基本数据类型。常量&#xff1a;const 关键字。变量的作用域&#xff1a;局部变量、全局变量。 输入输出&#xff1a; cin 和 cout&#xff1a;标准输入输出流。格式化输出…...

Makefile 学习笔记(一)gcc编译过程

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

mybatis的基本使用与配置

注释很详细&#xff0c;直接上代码 项目结构 源码 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 中未知类别玻璃文物的化学成分进行分析&#xff0c;鉴别其所属类型3.2 对分类结果的敏感性进行分析 问题44.1 针对不同类别的玻璃文物样品&#xff0c;分析其化学成分之间的关联关系绘图散点图相关系数图 问题3 3.1 对附件表单 3 中未知类别玻璃文物…...

易于理解和实现的Python代码示例

一些示例代码段&#xff0c;但请注意&#xff0c;由于无法直接执行或访问特定环境&#xff0c;将提供一些通用的、易于理解和实现的Python代码示例。这些示例旨在展示编程的不同方面&#xff0c;从基础到稍微复杂一点的概念。 示例1&#xff1a;简单的Python函数 def greet(n…...

Visual Studio 2019/2022 IntelliCode(AI辅助IntelliSense)功能介绍

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

mac安装swoole过程

1.很重要的是得根据自己环境的php版本来选择swoole版本&#xff01;否则都是做无用功。 Swoole 文档 2.通常pecl install swoole是安装最新版本的&#xff0c;当然安装的方式很多种&#xff0c;这里选择编译安装&#xff0c;因为可以选择不同的swoole版本进行安装&#xff0c;…...

代码随想录算法训练营第三十二天 | 509. 斐波那契数,70. 爬楼梯,746. 使用最小花费爬楼梯

第三十二天打卡&#xff0c;动态规范第一天&#xff01;今天比较简单&#xff0c;主要理解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发送邮件服务设置方法&#xff1f;怎么用Oracle数据库发信&#xff1f; Oracle数据库作为企业级应用的核心&#xff0c;其内置的发送邮件功能为企业提供了强大的自动化工具。AokSend将详细介绍如何配置Oracle发送邮件功能&#xff0c;以实现自动化发信&#xff0c;从而提…...

探索 InternLM 模型能力边界

Bad Case 1. 模型服务来源compassarea输入我刚才问了什么问题模型AInternLM2.5-20B-Chat (上海AILab书生浦语)模型BQwen2-72B-Instruct (阿里通义千问)模型A输出对不起&#xff0c;由于我无法访问之前的交互历史记录&#xff0c;我无法回答您刚才问的具体问题是什么。不过&am…...

Python 数学建模——Pearson/Spearman 相关系数

文章目录 前言原理关于 p p p 值Pearson 相关系数代码实例Spearman 相关系数代码实例求相关系数求相关系数矩阵 前言 相关系数尝尝用来衡量两个数值变量之间是否存在某种关系。我们常说的“正相关”“负相关”就是这种相关关系。而相关系数的绝对值大小体现了相关关系的强弱。…...

QUIC的loss detection学习

PTO backoff backoff 补偿 /ˈbkɒf/PTO backoff 是QUIC&#xff08;Quick UDP Internet Connections&#xff09;协议中的一种机制&#xff0c;用于处理探测超时&#xff08;Probe Timeout, PTO&#xff09;重传策略 它逐步增加探测超时的等待时间&#xff0c;以避免网络拥塞…...

【QT】使用QOpenGLWidget后,窗口全屏之后右键菜单出不来的问题

问题 QMainWindow全屏之后&#xff0c;发现右键菜单出不来了&#xff0c;后来排查到问题是和窗口中使用了QOpenGLWidget控件有关系。 解决方案 在QMainWindow构造函数末尾&#xff0c;添加这句话&#xff08;作用是给窗口周围增加1像素线&#xff0c;实现伪全屏&#xff09;…...

MySQL 8.0授权语法变更及解决方案‌

MySQL 8.0授权语法变更及解决方案‌ 授权语法变更‌&#xff1a;‌MySQL 8.0更改了授权语法&#xff0c;‌无法直接在授权语句中使用IDENTIFIED BY来创建用户并设置密码。‌需要先创建用户&#xff0c;‌再单独授权。‌ 创建用户并授权‌&#xff1a;‌ 使用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扩散模型的概念、架构设计与算法实现&#xff0c;详细解析了模型的前向与逆向过程、编码器与解码器的设计、网络结构与训练过程&#xff0c;结合PyTorch代码示例&#xff0c;提供全面的技术指导。 关注TechLead&#xff0c;复旦AI博士&#xff0c;分享A…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; 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功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <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集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

基于SpringBoot在线拍卖系统的设计和实现

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

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、结构体与…...