【LeetCode热题100】打卡第3天:无重复字符的最长子串

news/2024/4/19 12:00:35/

文章目录

  • 无重复字符的最长子串
    • ⛅前言
    • 🔒题目
    • 🔑题解

无重复字符的最长子串

⛅前言

大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏!

精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种类型的算法题目,包括但不限于数组、链表、树、字典树、图、排序、搜索、动态规划等等,并会提供详细的解题思路以及Java代码实现。如果你也想刷题,不断提升自己,就请加入我们吧!QQ群号:827302436。我们共同监督打卡,一起学习,一起进步。

博客主页💖:知识汲取者的博客

LeetCode热题100专栏🚀:LeetCode热题100

Gitee地址📁:知识汲取者 (aghp) - Gitee.com

Github地址📁:Chinafrfq · GitHub

题目来源📢:LeetCode 热题 100 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台

PS:作者水平有限,如有错误或描述不当的地方,恳请及时告诉作者,作者将不胜感激

🔒题目

原题链接:3. 无重复字符的最长子串 - 力扣(LeetCode)

在这里插入图片描述

🔑题解

  • 解法一:滑动窗口算法

    看到这个题目,我第一个想法就是使用滑动窗口算法😄,简单粗暴

    滑动窗口算法主要思路:

    • Step1:构建窗口。定义两个变量lr(这两个变量就相当于是“指针”),l 确定窗口左边界,r 确定右边界,这样就构成了一个由 l 和 r 的窗口

    • Step2:滑动窗口。

      1. 使用 r 往右遍历字符串
      2. 在遍历的过程中需要判断新加入窗口的元素是否与已窗口中的元素发生重复
      3. 如果重复了,就需要不断移动 l,直到不重复为止

      不断执行1、2、3步,这样我们的窗口就滑动起来了。其中2是核心步骤,一般我们可以通过Set或者Map集合进行判断(当然也可以使用其它方法进行判断,比如数组、字符串,但这两个方法是比较主流的,如何选择就看个人爱好和习惯)

    思路还是挺简单的,可以看一下下面的示意图:
    在这里插入图片描述

    import java.util.HashSet;
    import java.util.Set;/*** @author ghp* @title 无重复字符的最长子串*/
    class Solution {public int lengthOfLongestSubstring(String s) {if (s.length() == 0) {return 0;}// 使用Set集合记录加入窗口的元素(Set集合无重复、插入和删除比较快)Set<Character> set = new HashSet<>(16);int max = Integer.MIN_VALUE;int l = 0; // 窗口左边界int r = 0; // 窗口右边界while (r < s.length()) {// 移动右边界,往窗口中添加新元素char ch = s.charAt(r++);while (set.contains(ch)) {// 新加入窗口的元素与已有元素发生重复,移动左边界set.remove(s.charAt(l++));}// 新元素没有与窗口中已有元素发生重复,加入set集合set.add(ch);// 获取当前最大 无重复字符的最长子串 的长度max = Math.max(max, r - l);}return max;}
    }
    

    复杂度分析:

    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( n ) O(n) O(n)

    其中 n n n 为数组中元素的个数

    这里还提供几种其它方式来判断元素是否重复的方式:

    直接使用String自带的contains方法,需要注意的是sbustring方法截取的是包前不包后

    class Solution {public int lengthOfLongestSubstring(String s) {if (s.length() == 0) {return 0;}int max = Integer.MIN_VALUE;int l = 0;int r = 0;while (r < s.length()) {// 移动右指针,往窗口中添加新元素String ch = s.charAt(r++) + "";// 判断新增元素是否与窗口中已有元素发生重复,重复就移动左指针,直到不重复为止while (s.substring(l, r-1).contains(ch)) {l++;}// 获取当前最大 无重复字符的最长子串 的长度max = Math.max(max, r - l);}return max;}
    }
    
  • 解法二:官方提供的方法,好像也是滑动窗口算法🤣,此外官网并没有提供其它解法,所以说这类题型虽然存在其它解法,但是滑动窗口算法肯定是最优的了

    class Solution {public int lengthOfLongestSubstring(String s) {// 哈希集合,记录每个字符是否出现过Set<Character> occ = new HashSet<Character>();int n = s.length();// 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动int rk = -1, ans = 0;for (int i = 0; i < n; ++i) {if (i != 0) {// 左指针向右移动一格,移除一个字符occ.remove(s.charAt(i - 1));}while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {// 不断地移动右指针occ.add(s.charAt(rk + 1));++rk;}// 第 i 到 rk 个字符是一个极长的无重复字符子串ans = Math.max(ans, rk - i + 1);}return ans;}
    }作者:LeetCode-Solution
    链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
    来源:力扣(LeetCode)
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    

    复杂度分析:

    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( n ) O(n) O(n)

    其中 n n n 为数组中元素的个数


http://www.ppmy.cn/news/85230.html

相关文章

【重新定义matlab强大系列十】函数normalize进行归一化数据

&#x1f517; 运行环境&#xff1a;Matlab &#x1f6a9; 撰写作者&#xff1a;左手の明天 &#x1f947; 精选专栏&#xff1a;《python》 &#x1f525; 推荐专栏&#xff1a;《算法研究》 #### 防伪水印——左手の明天 #### &#x1f497; 大家好&#x1f917;&#x1f91…

StringRedisTemplate和RedisTemplate的区别

StringRedisTemplate和RedisTemplate的区别 springboot提供了两种redis访问工具类StringRedisTemplate和RedisTemplate&#xff0c;为什么spring官方会提供两种不同redis访问工具呢&#xff1f;两者主要的的区别在于redis的key和value的序列化方式不同&#xff0c;并且StringR…

hive 按照某字段聚类在排序,添加编号

使用row_number&#xff08;&#xff09;函数 数据样例 /* 数据样例 --------------------------------------- id |num --------------------------------------- 1 |12 2 |8 1 |29 2 |7 1 |10 --…

Unsupervised Visual Representation Learning by Context Prediction(2015

2015年 仅给定一个大的、未标记的图像集合&#xff0c;我们从每个图像中提取随机的片对&#xff0c;并训练卷积神经网络来预测第二个片相对于第一个片的位置。我们认为&#xff0c;要做好这项工作&#xff0c;需要模型学会识别物体及其组成部分。我们证明了使用这种图像内上下文…

程序员职业病之中医颈椎痛缓解办法

✨求关注~ &#x1f600;博客&#xff1a;www.protaos.com 治疗颈椎病的穴位按摩是一种传统中医疗法&#xff0c;可以缓解颈椎病引起的疼痛和不适。下面是关于五个常用穴位的介绍、取穴定位、按摩方法和功效主治的总结&#xff1a; 人体穴位图 穴位图 1. 揉捏风池穴&#xf…

pandas 遇到Key Error错误的一个小问题

最近刚刚接触Python&#xff0c;安装了Anaconda&#xff0c; 编程小白一个&#xff0c;照着教程准备做一个中考成绩录取分数线分析的案例&#xff0c; 使用read_excel()读入数据后&#xff0c; import pandas as pd data pd.read_excel(rC:\2021-2022深圳中考录取分数线(1).xl…

React组件通信

目录 组件通信的意义 结构准备 通过Props通信 父子通信 父传子 子传父 兄弟组件通信 第三方库的消息订阅与发布 父传子 兄弟传 组件通信的意义 1&#xff09; 组件是独立且封闭的单元&#xff0c;默认情况下组件只能使用自己的数据&#xff08;state&#xff09; 2&…

ChatGPT在语音识别技术领域的应用

第一章&#xff1a;引言 近年来&#xff0c;随着深度学习技术的飞速发展&#xff0c;语音识别技术已经成为了人工智能领域中备受关注的重要领域之一。在语音识别技术的应用中&#xff0c;ChatGPT作为一款先进的语言模型&#xff0c;可以发挥其强大的文本生成和自然语言处理能力…

【ONE·C++ || 哈希(二)】

总言 主要介绍哈希运用于unordered系列的上层封装框架与相关运用&#xff1a;位图、布隆过滤器、哈希切割。 文章目录 总言0、思维导图3、封装3.1、基础封装3.1.1、框架结构3.1.2、Inset 1.0 3.2、引入迭代器3.2.1、在迭代器中3.2.2、在哈希表中3.2.3、在unordered上层3.2.4、…

文本转语音怎么转?教你三招轻松搞定

近年来&#xff0c;人工智能技术飞速发展&#xff0c;语音合成技术 (TTS) 已经被广泛应用于各种应用场景中。在日常生活中&#xff0c;人们经常需要阅读长篇文章、新闻报道、科技论文等&#xff0c;但传统的阅读方式不仅效率低下&#xff0c;而且容易让人感到疲劳。随着语音合成…

day08 Spring MVC

spring MVC相当于Servlet mvc解释:模型,视图,控制器 **使用该思想的作用:**减少耦合性,提高可维护性 Spring MVC前端控制器 方式1 1.在web.xml中配置前端控制器方式2 ​ 要是用前端控制器,必须在web.xml中配置DidpatcherServlet类 <!--前端控制器--> <servlet&g…

14_Uboot图形化配置

目录 U-Boot图形化配置体验 make menuconfig过程分析 Kconfig语法简介 Mainmenu menu/endmenu条目 config条目 depends on和select choice/endchoice Menuconfig Comment Source 添加自定义菜单 U-Boot图形化配置体验 uboot或Linux内核可以通过输入"make menu…

20230522-win11删除文件失败-需要SYSTEM提供的权限

20230522-win11删除文件失败-需要SYSTEM提供的权限 一、软件环境 标签&#xff1a;win11 SYSTEM权限分栏&#xff1a;windows编译器&#xff1a;VS2019 二、问题描述 删除D:\WindowsApps\36186RuoFan.USB_5.8.1.0_x64__q3e6crc0w375t目录下的文件时&#xff0c;提示【文件访…

Qt之程序发布以及打包成exe安装包目录

Qt之程序发布以及打包成exe安装包 目录 一、简述二、设置应用程序图标三、发布程序四、打包程序 回到顶部 一、简述 Qt 项目开发完成之后&#xff0c;需要打包发布程序&#xff0c;而因为用户电脑上没有 Qt 配置环境&#xff0c;所以需要将 release 生成的 exe 文件和所依赖…

通过API接口调用数据的优势是什么?API接口调用展示示例

通过API接口调用数据的优势主要有以下几点&#xff1a; 1.规范化与一致性&#xff1a;API接口提供一种统一的方式来获取数据&#xff0c;保证了数据的规范化与一致性&#xff0c;消除了不同数据源可能带来的格式和结构上的差异。 2.灵活性&#xff1a;使用API接口可以定制请求的…

mycat的基本介绍及安装

1、mycat的基本介绍及安装 1、前置知识 1、分布式系统 ​ 分布式系统是指其组件分布在网络上&#xff0c;组件之间通过传递消息进行通信和动作协调的系统。它的核心理念是让多台服务器协同工作&#xff0c;完成单台服务器无法处理的任务&#xff0c;尤其是高并发或者大数据量…

vue项目性能优化

一、代码层面 1.v-if和v-show使用场景区分 2.computed和watch使用场景区分 3.v-for必须加key&#xff0c;不可和v-if同级使用 4.纯静态数据列表展示&#xff0c;可通过Object.freeze冻结对象 5.组件销毁时&#xff0c;手动移除事件监听器&#xff0c;避免内存泄漏 6.图片…

kaggle新赛推荐 | 从游戏中预测学生的表现

赛题名称&#xff1a;Predict Student Performance from Game Play 从游戏中预测学生的表现 赛题链接&#xff1a;https://www.kaggle.com/competitions/predict-student-performance-from-game-play 赛题背景 学习意味着有趣&#xff0c;这就是基于游戏的学习的用武之地。这…

Hadoop HA(高可用)搭建

ZooKeeper配置 解压安装 添加ZK环境变量 分发文件 启动 安装配置 Hadoop 解压安装 修改hadoop-env.sh文件 修改Hadoop配置文件core-site.xml HDFS 配置文件hdfs-site.xml MapReduce 配置文件 mapred-site.xml YARN 配置文件yarn-site.xml 配置worekers 分发配…

Django框架之模板其他补充

本篇文章是对django框架模板内容的一些补充。包含注释、html转义和csrf内容。 目录 注释 单行注释 多行注释 HTML转义 Escape Safe Autoescape CSRF 防止csrf方式 表单中使用 ajax请求添加 注释 单行注释 语法&#xff1a;{# 注释内容 #} 示例&#xff1a; {# 注…