After solved 1000 medium leetcode found these patterns — UnionFind, Devide And Conquer, Toposort

Devide and conquer

The core idea is split the problem into sub problems and keep merging the sub-answers into final answer . do not confuse with DP , they are very different. D and C split the problem into half-half, then 1/4 and 1/8, etc, and “merge” the 1/4 answers into “half” answer, then merge the half-half into final answer. in short, it is split input into half , recursive and merge . it is a very powerful idea .

def solve(input):
if break_condition:
return
// do something with input[index]
solve(input[:index])
solve(input[index+1:])
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
"""
first element in preorder is the root
the find the root's index in inorder. [left], [right] will be the sub trees
Sample :
[3 9 20 15 7] [9 3 15 20 7]
3
/ \
[9] [9] [20 15 7] [15 20 7]
/ 20
9 / \
[15] [7]
/ \
15 7
"""
def build(p, i):
if not p:
return None
r = TreeNode(val=p.pop(0))

idx = i.index(r.val)

r.left = build(p[:idx], i[:idx+1])
r.right = build(p[idx:], i[idx+1:])
return r

return build(preorder, inorder)
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
"""
Similar to #105 (construct from inoder and preorder)
in postorder , last element is the root
find the index in inoder ,[left] and [right] is sub tree. repeat the same
[9 3 15 20 7] [9 15 7 20 3]
3
/ \
[9] [9] [15 20 7] [15 7 20]
/ \
9 20
/ \
[15] [7]
"""
def build(p, i):
if not p :
return None
root = TreeNode(p.pop())
idx = i.index(root.val)
root.left = build(p[:idx], i[:idx])
root.right = build(p[idx:], i[idx+1:])
return root
return build(postorder, inorder)
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
def gen(left, right):
nonlocal n
if left > right :
return [None]

trees=[]
for i in range(left, right+1):
# use every node as root
l_tree=gen(left, i-1)
r_tree=gen(i+1, right)
# add each combination of left and tree sub tree
for l in l_tree:
for r in r_tree:
root = TreeNode(i)
root.left = l
root.right = r
trees.append(root)
return trees

return gen(1, n)
def diffWaysToCompute(self, expression: str) -> List[int]:
"""
Sample1 : 2*3-4 =>

* -
/ \ / \
2 - * 4
/ \ / \
3 4 2 3
let Tree(2*3-4) = result of 2*3-4

Sample2 : 2*3-4*5 =>
* * -
/ \ / \ / \
2 Tree(3-4*5) Tree(2*3-4) 5 * *
/ \ / \
2 3 4 5
"""
def val(left, right, operator):
if operator == '+':
return left+right
elif operator == '-':
return left-right
else:
return left*right
@cache # Cache result
def dwc(exp):
if all(e not in ['+', '-', '*'] for e in exp):
return [int(exp)]
res=[]
for i, e in enumerate(exp): # Loop through expression
if e not in ['+', '-', '*']: # Skip numbers
continue
left = dwc(exp[:i]) # Try put every operator as root node
right = dwc(exp[i+1:])
for l in left:
for r in right:
res.append(val(l, r, e))
return res
return dwc(expression)

Union Find

Even there are not a lot problems on leetcode, but this is a very useful algorithm .

class UF:
def __init__(self, row, col, grid):
self.parent = {}
#initialize parent values

def union(self, n1, n2):
p1, p2 = self.find(n1), self.find(n2)
if p1 != p2:
self.parent[p1] = p2

def find(self, node):
p = self.parent[node]
if p == node:
return node
return self.find(p)
def numIslands(self, grid: List[List[str]]) -> int:
"""
Idea :
when there is '1', DFS mark the connected '1' as '2'
num of islands = How many times DFS can do
"""

row, col = len(grid), len(grid[0])
def mark(grid, r, c):
if r < 0 or c < 0 or r == row or c == col or grid[r][c] != '1':
return
grid[r][c] = '2'
mark(grid, r-1, c)
mark(grid, r+1, c)
mark(grid, r, c-1)
mark(grid, r, c+1)

res=0
for r in range(0, row):
for c in range(0, col):
if grid[r][c] == '1':
res+=1
mark(grid, r, c)

return res
class UF:
def __init__(self, row, col, grid):
self.parent = {} # {(row, col): (parent_row, parent_col) }
self.count = 0 # track num of islands
for r in range(row):
for c in range(col):
if grid[r][c] == '1': # only store parent for island
self.parent[(r,c)]=(r,c) # every island parent point to self first
self.count+=1

def union(self, n1, n2): # n1, n2 : (row, col)
p1, p2 = self.find(n1), self.find(n2)
if p1 != p2: # merge 2 parents. it doesn't matter which will be new parent
self.parent[p1] = p2
self.count -= 1

def find(self, node):
p = self.parent[node]
if p == node:
return node
return self.find(p)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
"""
Idea :
when there is '1' ,check and union the left/right/up/down '1'
"""

row, col = len(grid), len(grid[0])
uf = UF(row, col, grid)
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def valid(r, c, row, col, grid):
if r < 0 or c < 0 or r == row or c == col or grid[r][c] == '0':
return False
return True

for r in range(0, row):
for c in range(0, col):
if grid[r][c] == '1':
for d in dirs:
r1, c1 = r+d[0], c+d[1]
if not valid(r1, c1, row, col, grid):
continue
uf.union((r, c), (r1, c1))
return uf.count
class UF:
def __init__(self):
self.parent = {}
def find(self, n):
if n not in self.parent:
return n
return self.find(self.parent[n])
def union(self, r1, r2):
self.parent[r2] = r1
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
equations.sort(key=lambda x:x[1:3], reverse=True)
uf = UF()
for e in equations:
e1,op,e2 = e[0],e[1:3],e[3]
root1 = uf.find(e1)
root2 = uf.find(e2)
if op == '==':
if root1 == root2:
continue
uf.union(root1, root2)
else:
if root1 == root2:
return False
return True

Toposort

When we deal with graph , toposort is important algorithm to remove nodes by such sequence : remove each node if degree = 0 (no input or output node)

def solve():
res=[]
g = build_graph() # <node: next_nodes>
while g:
nodes = [k for k in g.keys() if len(g[k]) == 0]
if not nodes:
break
# do something
for n in nodes:
for neighbor in g[n]:
g[neighbor].remove(n) # remove self from neighbor nodes
del g[n]
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
pre = prerequisites
dependencies = {i:set() for i in range(0, numCourses)}
for k,v in pre:
dependencies[k].add(v)

while len(dependencies.keys())>0 :
# find the courses has no dependency
no_dependency = [x for x in dependencies.keys() if len(dependencies[x]) == 0]
if not no_dependency :
return False
for c in no_dependency:
# finish each course, remove it from all course dependency list
for k, dep in dependencies.items():
if c in dep:
dep.remove(c)
del dependencies[c]
return True

Conclusion

All these 3 Algorithms are just ideas of leetcode problems , however the real power behind them are much deep than what covered above.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
LORY

LORY

A Senior Software Developer/Body builder . to help others enjoy coding and stay healthy