{{ message }}

Instantly share code, notes, and snippets.

# deque-blog

Created Mar 7, 2020
View trap_water_3.py
 def trap(heights: List[int]) -> int: right_heights = list(heights) for i in reversed(range(len(right_heights)-1)): right_heights[i] = max(right_heights[i], right_heights[i+1]) left_h = 0 total_volume = 0 for i in range(1, len(heights)-1): h = heights[i] left_h = max(heights[i-1], left_h)
Created Mar 7, 2020
View trap_water_2.py
 def trap(heights: List[int]) -> int: left_h = 0 total_volume = 0 for i in range(1, len(heights)-1): h = heights[i] left_h = max(heights[i-1], left_h) right_h = max(heights[i+1:], default=0) volume = max(0, min(left_h, right_h) - h) total_volume += volume return total_volume
Last active Mar 7, 2020
View trap_water_1.py
 def trap(heights: List[int]) -> int: total_volume = 0 for i, h in enumerate(heights): left_h = max(heights[:i], default=0) right_h = max(heights[i+1:], default=0) volume = max(0, min(left_h, right_h) - h) total_volume += volume return total_volume
Created Mar 7, 2020
View maxSubArray.py
 def maxSubArray(nums: List[int]) -> int: max_sum = float('-inf') cum_sum = 0 for num in nums: cum_sum += num if cum_sum >= max_sum: max_sum = cum_sum if cum_sum <= 0: cum_sum = 0 return max_sum
Created Mar 7, 2020
View maxSubArray.py
 def maxSubArray(nums: List[int]) -> int: max_sum = float('-inf') for i in range(len(nums)): cum_sum = 0 for j in range(i, len(nums)): cum_sum += nums[j] if cum_sum > max_sum: max_sum = cum_sum return max_sum
Created Mar 6, 2020
View wordBreak.py
 def wordBreak(self, s: str, wordDict: List[str]) -> bool: if not wordDict: return False word_dict = set(wordDict) smallest_word = min(len(w) for w in wordDict) longest_word = max(len(w) for w in wordDict) @lru_cache(maxsize=None) def can_break_from(i: int) -> bool:
Created Mar 4, 2020
View Regex_expand_selection.py
 def expand_selection(self, states: Set[int]): expanded = set() to_expand = list(states) while to_expand: s = to_expand.pop() expanded.add(s) if s < len(self.nodes) and self.stars[s]: if s+1 not in expanded: states.add(s+1) to_expand.append(s+1)
Last active Mar 4, 2020
View Regex_match.py
 def match(self, s: str) -> bool: current_nodes = { 0 } self.expand_selection(current_nodes) for c in s: next_nodes = set() for s in current_nodes: if s < len(self.nodes): if self.nodes[s] == c or self.nodes[s] == '.': next_nodes.add(s+1) if self.stars[s]:
Last active Mar 4, 2020
View Regex_compile.py
 @classmethod def compile(cls, pattern: str): nodes = [] stars = [] for c in pattern: if c == "*": stars[-1] = True else: nodes.append(c) stars.append(False)
Last active Mar 4, 2020
View Regex_init.py
 @dataclass(frozen=True) class Regex: nodes: List[str] stars: List[bool]