【leetcode】3: 无重复字串的最长子串(python)
2023-09-11 14:21:08 时间
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s:return 0 left = 0 lookup = set() n = len(s) max_len = 0 cur_len = 0 for i in range(n): cur_len += 1 #如果新的字符在当前窗口内。则窗口跳过当前的窗口,重新开始获得新的窗口。i=1,s[i]=k;s[i-1]=k=s[0] while s[i] in lookup:#为什么这里要用while?因为只remove了最左边的字符,还需要进行循环remove lookup.remove(s[left]) left += 1 cur_len -= 1 #如果新的字符不在当前窗口内: if cur_len > max_len: max_len = cur_len #无论如何都会向后添加窗口后的第一个元素 lookup.add(s[i]) return max_len
整体的思路也就是使用滑动窗口法,首先窗逐渐扩大,扩大到直到遇到了重复的字串后,则移动left指针,每次left指针向右移动一次,则将当前窗口left所指的字符remove掉,同时记录当前字符串长度的cur_len减去1,直到当前窗口中没有任何重复的字符,如字符串:
kbakiop当中
第一个窗口为kba,接着遇到新的k后,则变成了kbak,然后在while循环当中对k进行排除,最左边的k正好是左边的left指针这样新的窗口就变成了bak,然后后面的iop因为都不在窗口当中,因此最后的窗口包含的字符为:bakiop,长度则为6。
相关文章
- 对Python和Go的函数传参研究
- [ML] 可视化编写运行 Python 脚本的工具 Jupyter
- paip.python ide 总结最佳实践o4.
- Python之tkinter:动态演示调用python库的tkinter带你进入GUI世界(Button展示图片事件)
- Python语言学习:利用python语言实现调用内部命令(python调用Shell脚本)—命令提示符cmd的几种方法
- Python语言学习之常见语句命令那些事:python和常见语句命令(条件语句、pass语句)使用方法之详细攻略
- 常微分方程初值问题数值解法[完整公式](Python)
- 【Python成长之路】python并发学习:多进程与多线程的用法及场景介绍
- Python 制作进度条,原来有这么多方法!
- Python Django框架学习09:Django 路由
- 【Python 八股文】- 消息队列基础
- 【LeetCode Python实现】118. 杨辉三角(简单)
- 【LeetCode Python实现】 5472. 重新排列字符串(简单)
- 【LeetCode Python实现】ZJ27 字典树
- 【LeetCode Python实现】3. 无重复字符的最长子串(中等)
- Python 字符串转换为日期
- python里使用正则的findall函数
- python基础===装饰器@property 的扩展
- python基础===Python 代码优化常见技巧
- 【Python】Visual Studio Code 安装&&使用 hello python~~~~
- 【Leetcode刷题Python】88. 合并两个有序数组
- 【Leetcode刷题Python】224. 基本计算器
- 【Leetcode刷题Python】46. 全排列
- 【Leetcode刷题Python】剑指 Offer II 082. 含有重复元素集合的组合
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- 【Leetcode刷题Python】1143. 最长公共子序列
- 【Leetcode刷题Python】718. 最长重复子数组
- 【异常】前端ERR! stack Error: Can‘t find Python executable “python“, you can set the PYTHON env variable.
- 如何学习 python 爬虫?
- macOS chrome selenium python 全屏