文章目錄
-
-
- 0.滑動視窗
- 1.原文題目
- 2.解題思路
- 3.Python代碼
-
0.滑動視窗
對于剛剛入門計算機小白，接觸資料結構和算法，真的頭大，刷LeetCode真的痛苦的要死，希望自己能堅持下去，并有所收獲！！
以下是介紹滑動視窗：
主要參考滑動視窗法算法（matlab、java）和滑動視窗算法（Sliding Window Algorithm）以及Sliding Window Algorithm(滑動視窗算法）分析與實踐。建議都可以看看，對滑動視窗算法有個初步的了解！
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.
【Python】【LeetCode】【3.無重複最長字元串】【滑動視窗＆棧】
假設有數組[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張圖檔：
【Python】【LeetCode】【3.無重複最長字元串】【滑動視窗＆棧】