leetcode刷题 75 76
【摘要】
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.i...
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
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
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
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
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]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。
原文链接：maoli.blog.csdn.net/article/details/90543705
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）