【Python 千题 —— 算法篇】无重复字符最长子段

embedded/2024/12/22 19:35:50/

请添加图片描述

Python 千题持续更新中 ……
脑图地址 👉:⭐https://twilight-fanyi.gitee.io/mind-map/Python千题.html⭐

字符串处理

题目背景

在编程过程中,处理字符串的任务时常遇到,其中一个经典问题是查找无重复字符的最长子串。这在很多应用场景中有实际价值,例如在文本处理、数据分析、加密技术等领域中,确保字符串的唯一性和最长性是至关重要的。本题目要求我们不仅要找出最长的无重复字符的子串,还要优化算法,以应对大量输入的需求。

通过本题的学习,我们可以进一步提升对字符串的理解和操作,掌握滑动窗口、哈希表等高效的算法技巧。

题目描述

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

你需要实现一个函数 lengthOfLongestSubstring(),该函数接收一个字符串 s 作为输入,并返回无重复字符的最长子串的长度。

输入描述

  • 一个字符串 s,长度不超过 10^5,只包含 ASCII 字符。

输出描述

  • 一个整数,表示无重复字符的最长子串的长度。

示例

示例 ①

输入:

python"># 调用 lengthOfLongestSubstring() 函数
print(lengthOfLongestSubstring("abcabcbb"))

输出:

3

解释:无重复字符的最长子串是 “abc”,其长度为 3。

示例 ②

输入:

python">print(lengthOfLongestSubstring("bbbbb"))

输出:

1

解释:最长子串是 “b”,其长度为 1。


代码讲解与多种解法

解法一:暴力破解法

最简单的解法是尝试枚举字符串中每一个子串,并判断这个子串中是否包含重复字符。这种方法需要嵌套循环遍历每个子串,并检查是否有重复字符。

python">def lengthOfLongestSubstring(s):def is_unique(substring):return len(substring) == len(set(substring))n = len(s)max_len = 0for i in range(n):for j in range(i + 1, n + 1):if is_unique(s[i:j]):max_len = max(max_len, j - i)return max_len

优点:

  • 思路清晰,容易理解和实现。

缺点:

  • 时间复杂度为 O(n^3),对于较大的字符串,效率较低。

解法二:滑动窗口

暴力破解法的最大问题是效率低下,因为每次需要重新检查整个子串。通过滑动窗口的思想,我们可以有效地减少重复计算。滑动窗口法通过使用两个指针(startend)来维护一个窗口,并通过移动指针来寻找符合条件的最长子串。

python">def lengthOfLongestSubstring(s):n = len(s)if n == 0:return 0char_set = set()max_len = 0left = 0for right in range(n):while s[right] in char_set:char_set.remove(s[left])left += 1char_set.add(s[right])max_len = max(max_len, right - left + 1)return max_len

优点:

  • 时间复杂度降为 O(n),大大提高了性能。
  • 使用滑动窗口动态调整子串的范围,不需要重新计算每一个子串。

缺点:

  • 虽然时间复杂度较低,但内存占用可能稍大。

解法三:滑动窗口 + 哈希表

滑动窗口的效率已经不错,但我们还可以优化移除字符的操作。如果使用哈希表(即字典)来记录每个字符最后一次出现的位置,我们可以更加精确地调整窗口的左端,而不需要逐个移除字符。

python">def lengthOfLongestSubstring(s):n = len(s)if n == 0:return 0char_index = {}max_len = 0left = 0for right in range(n):if s[right] in char_index:left = max(char_index[s[right]] + 1, left)char_index[s[right]] = rightmax_len = max(max_len, right - left + 1)return max_len

优点:

  • 更加高效,进一步减少不必要的操作。
  • 保持 O(n) 的时间复杂度,并优化了滑动窗口的移动。

缺点:

  • 相较于滑动窗口,增加了一些额外的空间复杂度,用于存储哈希表。

总结与思考

在解决无重复字符最长子串问题时,我们可以通过多种方法进行尝试:

  1. 暴力破解法:适合初学者学习和理解,但实际应用中性能较差。
  2. 滑动窗口:通过维护一个窗口的字符集,减少了重复检查,提高了效率。
  3. 滑动窗口 + 哈希表:在滑动窗口的基础上进一步优化,通过哈希表来快速调整窗口,提升了效率。

在处理大型字符串数据时,选择合适的算法是至关重要的。滑动窗口和哈希表结合的算法是目前解决该类问题的最优选择,它在实际应用中的表现非常出色。

扩展思考

无重复字符的最长子串问题不仅仅是对字符的简单处理,它也能用于多个复杂场景,例如:

  • 在密码学中,寻找不重复的字符片段可以用于增强密码的安全性。
  • 在自然语言处理中,最长不重复子串可以帮助我们分析文本结构。
  • 在压缩算法中,可以利用不重复字符的子串来提升压缩效率。

通过本题的练习,不仅能够提升我们对字符串操作的理解,也能让我们在处理类似问题时有更好的应对方案。


希望通过本文的讲解,你能掌握无重复字符最长子串的几种常见算法,并学会如何在实际编程中高效地解决字符串问题!

持续关注博客,获取更多编程练习与技巧!
作者信息

作者 : 繁依Fanyi
CSDN: https://techfanyi.blog.csdn.net
掘金:https://juejin.cn/user/4154386571867191

http://www.ppmy.cn/embedded/109342.html

相关文章

[Linux] Linux如何管理进程

标题:[Linux] Linux如何管理进程 水墨不写bug 目录 一、如何理解管理 二、如何进行管理(先描述,后管理) 三、进程的概念 正文开始: 在《Linux操作系统入门详解》中,我们了解到了操作系统的定位…

交友系统“陌陌”全方位解析

交友系统在现代社会中扮演着越来越重要的角色,尤其是随着互联网技术的发展,各种交友软件层出不穷。陌陌作为其中的佼佼者,其全方位解析对于理解交友系统的商业开发至关重要。 陌陌的核心功能是提供基于地理位置的社交服务,用户可…

模拟网络丢包常用方法以及工具

文章目录 背景常用方法代码实现使用方法测试代码 使用网络流量控制工具 常用工具Clumsy 背景 在软件开发过程中,经常需要模拟不同的网络环境来测试应用在不同条件下的表现。 这些模拟可以采用多种方式进行,包括在代码中实现随机丢包、随机延时、乱序&am…

transforemr网络理解

1.transformer网络中数据的流动过程: 2.transformer中残差的理解: 残差连接(Residual Connection) 的核心思想就是通过将输入与经过变化的输出相加,来最大限度地保留原始信息。 transforemr中注意力层网络和前馈神经…

VOCs将纳入征税,LDAR系统的排放量计算准确度将要求更加规范,VOCs排放量计算准确度会更加重视,直接影响到税费

笔者见过很多不同公司的LDAR管理系统以及和很多检测公司技术人员沟通,部分技术人员在排放量计算方面尽然不知道中间点等关键要素,有的系统计算排放量不考虑中间点算法、有的计算一年四轮次检测 每轮都是独立计算和上轮检测数据没有任何关系(这…

CMake_CMD_02_add_custom_command() 是什么功能?

在 CMake 中,add_custom_command() 函数用于定义一个自定义命令,以便在构建过程中执行特定的操作。这个命令通常与文件的生成、处理或更新相关联,可以指定在构建过程中的任何阶段执行。 功能 生成文件: add_custom_command() 通常用于生成源…

洛谷刷题之B2089 数组逆序重存放

数组逆序重存放 题目入口 题目描述 将一个数组中的值按逆序重新存放。例如,原来的顺序为 8 , 6 , 5 , 4 , 1 8,6,5,4,1 8,6,5,4,1。要求改为 1 , 4 , 5 , 6 , 8 1,4,5,6,8 1,4,5,6,8。 输入格式 输入为两行:第一行数组中元素的个数 n n n&#x…

c++ 定义函数

在C中,定义函数是一个基本的编程概念。函数是执行特定任务的一段代码,可以接受参数并返回值。下面是关于如何定义和使用函数的详细介绍。 1. 函数的基本结构 函数的基本结构包括以下几个部分: 返回类型:表示函数返回值的类型。…