Skip to content

Instantly share code, notes, and snippets.

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)
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
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
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
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
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:
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)
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]:
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)
View Regex_init.py
@dataclass(frozen=True)
class Regex:
nodes: List[str]
stars: List[bool]
You can’t perform that action at this time.