首页 > 编程语言 >【leetcode】3: 无重复字串的最长子串(python)

【leetcode】3: 无重复字串的最长子串(python)

时间:2022-12-28 17:00:11浏览次数:48  
标签:子串 字符 窗口 cur python len 字串 leetcode left

给定一个字符串 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。

标签:子串,字符,窗口,cur,python,len,字串,leetcode,left
From: https://www.cnblogs.com/geeksongs/p/17010530.html

相关文章

  • [oeasy]python0033_回车_carriage_return_figlet_字体变大
    回到开头回忆上次内容进程前后台切换<kbd>ctrl</kbd>+<kbd>z</kbd>把当前进程切换到后台并暂停​​jobs​​查看所有作业用​​fg​​可以把后台进程再切回前台​​......
  • python logging配置
    python中,logging由logger,handler,filter,formater四个部分组成。logger是提供我们记录日志的方法;handler是让我们选择日志的输出地方,如:控制台,文件,邮件发送等,一个logger添加......
  • python中的mysql操作教程及实例
    一.数据库在自动化测试中的应用存测试数据有的时候大批量的数据,我们需要存到数据库中,在测试的时候才能用到,测试的时候就从数据库中读取出来。这点是非常重要的!存测试结......
  • 数值计算:前向和反向自动微分(Python实现)
    1自动微分我们在《数值分析》课程中已经学过许多经典的数值微分方法。许多经典的数值微分算法非常快,因为它们只需要计算差商。然而,他们的主要缺点在于他们是数值的,这意味......
  • python中的集合推导式
    集合推导式可用来去重需求:将列表list1=[2,2,2,3,4,4,4]中的偶数进行筛选,并且去重list1=[2,2,2,3,4,4,4]set1={iforiinlist1ifi%2==0}print(set......
  • python中的列表推导式
    1.单列表,单条件求1-20之间的偶数list1=[]foriinrange(1,21):ifi%2==0:list1.append(i)print(list1)列表推导式list2=[iforiinrange(1,21)if......
  • Python爬虫(一)热身
    基础操作一importurllibimportchardet#字符集检测url="http://www.163.com/"html=urllib.urlopen(url)printhtml.headers#头部信息printhtml.getcode()#状态......
  • 当我把用Python做的课堂点名系统献给各科老师后,再也没挂过科
    刚上大学的表弟问我,大学准备好好玩玩,问我有没有什么不挂科的秘诀。哎,这可就问对人了,要想不挂科,先把老师贿赂好,当然,咱们说的贿赂不是送钱啥的,这不是侮辱老师吗?于是我......
  • python中resp.json()与json.loads(str)的区别
    resp=resquests.get(url)print(type(resp))#<class'requests.models.Response'>第一行代码使用requests库发送get请求,得到响应数据resp。第二行代码的输......
  • 读python代码-学到的python
    1.withopen(data_path,'r')asf:withopen()是python用来打开本地文件的,他会在使用完毕后,自动关闭文件,无需手动书写close().三种打开模式:r:只读 用read()w:只写用w......