当前位置:网站首页>Leetcode 3. longest substring without repeated characters
Leetcode 3. longest substring without repeated characters
2022-07-29 06:23:00 【Zhangchuming ZCM】
Power button | 3. Longest substring without repeating characters
Title screenshot
Method 1 : Violence law
Use the list . Use list slices to slide windows .
Traversal string s, Constantly add the characters of the string to the list .
If a new element in the string is found in the previous list , Use slices now , Cut the beginning of the slice to the last bit of the repeating element , Then add the repeating element ( At this time, the repeated part has been cut off ), Then continue to traverse down .
Each addition compares the length , Choose the longer one , Finally, the maximum substring length is returned .
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
a = []
res = 0
for i in s:
if i in a:
a = a[a.index(i)+1:]
a.append(i)
res=res if len(a)< res else len(a)
return res
res It can be used directly max() function
res = max(res, len(a))
Complete test code
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
a = []
res = 0
for i in s:
if i in a:
a = a[a.index(i)+1:]
a.append(i)
res=res if len(a)< res else len(a)
return res
class main():
a = Solution()
s = "abcabcbb"
print(a.lengthOfLongestSubstring(s))
if __name__ == '__main__':
main()
Method 2 : Slide window one
set() Function can create a set of non repeating elements , This function can be used to determine whether there is a repeated part .
Python set() function | Novice tutorial
The inner loop determines whether the newly added element is repeated , If it does not repeat, the pointer moves to the right , Add it to the element set . If the newly added element repeats and cannot enter the loop , Jump out of the loop and enter the outer loop , The outer loop will delete the previous elements , This element is a previously repeated element .
In this way, a series of substrings can be found by using the left and right pointer sliding window , utilize max() Function returns the largest substring without repetition .
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# Hash set , Record whether each character appears
occ = set()
n = len(s)
rk, ans = -1, 0
for i in range(n):
if i != 0:
occ.remove(s[i - 1])
while rk + 1 < n and s[rk + 1] not in occ:
occ.add(s[rk + 1])
rk += 1
ans = max(ans, rk - i + 1)
return ans
Method 3 : Sliding window II
The basic idea is the same as the above, with a little difference . It's easier to understand .
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
occ = set()
left = 0
max_len, cur_len = 0, 0
n = len(s)
for i in range(n):
cur_len += 1
while s[i] in occ:
occ.remove(s[left])
left += 1
cur_len -= 1
max_len = max(max_len, cur_len)
occ.add(s[i])
return max_len
边栏推荐
- Traditional model predictive control trajectory tracking - circular trajectory (function package has been updated)
- 循环链表和双向链表
- [beauty of software engineering - column notes] 14 | project management tools: all management problems should be considered whether they can be solved by tools
- 多线程和并发
- Ml self study notes 5
- 进程与进程的概念
- LeetCode #557.反转字符串中的单词 III
- Dynamic planning summary
- UE5 光影基础 阴影全解析 锯齿阴影解决方案 Lumen
- 【软件工程之美 - 专栏笔记】21 | 架构设计:普通程序员也能实现复杂系统?
猜你喜欢
【软件工程之美 - 专栏笔记】19 | 作为程序员,你应该有产品意识
【软件工程之美 - 专栏笔记】26 | 持续交付:如何做到随时发布新版本到生产环境?
HR must ask questions - how to fight with HR (collected from FPGA Explorer)
【软件工程之美 - 专栏笔记】20 | 如何应对让人头疼的需求变更问题?
Jingwei Qili: OLED character display based on hmep060 (and Fuxi project establishment demonstration)
一些工具,插件,软件链接分享给大家~
关于【链式前向星】的自学理解
Jingwei Qili: development of heart rate and blood oxygen module based on hmep060 (1: FPGA sends multi bit instructions)
LeetCode #19.删除链表的倒数第N个结点
UE5 landscape 换算 Nanite 转换方式及不支持 配合 Lumen及Lumen开启 Dynamic Mesh 使用方法
随机推荐
Markdown and typora
【软件工程之美 - 专栏笔记】27 | 软件工程师的核心竞争力是什么?(上)
寒假集训总结 (1.23~1.28) [第一梯队]
官方教程 Redshift 08 Light
SQLyog 安装和配置教程
Leetcode 283. move zero
Based on STM32: couple interactive doll (design scheme + source code +3d drawing +ad circuit)
HR must ask questions - how to fight with HR (collected from FPGA Explorer)
网络安全学习篇
JUC并发知识点
从头安装MYSQL(MYSQL安装文档-解压版)
位运算学习笔记
SimpleFOC+PlatformIO踩坑之路
Leetcode 167. sum of two numbers II - input ordered array
【软件工程之美 - 专栏笔记】26 | 持续交付:如何做到随时发布新版本到生产环境?
Computer factory interview questions
IDEA安装scala
给二维表添加时间序列索引
Encapsulation - Super keyword
LeetCode #19.删除链表的倒数第N个结点