惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

Google DeepMind News
Google DeepMind News
Stack Overflow Blog
Stack Overflow Blog
Hugging Face - Blog
Hugging Face - Blog
博客园_首页
T
The Blog of Author Tim Ferriss
博客园 - 叶小钗
N
Netflix TechBlog - Medium
腾讯CDC
C
Check Point Blog
P
Proofpoint News Feed
Engineering at Meta
Engineering at Meta
GbyAI
GbyAI
S
SegmentFault 最新的问题
F
Fortinet All Blogs
美团技术团队
U
Unit 42
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
博客园 - 司徒正美
F
Full Disclosure
Recorded Future
Recorded Future
D
DataBreaches.Net
博客园 - 【当耐特】
Martin Fowler
Martin Fowler
J
Java Code Geeks
I
InfoQ
Y
Y Combinator Blog
A
About on SuperTechFans
AI
AI
爱范儿
爱范儿
Exploit-DB.com RSS Feed
Exploit-DB.com RSS Feed
Forbes - Security
Forbes - Security
W
WeLiveSecurity
M
MIT News - Artificial intelligence
雷峰网
雷峰网
cs.CV updates on arXiv.org
cs.CV updates on arXiv.org
Simon Willison's Weblog
Simon Willison's Weblog
Schneier on Security
Schneier on Security
The GitHub Blog
The GitHub Blog
Security Archives - TechRepublic
Security Archives - TechRepublic
aimingoo的专栏
aimingoo的专栏
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
G
GRAHAM CLULEY
Know Your Adversary
Know Your Adversary
Latest news
Latest news
Threat Intelligence Blog | Flashpoint
Threat Intelligence Blog | Flashpoint
D
Docker
Recent Commits to openclaw:main
Recent Commits to openclaw:main
量子位
V2EX - 技术
V2EX - 技术
Project Zero
Project Zero

博客园 - 马维拉的真实之眼

关于win7添加惠普打印机驱动出现网络打印机驱动安装失败问题的各种解决方法 python 与C#的类方面的区别,纯属感受 word的临时文件机制,还挺有趣 LeetCode的一道题引申的python实现的对字符串进行分词,提取词频的方法 python+lego ev3的心得总结 随时更新 坎巴拉太空计划的心得总结 最近学习的sql查询语句连接查询,标记一下 解决ecplise+phthon2.7中使用pytesser和tesseract进行ocr,出现报错的问题 zt <Windows Image Acquisition (WIA)> from msdn zt对于C#中的FileUpload解决文件上传大小限制的问题设置 当不搞技术好几年后,又回来了,忽然很亲切 胡亥语录,也应该学习学习 无意中看到了一个wii Remote的新应用,廉价触摸屏,很实用,而且已经有人在用了,淘宝上已经有卖红外线笔的了 准备入手wii,先在网上乱看了几小时,然后看到了一条新闻,说360和ps3也要做体感,然后就看到了这两张360的体感游戏照片,太牛叉了 这两天要给别人做视频,学习了下友立的会声会影,找到了些好资源 晕,我的nokia 3500c 和 数独游戏 内存惊魂 EA:这不是一个BUG(只有EA这么财大气粗的才能玩这么NB的招数) 谭望嵩和郑智
LeetCode,3. 无重复字符的最长子串
马维拉的真实之眼 · 2019-11-29 · via 博客园 - 马维拉的真实之眼

看了各位大神的,真是难堪,尤其是各种c++动不动就击败99%。。。
我用python,换了三次算法,改了十几次bug,才击败5%。。。。
贴出来纪念下吧。

题目如下:


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


示例?1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。


示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。


示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是?"wke",所以其长度为 3。
?

请注意,你的答案必须是 子串 的长度,"pwke"?是一个子序列,不是子串。


对s="ojyseenuxxpohrysqixldpki"的纸面运算模拟:

 1 def lengthOfLongestSubstring(self, s: str) -> int:
 2          #该函数思路为:从头到尾逐个移动字符,添加到临时字符串中,如果临时字符串已经包含该字符,则剪切至sc列表中保存,并临时字符串清空,重新待填充
 3         sc=[]   #列表方式
 4         temps={}#临时字典,按字符头+临时字符串方式
 5         maxlen=0
 6         
 7         for x in s:
 8             if x not in sc:#如果该字母在sc字典中不存在以该字母为首字母序列的列表的,则创建之,并填充
 9                 sc.append(x) 
10                 temps[x]=x
11             for y in list(temps.keys()):#对临时字符串字典中的key进行遍历
12                 if x in temps[y]:#如果在临时字符串里面有x,则把不重复的字符串添加到sc
13                     if temps[y] not in sc:
14                         sc.append(temps[y])
15                     if x==y:#填充完后,对临时字符串进行处理,
16                         temps[y]=x#对于abc遇到a这种,abc上sc,然后临时字符串a重新从a字符开始
17                     else:
18                         temps[y]=""#对于abc遇到c这种,abc上sc,然后临时字符串a清空,因为下一个字符是c,临时字符串c可能不为空,不能随便覆盖
19                 else:
20                     if temps[y]!="" or (y==x and temps[y]==""):#对于临时字符串如果不为空,则增加字符,对于被清空的字符串,如果字符头和遇到的字符一样,则同意添加
21                         temps[y]=temps[y]+x
22                    
23         for y1 in list(temps.keys()):#运行完成后,再回头把所有temps筛选不重复的填充进sc
24             if temps[y1] not in sc:
25                 sc.append(temps[y1])
26         #print(sc)
27         for x1 in sc:#从sc列表中选取最长的字符串,求长度并返回
28             if len(x1)>maxlen:
29                     maxlen=len(x1)
30         return maxlen

心得体会:

1、必须纸面模拟,否则直接写,很多地方难以理解为什么,比如临时字符串什么时候清空,什么时候保留一个字符,前面两个算法都没想明白,模拟后发现了差别。

2、list好虽好,但在for循环中,获取最后一个元素没有现成方法,遗憾。(如果x==s[-1:],会有重复的,如果是for用数字循环,则又不值得)