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

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...