【Python】【LeetCode】【3.无重复最长字符串】【滑动窗口＆栈】

喜欢ヅ旅行 2022-02-01 12:25 124阅读 0赞

### 文章目录 ###

*   *   *  0.滑动窗口
         *  1.原文题目
         *  2.解题思路
         *  3.Python代码

### 0.滑动窗口 ###

对于刚刚入门计算机小白，接触数据结构和算法，真的头大，刷LeetCode真的痛苦的要死，希望自己能坚持下去，并有所收获！！

**以下是介绍滑动窗口**：  
主要参考[滑动窗口法算法（matlab、java）][matlab_java]和[滑动窗口算法（Sliding Window Algorithm）][Sliding Window Algorithm]以及[Sliding Window Algorithm(滑动窗口算法）分析与实践][Sliding Window Algorithm 1]。建议都可以看看，对滑动窗口算法有个初步的了解！

> What is Sliding Window Algorithm  
> **The Sliding Problem contains a sliding window which is a sub – list that runs over a Large Array which is an underlying collection of elements.**  
> ![滑动窗口示例][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xtMjc4ODU4NDQ1_size_16_color_FFFFFF_t_70]

> 假设有数组\[a b c d e f g h\]  
> 一个大小为3的滑动窗口在其上滑动，则有:  
> \[a b c\]  
> \[b c d\]  
> \[c d e\]  
> \[d e f\]  
> \[e f g\]  
> \[f g h\]

由于自己主要研究图像处理相关算法，对matlab比较钟爱！贴上matlab实现的一个简单示例：

clc;
    clear;
     
    a=[2,3,4,2,6,2,5,1];    % a是数组
    w=3;                               % w是滑动窗口的大小3
    len=length(a);                     % len表示矩阵长度
     
    n=1;
    c=[];
    q=1;
        for i=n:len-w+1  % 遍历 整个矩阵
            b=[a(i),a(i+1),a(i+2)];  
            d=max(b);
            c(q)=d;
            q=q+1; % 更新输出矩阵c的索引号
            n=n+1; % 更新输出矩阵a的索引号
        end  
    c

### 1.原文题目 ###

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

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

示例2

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

示例3

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

### 2.解题思路 ###

> 这道题主要用到思路是：滑动窗口  
> 什么是滑动窗口？  
> 其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

> 如何移动？  
> 我们只要把队列的左边的元素移出就行了，直到满足题目要求！  
> 一直维持这样的队列，找出队列出现最长的长度时候，求出解！  
> 时间复杂度：O(n)

### 3.Python代码 ###

# -*- coding: utf-8 -*- 
    # @Time : 2019/5/14 14:29 
    # @Author : ZXL 
    # @Site :  
    # @File : 3.无重复最长字符串.py 
    # @Software: PyCharm
    class Solution(object):
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            left, right = 0, 0
            chars = set()
            res = 0
            while left < len(s) and right < len(s):
                if s[right] in chars:
                    chars.remove(s[left])
                    left += 1
                else:
                    chars.add(s[right])
                    right += 1
                    res = max(res, len(chars))
            return res
    
    print(Solution().lengthOfLongestSubstring('adcwdfjcv'))    #提交时请删除该行
    
    
    class Solution1(object):
        #此解法为进栈法
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            #获取字符串s对应的列表
            s_to_list = list(s)
            stack = []
            max_length = 0
            for index in s_to_list:
                #如果stack栈中不包含index元素，则可以进栈
                if index not in stack:
                    stack.append(index)
                    max_length = max(max_length, len(stack))
                #如果stack栈中包含index元素，则要将前面index元素之前的数都得拿出栈
                else:
                    start = stack.index(index)
                    stack[:] = stack[start+1:]
                    stack.append(index)
            return max_length
    
    
    if __name__ == "__main__":
        s = "abcabcbb"
        max_str = Solution1().lengthOfLongestSubstring(s)
        print(max_str)

> 使用栈方法来解决。即可用一个栈专门来存储字符串s中不重复的字符，而该栈内不重复字符的个数即是我们需要找的无重复字符的最长子串长度。  
> 我是参考这LeetCode张图片：![进栈法][923a917ae3907645cc3b9febf38f3f10ee0d7002837b5aaa9637e31e0b44b177-image.png_pic_center]

[matlab_java]: https://blog.csdn.net/qq_40260642/article/details/82926133
[Sliding Window Algorithm]: https://blog.csdn.net/lm278858445/article/details/88189212
[Sliding Window Algorithm 1]: https://www.jianshu.com/p/869f6d00d962
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xtMjc4ODU4NDQ1_size_16_color_FFFFFF_t_70]: /images/20220201/864099a8305144238bb3bee311f0aabe.png
[923a917ae3907645cc3b9febf38f3f10ee0d7002837b5aaa9637e31e0b44b177-image.png_pic_center]: /images/20220201/cd75983321d947449a4712f878681959.png