五大算法代码模板（DFS 递归非递归都算上，是六个）

这几种算法不仅要理解，更要能背下来伪代码，让这些算法的回想变成O(1)的时间复杂度。

1. Recursion 递归

def recursion(level, param1, param2, ...):
    # recursion terminator
    if level > MAX_LEVEL:
        print_result
        return

    # process logic in current level
    process_data(level, data...)

    # drill down
    self.recursion(level+1, p1, p2, ...)

    # reverse the current level status if needed
    reverse_state(level)

2. DFS(递归写法)

   visited = set()
   def dfs(node, visited)
    visited.add(node)
    # process current node here.
    ...
    for next_node in node.children():
        if not next_node in visited:
            dfs(node, visited)

3. –DFS(非递归写法)

   def dfs(graph, start, end):
    stack = []
    visited = set()
    stack.append(start)
    while stack:
        node = stack.pop()
        visited.add(node)
        # process current node here
        ...
        for next_node in node.children():
            if not next_node in visited:
                stack.append(next_node)

4. BFS

   def bfs(graph, start, end):
    queue = Queue()
    visited = set()
    queue.enqueue(start)
    while queue:
        node = queue.dequeue()
        visited.add(node)
        # process current node here
        ...
        for next_node in node.children():
            if not next_node in visited:
                queue.enqueue(next_node)

5. binary search

   l, r = 0, len(array) - 1
   while l <= r:
    mid = l + (r - l) // 2
    if  array[mid] == target:
        # find the target!
        break or return result
    elif array[mid] < target:
        l = mid + 1
    else:
        r = mid - 1

   二分查找还有几种变形，想法类似。第一个大于、大于等于、小于、小于等于的数

6. DP

   // 状态定义
   dp = new int[m+1][n+1]
   // 初始状态
   dp[0][0] = x;
   dp[0][1] = y;
   ...
   // DP状态推导
   for i  = 0; i <= n; ++i {
    for j = 0; j <=  m; ++j {
        ...
        dp[i][j] = min{dp[i-1][j], dp[i][j-1], etc.}
    }
   }
   return dp[m][n] // 最优解

本作品采用《CC 协议》，转载必须注明作者和本文链接