Some paradigms for leetcode questions

[wanghsinche]

• A dfs template

def dfs(root):
  res = []
  if not root:
      return res
  if isSatisfied(root):
      res.append(root.val)
  for ele in root.children:
      left = dfs(ele)
      for i in left:
          res.append(i)
  return res

• A bfs template

def bfs(root):
  res = []
  q = [root]
  while len(q) > 0:
    layer = q
    q = []
    for ele in layer:
         if not ele:
            continue
         if isStatified(ele):
            res.append(ele.val)
         for i in ele.children:
            q.append(i)
   return res

• A binary searching template

def bst(array):
    if len(array) <= 1:
      return isStatified(array)
    left, right = sperate(array)
    if isIn(left):
      return bst(left)
    return bst(right)

[wanghsinche]

• Dynamic programing

To use dynamic programing to solve a problem, there are some steps we can follow with:

1. find out the general term formula
2. use a map or an array to store the results of sub problems
3. iterate the problem from bottom to top, or just recurse it from the top

For example, an iterative method to solve dynamic programing problem:

cache =  dict()
def iter_dp(target):
  ## initial condition
  cache[1] = 1
  cache[2] = 2
  idx = 3
  while idx <= target:
    cache[idx] = f(cache)
  return cache[target]

[wanghsinche]

• sliding window template

  0. set both left and right boundary to be zero
  1. find out the right boundary to meet the condition
  2. shrink the left boundary until left boundary can not meet the condition

  3. save the range if the range is satisfied with all of the conditions.

     
     def sliding(array, condition):
     state = None
     left, right = 0, 0
     while right < len(array):
     updateState(state, array[right])
     # shrink left pointer until the subarray from left to right can not match the condition anymore
     while state with left pointer meets the condition:
        save ans
        left += 1
     # right pointer grows
     right += 1
     
     return all ans

[wanghsinche]

• monotonic stack the top of monotonic stack is always the nearest element that is bigger or smaller than current element from the beginning. By using monotonic stack, we can solve problems like find out the minimum distance of two element, which's difference is bigger than zero, or the largest distance of two element with the difference bigger than zero some best practices are
  1. leetcode 962. Maximum Width Ramp
  2. leetcode 1124. Longest Well-Performing Interval
  3. leetcode 11. Container With Most Water
  4. leetcode 042 Trapping Rain Water[H]

[wanghsinche]

There are a nice resource. https://protegejj.gitbooks.io/my-algorithm-summary/data-structure.html

[wanghsinche]

https://www.techinterviewhandbook.org/ a great coding interview handbook