leetcode刷题7576

class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ i = 0 for _ in range(len(nums)): if nums[i] == 0: nums.insert(nums.pop(i), 0) i += 1 elif nums[i] == 2: nums.append(nums.pop(i)) else: i += 1 class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ s, e = 0 , len(nums)-1 i = 0 while i <= e: if nums[i] == 0: nums[s], nums[i] = nums[i], nums[s] s, i = s+1, i+1 elif nums[i] == 1: i = i+1 elif nums[i] == 2: nums[i], nums[e] = nums[e], nums[i] e = e-1 return

o（n）解法

from collections import Counter class Solution: def minWindow(self, text, pat): '''Find the minimum window covering a pattern possibly with duplicate tokens. T(t, p) = O(t) S(t, p) = O(p) ''' n = len(text) j = 0 orig = Counter(pat) have = Counter() rem = set(pat) sub = '' for i in range(n): while rem and j < n: # expand right to cover pat ch = text[j] if ch in orig: have[ch] += 1 if have[ch] >= orig[ch] and ch in rem: rem.remove(ch) j += 1 if rem and j == n: break if not rem and ((not sub) or j-i < len(sub)): sub = text[i:j] ch = text[i] have[ch] -= 1 if ch in orig and have[ch] < orig[ch]: rem.add(ch) return sub #滑动窗口 class Solution: def minWindow(self, s: str, t: str) -> str: d = {} for c in t: d[c] = d.get(c,0) + 1 ToFind, ind = len(t), [] L, R, head = -len(s)-1, -1, 0 for i, c in enumerate(s): if c in d: ind.append(i) d[c] -= 1 if d[c] >=0: ToFind -= 1 if ToFind == 0: while d[s[ind[head]]] < 0: # s[ind[head]] is the character d[s[ind[head]]] += 1 head += 1 if i - ind[head] < R - L: L, R = ind[head], i d[s[ind[head]]] += 1 ToFind += 1 head += 1 return s[L:R+1] 刘润森！ 认证博客专家 Python Java 前端 17年就读于东莞XX学院化学工程与工艺专业，GitChat作者。Runsen的微信公众号是"Python之王"，因为Python入了IT的坑，从此不能自拔。公众号内容涉及Python，Java计算机、杂谈。干货与情怀同在。喜欢的微信搜索：「Python之王」。个人微信号：RunsenLiu。不关注我公号一律拉黑！！！