leetcode 3 无重复字符个数

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

示例 1:

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

示例 2:

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

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

解体答案,这里用到了list作为一个滑动窗口.
window=[1,2,3,4]
当一个新的字符再windows中的时候,就删除这个字符之前的元素,同时插入新字符到行尾.
当新字符不在windows中的时候,直接插入到list尾部.
不停循环的时候,整个过程中出现的windows元素最多的一次,就是最大的无重复的字串.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        maxlen=0
        window=[]
        for i in s:
            if i not in window:
                window.append(i)
                maxlen=max(len(window),maxlen)
            else:
                x1 = window.index(i)
                window=window[x1+1:]
                window.append(i)
                maxlen=max(len(window),maxlen)
        return maxlen

但是运行结果内存使用不是很理想:
执行结果:
通过
显示详情
执行用时 :80 ms, 在所有 Python3 提交中击败了82.75% 的用户
内存消耗 :13.9 MB, 在所有 Python3 提交中击败了5.01%的用户
所以应该还有优化空间,再网上看了下别人写的代码,可以通过dict来替代list,这样占用空间会更小一点.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        maxlen=0
        strdict={}
        window=[0,0]
        j=0
        for i in s:
            if i in strdict:
                # print(j)
                # print(i)
                # print(strdict)
                if window[0] <= strdict[i]:
                    window[0] = strdict[i]+1

            strdict[i]=j
            window[1]=j
            # print(strdict)
            # print(window)
            j=j+1
            maxlen=max(window[1]+1-window[0],maxlen)



        return maxlen

不过貌似并没有什么改善:
行结果:
通过
显示详情
执行用时 :72 ms, 在所有 Python3 提交中击败了92.77% 的用户
内存消耗 :14 MB, 在所有 Python3 提交中击败了5.01%
然后参考网上教程用go写了个

func lengthOfLongestSubstring(s string) int {
    window ,start:= 0,0


    for i:=0;i<len(s);i++{
        isexit :=strings.Index(string(s[start:i]),string(s[i]))
        if isexit == -1{
            window = Maxint(window,i - start +1)
        }       else{
            start = start + isexit +1
        }
        window = Maxint(window,i - start +1)

    }
     return window
}
func Maxint(x,y int) int {
    if x >y{
        return x
    }else{
        return y 
    }
}

执行用时 :4 ms, 在所有 golang 提交中击败了92.27% 的用户
内存消耗 :2.6 MB, 在所有 golang 提交中击败了93.74%的用户
时间比较感人,用python重写看下时间方面是不是会增加点.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window =0
        start = 0
        j=0
        for k in s :
            isexist = s[start:j].find(k)
            if isexist == -1:
               window = max(window,j-start+1)
            else:
                start = start+isexist +1    
            j=j+1
        return window

执行用时 :56 ms, 在所有 python3 提交中击败了99.64% 的用户
内存消耗 :13.9 MB, 在所有 python3 提交中击败了5.01%的用户
然而并没有什么长进..

About: loony


发表评论

电子邮件地址不会被公开。 必填项已用*标注

Captcha Code