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

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...

CSS 工具对比:UnoCSS vs Tailwind CSS,谁是你的菜?

在现代前端开发中&#xff0c;Utility-First (功能优先) CSS 框架已经成为主流。其中&#xff0c;Tailwind CSS 无疑是市场的领导者和标杆。然而&#xff0c;一个名为 UnoCSS 的新星正以其惊人的性能和极致的灵活性迅速崛起。 这篇文章将深入探讨这两款工具的核心理念、技术差…...