leetcode刷题 75 76

举报
毛利 发表于 2021/07/15 07:40:56 2021/07/15
【摘要】 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

  
 
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]

  
 

文章来源: maoli.blog.csdn.net,作者:刘润森!,版权归原作者所有,如需转载,请联系作者。

原文链接:maoli.blog.csdn.net/article/details/90543705

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。