Skip to content

Instantly share code, notes, and snippets.

Avatar

Ray liyunrui

View GitHub Profile
View 1049. Last Stone Weight II.py
class Solution:
"""
we enumerate all possible combinations when cosidring all stones.
O(2^n)
"""
def lastStoneWeightII(self, stones: List[int]) -> int:
"""
T: O(n*2M), where n =len(stones) and M = sum(stones). At most, we need to caclulate n*M possibilties.
because same path will be casched.
n comes from depth of recursion tree and M comes from at most our left_sum could be.
View 494. Target Sum.py
class Solution:
"""
To clarify:
what's range of S?
what's range of nums? sum(nums) <= 1000 and len(nums) <= 20
"""
def findTargetSumWays(self, nums: List[int], S: int) -> int:
"""
Brute Force
T:O(2^n)
View 545. Boundary of Binary Tree.py
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
"""
Problem Clarification:
Can I assume value of node in the tree is unique? No
View 1740. Find Distance in a Binary Tree.py
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
"""
This code reuses the recursive function from Lowest Common Ancestor of Binary Tree (#236)
View 235. Lowest Common Ancestor of a Binary Search Tree.py
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
"""
For each given current node, we need to determine where to search the common ancestor.
View 1676. Lowest Common Ancestor of a Binary Tree IV.py
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
"""
For each current given root node, we try to find if given nodes in the left subtree and give nodes in the right subtree.
View 1644. Lowest Common Ancestor of a Binary Tree II.py
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
"""
For each current given root node, we try to find p in the left subtree and q in the right subtree.
View 32. Longest Valid Parentheses.py
class Solution:
"""
Greedy+stack:
We use stack to keep track of index of unmatched parentheses.
Top of stack is nearest index of unmatched parenthese.
We traverse the given string forward.
Initally, we put -1 in the stack.
如果又括號就進stack, 左括號就出stack, 然後計算長度
when encounter the open parenthese, we append the index
View 921. Minimum Add to Make Parentheses Valid.py
class Solution:
"""
Greedy+stack:
We use stack to keep track of index of unmatched left parentheses.
Top of stack is nearest index of unmatched left parenthese.
We traverse the given string forward.
when encounter the open parenthese, we append the index
when encounter the close parenthese,
if stack is empty, we need to remove current close parenthese to get valid paretheses
View 84. Largest Rectangle in Histogram.py
class Solution:
"""
Thought Process
Brute Force:
Two pointers:
T: O(n^2)
S: O(1)
Stack:
we use stack to maintain the minimum height on the left side of heights[i].
And, the top of stack is closest index of minimum height.