码迷,mamicode.com
首页 > 其他好文 > 详细

Leetcode(3)无反复字符的最长子串

时间:2019-10-10 00:31:47      浏览:31      评论:0      收藏:0      [点我收藏+]

标签:return   初始   不消   else   暴力   集合   第一个字符   ges   后果   

Leetcode(3)无反复字符的最长子串

[标题表述]:

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

第一种办法:暴力

履行用时:996 ms; 内存消费:12.9MB 后果:太差

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        Maxsize=0
        res=''
        if len(s)==1:Maxsize=1
        for i in range(len(s)):
            for j in s[i:len(s)]:
                if j not in res:res+=j
                else:
                    break
                Maxsize=max(Maxsize,len(res))
            res=''
        return Maxsize

进修

  • 应用一个空串来存储子串

  • for对迭代对象的应用

第二种办法:一个for加切片操作

履行用时:60 ms; 内存消费:12.1MB 后果:异常好

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        res = ''
        maxlen = 0
        for i in s:
            if i not in res:
                res += i
            else:
                maxlen = max(maxlen, len(res))
                index = res.index(i)
                res = res[index + 1:] + i
        return max(maxlen, len(res))

进修

  • 算法有点类似于字符串婚配形式算法KMP

  • 出现反复的移动到反复字符的后一个地位,截取以后持续操作

  • 就不消for+for,只须要用一个for,跟改进婚配算法一样的改进方法

  • 字符串可以+= + 这类重载运算符

  • 切片
    ? [:] 提取从开首(默许地位0)到开头(默许地位-1)的全部字符串

    ? [start:] 从start 提取到开头

    ? [:end] 从开首提取到end - 1

    ? [start:end] 从start 提取到end - 1

    ? [start??step] 从start 提取到end - 1,每step 个字符提取一个

    ? 左边第一个字符的地位/偏移量为0,右边最后一个字符的地位/偏移量为-1

第三种办法:set+滑窗

履行用时:472 ms; 内存消费:12MB 后果:普通

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """


        len_s = len(s)
        if len_s == 0:
            return 0
        set_s = set(s)
        # get the max_size of sild window
        max_len = len(set_s) //
        max_sub_str = ""
        while max_len:
            if max_len == 1:
                return 1
            i = 0
            while i + max_len <= len_s:
                sub_s = s[i:i + max_len]
                set_sub = set(sub_s) //
                # if there is no repeat in sub string
                if len(set_sub) == len(sub_s):
                    max_sub_str = sub_s
                    return(len(list(max_sub_str)))
                i = i + 1
            # adjust the size of window
            max_len = max_len - 1 //

进修

  • 采取python的set,可以知道无反复子串的能够最大年夜值,把能够的最大年夜长度作为滑动窗口的初始大年夜小,在搜刮中调理大年夜小直到找到。

  • set集合 set(s)转化成一个集合 每个字符是个单位 无序的不反复元素序列

  • 一开端就知道无反复的有若干个,然后顺次减去找,无反复的set

  • 这类算法不克不及断定len(s)=0 or 1

Leetcode(3)无反复字符的最长子串

标签:return   初始   不消   else   暴力   集合   第一个字符   ges   后果   

原文地址:https://www.cnblogs.com/ymjun/p/11645088.html

(0)
(0)
   
告发
评论 一句话评论(0
登录后才能评论!
© 2014 mamicode.com 版权一切 京ICP备13008772号-2
迷上了代码!