leetcode面试经典150题——31 无重复字符的最长子串(方法二极简代码!!!)
题目: 无重复字符的最长子串
描述:
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
leetcode链接
方法一:滑动窗口(双指针)
设定两个指针left和right指向最长子串的头部和尾部的下一个元素,left和right初始分别为0和1,对于right指向的每一个元素我们都在前面left和right区间内寻找是否出现过,若未出现过,则把它加入子串中,,right指针右移,若出现过,left指针移动到出现的元素后一个位置,right指针移动到出现的元素后两个位置,最后再更新最长子串的长度
时间复杂度:o(n²) 需要遍历一遍字符串的时间复杂度为o(n),对于每一个新加入的元素都需要进行查找操作,时间复杂度为o(n),因此总时间复杂度为o(n²)
空间复杂度:o(1) 都在原字符串上进行操作,无需占用新的内存空间
int lengthOfLongestSubstring(string s) {int n = s.size();if(n==1){//字符串只有一个元素,那么最长无重复子串长度也为1return 1;}int left = 0,right = 1;int maxLen = 0;while(right<n){int i = left;//在子串中查找相同的元素while(s[right]!=s[i]&&i<right){i++;}if(i==right){//没有相同的元素则加入子串中right++;}else{left = i+1;right = i+2;}//更新最大的子串长度maxLen = max(maxLen,right-left);}return maxLen;
}
方法二:滑动窗口+哈希表判断重重复元素
对于方法一中我们判断重复元素需要遍历一遍子数组,时间复杂度为o(n),因此我们考虑用哈希表来优化查找重复元素的时间,我们把子数组的每一个元素存储到哈希表中,哈希表查找的时间复杂度为o(1),同样的我们定义两个指针left和right,left
指向子数组的起始位置,right指向待加入的元素,然后我们利用count()判断right指向的元素是否在子数组中存在,如果不存在,那么加入哈希表中,如果存在删除哈希表中键为s[left]的元素,然后left右移动,循环此操作直到right指向的元素在子数组中不出现为止,最后维护最大的子数组长度。
时间复杂度:o(n)left,right指针均只会向右移动,遍历一遍字符串,时间复杂度为o(n)
空间复杂度:o(n)哈希表的空间为o(n)
int lengthOfLongestSubstring(string s) {int n = s.size();int left = 0,right = 0;int maxLen = 0;unordered_map<char,int> map;while(right<n){while(left<right&&map.count(s[right])){//删除有重复字符的子串直至不出现重复的字符map.erase(s[left++]);}//把right指向的元素当成关键字插入mapmap[s[right++]] = 0;maxLen = max(maxLen,right-left);}return maxLen;}
相关文章:
leetcode面试经典150题——31 无重复字符的最长子串(方法二极简代码!!!)
题目: 无重复字符的最长子串 描述: 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 leetcode链接 方法…...
Kafka(一):在WSL单机搭建Kafka伪集群
目录 1 运行Kafka单实例1.1 Windws1.1.1 安装包下载1.1.2 修改环境变量1.1.3 修改配置文件1.1.4 启动Kafka单机版 1.2 Linux1.2.1 安装包下载1.2.2 创建目录1.2.3 添加环境变量1.2.4 修改配置文件1.2.5 运行Kafka1.2.6 停止Kafka 2 搭建Kafka集群2.1 搭建Zookeeper集群2.2 搭建…...
mysql1124实验七索引管理
实验任务七 索引管理实验任务书 1. 实验目的 掌握在MySQL中使用MySQL Workbench或者SQL语句创建和使用索引的方法(以SQL命令为重点)。 掌握在MySQL中使用MySQL Workbench或者SQL语句查看和删除索引的方法(以SQL命令为重点)。 …...
[带余除法寻找公共节点]二叉树
二叉树 题目描述 如上图所示,由正整数1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结点(编号是1的结点)都有一条唯一的路径,比如从10到根结点的路径是(10, 5, 2, 1),从4到根结点的路径是(4, 2, 1)&#x…...
详解Rust编程中的生命周期
1.摘要 生命周期在Rust编程中是一个重要概念, 它能确保引用像预期的那样一直有效。在Rust语言中, 每一个引用都有其生命周期, 通俗讲就是每个引用在程序执行的过程中都有其自身的作用域, 一旦离开其作用域, 其生命周期也宣告结束, 值不再有效。幸运的是, 在绝大多数时间里, 生…...
【实践】Deployer 发布到search head : local OR default
1: 背景: search head deployer 上的 /opt/splunk/etc/schcluster/apps 下面的local, 还有default 派发到 search head 到app 下面是怎么工作的,这个过程,实践了一下: 参考Use the deployer to distribute apps and configuration updates - Splunk Documentation 2: 实…...
U盘报错无法访问文件或目录损坏且无法读取的解决办法
使用电脑打开U盘的部分文件时提示无法访问,文件或目录损坏且无法读取 报错内容如下图: 因为我这个U盘是那种双接口的 Type-C和USB,前段时间被我摔了一下 看网上说这种双接口的U盘USB接口容易坏掉 尝试在手机上使用OTG打开,先测试…...
【MySQL】数据库基础操作
👑专栏内容:MySQL⛪个人主页:子夜的星的主页💕座右铭:前路未远,步履不停 目录 一、数据库操作1、创建数据库2、查看所有数据库3、选定指定数据库4、删除数据库 二、数据表操作1、创建数据表2、查看所有表3、…...
2023年微软开源八个人工智能项目
自2001年软件巨头微软前首席执行官史蒂夫鲍尔默对开源(尤其是Linux)发表尖刻言论以来,微软正在开源方面取得了长足的进步。继ChatGPT于去年年底发布了后,微软的整个2023年,大多数技术都是面向开发人员和研究人员公开发…...
指定训练使用的GPU个数,没有指定定gpu id,训练在其中两个gpu上执行,但是线程id分布在所有4个gpu上,为什么?如何解决?
目录 问题背景 1 线程id分布在所有gpu(包括未启用的gpu)上原因: 2 在解决这个问题时,可以采取以下步骤: 3 修正深度学习框架默认使用所有可见 GPU 的问题 1 TensorFlow: 2 PyTorch: 3 K…...
PPT 遇到问题总结(修改页码统计)
PPT常见问题 1. 修改页码自动计数 1. 修改页码自动计数 点击 视图——>幻灯片母版——>下翻找到计数页直接修改——>关闭母版视图...
Matplotlib子图的创建_Python数据分析与可视化
Matplotlib子图的创建 plt.axes创建子图fig.add_axes()创建子图 plt.axes创建子图 前面已经介绍过plt.axes函数,这个函数默认配置是创建一个标准的坐标轴,填满整张图。 它还有一个可选的参数,由图形坐标系统的四个值构成。这四个值表示为坐…...
VM虚拟机中Ubuntu14.04安装VM tools后仍不能全屏显示
1、查看Ubuntu所支持的分辨率大小。 在终端处输入: xrandr,回车 2、输入你想设置的分辨率参数。 我设置的为1360x768,大家可以根据自己的具体设备设置。 在终端输入:xrandr -s 1360x768 注意:这里1360后边是字母 x 且…...
聊聊httpclient的connect
序 本文主要研究一下httpclient的connect HttpClientConnectionOperator org/apache/http/conn/HttpClientConnectionOperator.java public interface HttpClientConnectionOperator {void connect(ManagedHttpClientConnection conn,HttpHost host,InetSocketAddress loca…...
处理视频的新工具:UniFab 2.0.0.4 Crack
UniFab这是一个用于处理视频的新工具,可以帮助您像专业人士一样获得结果,事实上,它可以确保在项目的任何设备上完美播放,所以,来认识一下 UniFab - 一款功能强大且方便的视频编辑器和转换器,但另一方面&…...
设计模式—开闭原则
1.背景 伯特兰迈耶一般被认为是最早提出开闭原则这一术语的人,在他1988年发行的《面向对象软件构造》中给出。这一想法认为一旦完成,一个类的实现只应该因错误而修改,新的或者改变的特性应该通过新建不同的类实现。新建的类可以通过继承的方…...
【开源】基于Vue和SpringBoot的学校热点新闻推送系统
项目编号: S 047 ,文末获取源码。 \color{red}{项目编号:S047,文末获取源码。} 项目编号:S047,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 新闻类型模块2.2 新闻档案模块2.3 新…...
Java,File类与IO流,处理流:缓冲流、转换流、数据流、对象流
目录 处理流之一:缓冲流 四种缓冲流: 缓冲流的作用: 使用的方法: 处理文本文件的字符流: 处理非文本文件的字节流: 操作步骤: 处理流之二:转换流 转换流的使用: …...
【电路笔记】-分压器
分压器 文章目录 分压器1、概述2、负载分压器3、分压器网络4、无功分压器4.1 电容分压器4.2 感应分压器 5、总结 有时,需要精确的电压值作为参考,或者仅在需要较少功率的电路的特定阶段之前需要。 分压器是解决此问题的一个简单方法,因为它们…...
音视频5、libavformat-3
8、设置I/O中断机制 在 demux 时,我们首先需要调用 avformat_open_input() 打开一个输入,然后循环调用 av_read_frame() 函数来读取输入。 我们要注意的是: avformat_open_input() 和 av_read_frame() 都是阻塞函数,如果不能读取到足够的数据,那么它们将会一直阻塞…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
