528
个编辑
更改
无编辑摘要
== 使用 pattern ==
== 使用 pattern ==
<ref>[http://www.noteanddata.com/leetcode-3-Longest-Substring-Without-Repeating-Characters-java-sliding-windows-solution-note.html#sliding-windows滑动窗口的特征和基本模版 sliding windows 滑动窗口的特征和基本模版]</ref> <ref>https://blog.csdn.net/fuxuemingzhu/article/details/82931106</ref>
在需要找一个区间的问题中，
'''第一种情况：'''首先移动右指针使得满足要求，再移动左指针直到不满足要求，再移动右指针，持续如此，直到区间的右边界到达整体的结束点。
<syntaxhighlight lang=python>
<syntaxhighlight lang=python>
left = 0
left = 0
init state
ret = worse case retval
ret = worse case retval
for right in range(n):
for right in range(n):
left += 1
left += 1
update state
update state
return ret
</syntaxhighlight>
'''第二种情况：'''首先移动右指针直到不满足要求，再移动左指针直到满足要求，此时记录当前状态，若更优则记录下来。持续如此，直到区间的右边界到达整体的结束点。
<syntaxhighlight lang=python>
left = 0
init state
ret = worse case retval
for right in range(n):
update state
while state is not valid:
left += 1
update state
sol = f(left, right)
if sol is better than ret:
ret = sol
return ret
return ret
</syntaxhighlight>
</syntaxhighlight>
=== [https://leetcode.com/problems/minimum-window-substring/ LeetCode 76. Minimum Window Substring] ===
=== [https://leetcode.com/problems/minimum-window-substring/ LeetCode 76. Minimum Window Substring] ===
第一种情况。Python 解法：
<syntaxhighlight lang=python>
<syntaxhighlight lang=python>
if chars[sl] < target[sl]:
if chars[sl] < target[sl]:
cnt -= 1
cnt -= 1
return ret
</syntaxhighlight>
=== LeetCode 340. Longest Substring with At Most K Distinct Characters ===
第二种情况。Python 解法：
<syntaxhighlight lang=python>
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
left = 0
ret = 0
distinct = 0
chars = Counter()
for right, ch in enumerate(s):
# move the right pointer until the state is invalid
if chars[ch] == 0:
distinct += 1
chars[ch] += 1
while distinct > k and left <= right:
# move the left pointer until the state is valid
c = s[left]
left += 1
chars[c] -= 1
if chars[c] == 0:
distinct -= 1
# after the state becomes valid, record the best result
ret = max(right - left + 1, ret)
return ret
return ret
</syntaxhighlight>
</syntaxhighlight>