首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

LeetCode题集-3 - 无重复字符的最长子串

编程知识
2024年09月09日 20:17

题目:给定一个字符串 s ,请你找出其中不含有重复字符的最长子串的长度。

我们先来好好理解题目,示例1中怎么得到长度为3的?

如果以第一个字符a为起始,不含重复的最长子串是abc;则我们这样表示(a)bcabcbb -> (abc)abcbb,如此表达枚举出所有可能的情况如下:

1.(a)bcabcbb -> (abc)abcbb;

2.a(b)cabcbb -> a(bca)bcbb;

3.ab(c)abcbb -> ab(cab)cbb;

4.abc(a)bcbb -> abc(abc)bb;

5.abca(b)cbb -> abca(bc)bb;

6.abcab(c)bb -> abcab(cb)b;

7.abcabc(b)b -> abcabc(b)b;

8.abcabcb(b) -> abcabcb(b);

在所有可能的情况中满足条件的最长的子串分别为abc、bca、cab三个,三个长度都是3,因此示例1的结果为3。

01、解法一、双指针法

通过上面枚举出的所有情况,可以发现满足要求的字串是从起始位置向结束位置滚动的,并且在这个过程中,字串的长度也是在变化的,那也就是说只要我们准备两个指针start和end,并控制好两个指针前进的节奏就可以完成任务。

那如何控制指针节奏呢?

首先说第二个指针end,我们把上面1.(a)bcabcbb -> (abc)abcbb中步骤进行补充,应该是1.(a)bcabcbb -> (ab)cabcbb -> (abc)abcbb即指针end一步一步往后走,即使遇到重复字符依旧稳步前进。

每当指针end往后移动一位,只需判断这一位有没有在之前的字串中出现过,如果出现过则开始调整指针start。

例如上面的1->2即(abc)abcbb -> a(bca)bcbb过程中,当指针end到第二个a时,而前面的子串abc中已经出现过a了,因此需要把指针start跳转到b即跳转到子串中重复字符后一个位置。

我们用图例详细描述一下从指针end移动到start移动的具体过程。

下面看看具体实现代码。

public static int SlidingWindow(string s)
{
    //start指针
    var startIndex = 0;
    //end指针
    var endIndex = 0;
    //当前不重复子串长度
    var currentLength = 0;
    //最长不重复子串长度
    var maxLength = 0;
    //一直处理直到end指针不小于字符串长度
    while (endIndex < s.Length)
    {
        //获取待处理字符
        var pendingChar = s[endIndex];
        //判断待处理字符串是否在当前子串中存在
        for (var i = startIndex; i < endIndex; i++)
        {
            //如果子串中已经存在待处理字符
            if (pendingChar == s[i])
            {
                //把start指针跳转至子串中重复字符下一个位置
                startIndex = i + 1;
                //重新计算当前不重复子串长度
                currentLength = endIndex - startIndex;
                break;
            }
        }
        //end指针向后移动一位
        endIndex++;
        //当前不重复子串长度加1
        currentLength++;
        //比较并更新最大不重复子串长度
        if (currentLength > maxLength)
        {
            maxLength = currentLength;
        }
    }
    return maxLength;
}

分析可知,因为是双层循环while+for所以算法时间复杂度是:O(N2),又因为没有引用额外的空间因此空间复杂度是:O(1)。

02、解法二、双指针+哈希法

对于双层循环我们还是有办法进行优化的,最常见的做法是空间换时间,即把内层循环通过哈希表替换换掉,这样通过哈希表提供O(1)查询时间复杂度,使得整个算法时间复杂度达到O(N)。但是哈希表需要额外的O(N)空间

如果用哈希表存储已经存在字符,应该如何存储呢?key存什么?value存什么?这里有一个问题是哈希表只存当前子串的字符?还是存所有已存在字符?如果只存当前子串的字符意味着每次都要清除哈希表,而且清除动作时间复杂度是O(N)。所以我们选择存所有已存在字符。

如果存所有已存在字符,则要注意判断无效数据,比如abc(ba)b中我们不能把最后一个b和第一个b比较,因为当前子串是(ba),所以应该和第二个b做判断。

实现代码如下:

public static int SlidingWindowDictionary(string s)
{
    //start指针
    var startIndex = 0;
    //end指针
    var endIndex = 0;
    //当前不重复子串长度
    var currentLength = 0;
    //最长不重复子串长度
    var maxLength = 0;
    //字典表,存储已存在字符
    var dic = new Dictionary<char, int>();
    //一直处理直到end指针不小于字符串长度
    while (endIndex < s.Length)
    {
        //获取待处理字符
        var pendingChar = s[endIndex];
        //判断待处理字符是否在字典表中存在,并且其索引位置在当前子串中
        if (dic.TryGetValue(pendingChar, out var value) && value >= startIndex)
        {
            //把start指针跳转至子串中重复字符下一个位置
            startIndex = value + 1;
            //重新计算当前不重复子串长度
            currentLength = endIndex - startIndex;
        }
        //更新字典表已存在字符最后的索引位置
        dic[pendingChar] = endIndex;
        //end指针向后移动一位
        endIndex++;
        //当前不重复子串长度加1
        currentLength++;
        //比较并更新最大不重复子串长度
        if (currentLength > maxLength)
        {
            maxLength = currentLength;
        }
    }
    return maxLength;
}

03、解法三、双指针+数组法

那这个算法还有优化空间吗?我们知道哈希表操作是有消耗的,有没有比哈希表更好的存储方式呢?

针对不同的问题可能有不同的方式,对于这一题,的确有点特别,不知道有没有注意到题目最下面的“s 由英文字母、数字、符号和空格组成”描述,这不由的让我想到ASCII码表。

如果是s是由ASCII码表里的字符组成,那么就代表每一个字符都有一个对应的十进制值,这就是天然的下标,然后以所有的ASCII码表数量构建一个字符数组用来存放已经存在的字符,而每个字符存放位置就是其对应的十进制值,这样不就可以解决存储的问题了吗?

因为我们先构建了数组,因此还需要给数组每个元素赋值为-1,用来标记当前元素还没有使用。

具体实现代码如下:

public static int SlidingWindowArray(string s)
{
    //start指针
    var startIndex = 0;
    //end指针
    var endIndex = 0;
    //当前不重复子串长度
    var currentLength = 0;
    //最长不重复子串长度
    var maxLength = 0;
    //定义可能存在的字符数组,并全部填充为-1
    var arr = new int[128];
    Array.Fill(arr, -1);
    //一直处理直到end指针不小于字符串长度
    while (endIndex < s.Length)
    {
        //获取待处理字符
        var pendingChar = s[endIndex];
        //判断待处理字符索引位置是否在当前子串内
        if (arr[pendingChar] >= startIndex)
        {
            //把start指针跳转至子串中重复字符下一个位置
            startIndex = arr[pendingChar] + 1;
            //重新计算当前不重复子串长度
            currentLength = endIndex - startIndex;
        }
        //更新数组中已存在字符最后的索引位置
        arr[pendingChar] = endIndex;
        //end指针向后移动一位
        endIndex++;
        //当前不重复子串长度加1
        currentLength++;
        //比较并更新最大不重复子串长度
        if (currentLength > maxLength)
        {
            maxLength = currentLength;
        }
    }
    return maxLength;
}

虽然已经实现了三种解题方法,但是到底性能如何?下面我们对三个方法进行一组基准测试,每个方法测试10000次,每次随机构建一个长度为10000的字符串。

可以发现双指针+哈希表比单纯的双指针性能还有差很多,而双指针+数组整体表现就好很多了。由此可见双指针+哈希表还是有其局限性的,虽然理论值很好,但是实际表现不尽如人意,这也提醒我们要在合适的地方使用合适的方法,才能更好的解决问题。

测试方法代码以及示例源码都已经上传至代码库,有兴趣的可以看看。https://gitee.com/hugogoos/Planner

From:https://www.cnblogs.com/hugogoos/p/18405351
本文地址: http://www.shuzixingkong.net/article/1871
0评论
提交 加载更多评论
其他文章 爬虫案例2-爬取视频的三种方式之一:requests篇(1)
@目录前言爬虫步骤确定网址,发送请求获取响应数据对响应数据进行解析保存数据完整源码共勉博客 前言 本文写了一个爬取视频的案例,使用requests库爬取了好看视频的视频,并进行保存到本地。后续也会更新selenium篇和DrissionPage篇。当然,爬取图片肯定不止这三种方法,还有基于pytho
爬虫案例2-爬取视频的三种方式之一:requests篇(1) 爬虫案例2-爬取视频的三种方式之一:requests篇(1)
用Python实现阿拉伯数字转换成中国汉字
本文简要介绍了要将阿拉伯数字转换成中国汉字表示的数字的方法,我们需要一个映射表来转换每个数字,并且处理不同位数的数字(如十、百、千、万等),给出了详细的代码示例和解释。
C#/.NET/.NET Core技术前沿周刊 | 第 4 期(2024年9.1-9.8)
前言 C#/.NET/.NET Core技术前沿周刊,你的每周技术指南针!记录、追踪C#/.NET/.NET Core领域、生态的每周最新、最实用、最有价值的技术文章、社区动态、优质项目和学习资源等。让你时刻站在技术前沿,助力技术成长与视野拓宽。 欢迎投稿,推荐或自荐优质文章/项目/学习资源等。每周
C#/.NET/.NET Core技术前沿周刊 | 第 4 期(2024年9.1-9.8) C#/.NET/.NET Core技术前沿周刊 | 第 4 期(2024年9.1-9.8) C#/.NET/.NET Core技术前沿周刊 | 第 4 期(2024年9.1-9.8)
java基础 -线程(基础)的 笔记
581,多线程机制 因为需要敌人的坦克可以自由移动并发射子弹,我们的坦克可以移动并发射子弹,这些要用到线程的知识。 根据JConsole监控线程执行情况,发现,主线程执行完了,子线程还没有执行完,并不能表示当前进程死亡了,只有当所有的子线程执行完了,主进程才会结束。 真正实现多线程的效果, 是 st
java基础 -线程(基础)的 笔记 java基础 -线程(基础)的 笔记 java基础 -线程(基础)的 笔记
全网最适合入门的面向对象编程教程:46 Python函数方法与接口-函数与事件驱动框架
函数是 Python 中的一等公民,是一种可重用的代码块,用于封装特定的逻辑;事件驱动框架是一种编程模式,它将程序的控制流转移给外部事件,如用户输入、系统消息等,它事件驱动框架可以使用函数作为事件的处理逻辑。
全网最适合入门的面向对象编程教程:46 Python函数方法与接口-函数与事件驱动框架 全网最适合入门的面向对象编程教程:46 Python函数方法与接口-函数与事件驱动框架 全网最适合入门的面向对象编程教程:46 Python函数方法与接口-函数与事件驱动框架
代码整洁之道--读书笔记(6)
代码整洁之道 简介: 本书是编程大师“Bob 大叔”40余年编程生涯的心得体会的总结,讲解要成为真正专业的程序员需要具备什么样的态度,需要遵循什么样的原则,需要采取什么样的行动。作者以自己以及身边的同事走过的弯路、犯过的错误为例,意在为后来者引路,助其职业生涯迈上更高台阶。 本书适合所有程序员阅读,
代码整洁之道--读书笔记(6) 代码整洁之道--读书笔记(6)
一种基于祈祷的开源项目学习方法
总体上是这几点: 以祈祷、读文档、读注释、看issue为理解代码的主要手段 以读代码、debug为辅助理解代码的方法 以debug为验证理解的主要手段 每日整理当日理解的内容 不理解的留个印象,先跳过 为什么要祈祷? 因为作者不一定太关心文档和注释:大多数人以正确实现为主要目标。所以要祈祷文档和注释
一种基于祈祷的开源项目学习方法 一种基于祈祷的开源项目学习方法
PHP 程序员学会了 Go 语言就能唬住面试官吗?
唬住了 50k ,唬不住就 5k 。这句话一直是 PHP 程序员之间相互吹捧、吹牛逼的笑点,每次面试过后都会挠挠头上仅剩的几根头发,回想自己是否吹牛逼会过了头。
PHP 程序员学会了 Go 语言就能唬住面试官吗? PHP 程序员学会了 Go 语言就能唬住面试官吗? PHP 程序员学会了 Go 语言就能唬住面试官吗?