基础算法 切题姿势

切题模板，强记！

模板

1. 递归

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(node).
    # ...
    
    for next_node in node.children():
        if not next_node in visited:
            dfs(next_node, visited)

非递归写法

def DFS(self, tree):
    if tree.root is None:
        return []
    
    visited = set()
    stack = [tree.root]
    
    while stack:
        node = stack.pop()
        visited.add(node)
        
        # process(node)
        
        nodes = generate_related_unvisited_nodes(node)
        stack.push(nodes)
        
    # other processing work
    # ...

---

3. BFS代码

def BFS(graph, start, end):
    queue = []
    visited = set()
    
    queue.append([start])
    visited.add(start)
    
    while queue:
        node = queue.pop()
        visited.add(node)
        
        # process(node)
        
        nodes = generate_related_unvisited_nodes(node)
        queue.push(nodes)
        
    # other processing work
    ...

---

4. 二分查找

left, right = 0, len(array) - 1
while left <= right:
    mid = left + (right - left) // 2
    
    if array[mid] == target:
        break or return result
    elif array[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

---

5. DP

# 状态定义
dp = [m + 1][n + 1]

# 初始状态
dp[0][0] = x
dp[0][1] = y
...

# DP状态的推导
for i in range(0, n + 1):
    for j in range(0, m + 1):
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], etc.)
        
return dp[m][n] # 最优解

---

框架

1.回溯算法

result = []
def backtrack(路径， 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        # 做选择
        将该选择从选择列表中移除
        路径.add(选择)
        
        backtrack(路径， 选择列表)
        
        # 撤销选择
        路径.remove(选择)
        将该选择再加入到选择列表中

---

2.计算图中最短距离(BFS)

# 计算从起点start到终点target的最短距离
def BFS(graph, start, target):
	queue = []
	visited = set()
    
    queue.append(start)  # 将起点加入到队列中
    visited.add(start)
    step = 0
    
	while queue:
        for i in range(len(queue)):
            cur_node = queue.pop(0)
            
            if cur_node is target:
                return step
            
            # 将cur_node相邻节点中未被访问的加入队列
            for (node in graph[cur_node]):
                if node not in visited:
                    queue.append(node)
                    visited.add(x)
        # 更新步长 
        step = step + 1

本文作者： Yao Zhu
发布时间： 2020-05-28
最后更新： 2020-09-10
本文链接： https://juoyo.github.io/posts/f81d45b4.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

谢谢你请我吃糖果

支付宝

微信