# 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                     /             \                     [20 15 7] [15 20 7]          /                     20        9                      /  \                                                           /       \                          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                /         \                  [15 20 7]  [15 7 20]              /             \             9              20                           /  \                               """    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)  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)        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, c+d                        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] = r1class 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,e[1:3],e            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.

--

-- ## LORY

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