看了各位大神的,真是难堪,尤其是各种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用数字循环,则又不值得)

最新文章

  1. 目标电脑未安装VC++6.0或者VS,运行APP丢失DLL问题解决办法
  2. .net基本数据类型操作
  3. padding(内边距)、margin(外边距)、border(边框)
  4. 你必须知道的ASP.NET-----IHttpAsyncHandler实质
  5. python——第二天
  6. Task+http请求
  7. sed 例子
  8. uva10375 Choose and divide
  9. Redis 命令 - Server
  10. 基于jQuery选择器的整理集合
  11. XmlHttp对象
  12. CentOS 5.5安装图解教程
  13. vs2010中自动实现抽象方法
  14. cxf2.7.10 与 spring3.0.5集成
  15. Python 一些常用模块的安装
  16. 安装JDK,配置环境变量有感
  17. 工厂设计模式 Factory
  18. ReactiveSwift源码解析(七) Signal的CombineLatest的代码实现
  19. XML解析之SAX解析过程代码详解
  20. vue-cli webpack配置 简单分析

热门文章

  1. docker-compose部署zabbix4.2.5
  2. nginx1.15.10配置使用非https访问返回403
  3. np.mean()函数
  4. AJax和JQ的结合使用
  5. webpack的loader的原理和实现
  6. 持续集成学习11 jenkins和gitlab集成自动触发
  7. learning java 使用WatchService监控文件变化
  8. 2019.12.11 java程序中几种常见的异常以及出现此异常的原因
  9. redis windows版本的使用
  10. 洛谷 P2858 [USACO06FEB]奶牛零食Treats for the Cows 题解