五大算法代码模板(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)
  1. 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)
  2. –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)
  3. 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)
  4. 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

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

  5. 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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!