LeetCode,3. 无重复字符的最长子串
2024-09-05 01:49:49
看了各位大神的,真是难堪,尤其是各种c++动不动就击败99%。。。
我用python,换了三次算法,改了十几次bug,才击败5%。。。。
贴出来纪念下吧。
题目如下:
给定一个字符串,请你找出其中不含有重复字符的?最长子串?的长度。
示例?1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是?"wke",所以其长度为 3。
?
请注意,你的答案必须是 子串 的长度,"pwke"?是一个子序列,不是子串。
对s="ojyseenuxxpohrysqixldpki"的纸面运算模拟:
def lengthOfLongestSubstring(self, s: str) -> int:
#该函数思路为:从头到尾逐个移动字符,添加到临时字符串中,如果临时字符串已经包含该字符,则剪切至sc列表中保存,并临时字符串清空,重新待填充
sc=[] #列表方式
temps={}#临时字典,按字符头+临时字符串方式
maxlen=0 for x in s:
if x not in sc:#如果该字母在sc字典中不存在以该字母为首字母序列的列表的,则创建之,并填充
sc.append(x)
temps[x]=x
for y in list(temps.keys()):#对临时字符串字典中的key进行遍历
if x in temps[y]:#如果在临时字符串里面有x,则把不重复的字符串添加到sc
if temps[y] not in sc:
sc.append(temps[y])
if x==y:#填充完后,对临时字符串进行处理,
temps[y]=x#对于abc遇到a这种,abc上sc,然后临时字符串a重新从a字符开始
else:
temps[y]=""#对于abc遇到c这种,abc上sc,然后临时字符串a清空,因为下一个字符是c,临时字符串c可能不为空,不能随便覆盖
else:
if temps[y]!="" or (y==x and temps[y]==""):#对于临时字符串如果不为空,则增加字符,对于被清空的字符串,如果字符头和遇到的字符一样,则同意添加
temps[y]=temps[y]+x for y1 in list(temps.keys()):#运行完成后,再回头把所有temps筛选不重复的填充进sc
if temps[y1] not in sc:
sc.append(temps[y1])
#print(sc)
for x1 in sc:#从sc列表中选取最长的字符串,求长度并返回
if len(x1)>maxlen:
maxlen=len(x1)
return maxlen
心得体会:
1、必须纸面模拟,否则直接写,很多地方难以理解为什么,比如临时字符串什么时候清空,什么时候保留一个字符,前面两个算法都没想明白,模拟后发现了差别。
2、list好虽好,但在for循环中,获取最后一个元素没有现成方法,遗憾。(如果x==s[-1:],会有重复的,如果是for用数字循环,则又不值得)
最新文章
- 目标电脑未安装VC++6.0或者VS,运行APP丢失DLL问题解决办法
- .net基本数据类型操作
- padding(内边距)、margin(外边距)、border(边框)
- 你必须知道的ASP.NET-----IHttpAsyncHandler实质
- python——第二天
- Task+http请求
- sed 例子
- uva10375 Choose and divide
- Redis 命令 - Server
- 基于jQuery选择器的整理集合
- XmlHttp对象
- CentOS 5.5安装图解教程
- vs2010中自动实现抽象方法
- cxf2.7.10 与 spring3.0.5集成
- Python 一些常用模块的安装
- 安装JDK,配置环境变量有感
- 工厂设计模式 Factory
- ReactiveSwift源码解析(七) Signal的CombineLatest的代码实现
- XML解析之SAX解析过程代码详解
- vue-cli webpack配置 简单分析
热门文章
- docker-compose部署zabbix4.2.5
- nginx1.15.10配置使用非https访问返回403
- np.mean()函数
- AJax和JQ的结合使用
- webpack的loader的原理和实现
- 持续集成学习11 jenkins和gitlab集成自动触发
- learning java 使用WatchService监控文件变化
- 2019.12.11 java程序中几种常见的异常以及出现此异常的原因
- redis windows版本的使用
- 洛谷 P2858 [USACO06FEB]奶牛零食Treats for the Cows 题解