LeetCode进阶之路（三）算法题的核心套路

一、框架思维

1.数据结构存储方式

　　数据结构底层存储方式有两种：数组和链表（即顺序存储和链式存储）。

2.树的遍历框架

//二叉树遍历框架
class TreeNode{
    int val;
    TreeNode left,right;
}

public void traverse(TreeNode root){
    //前序遍历
    traverse(root.left);
    //中序遍历
    traverse(root.right);
    //后序遍历
    
}

//n叉树比遍历框架
class TreeNode{
int val;
TreeNode[] children;
}

void traverse(TreeNode root){
for(TreeNode child:root.children){
traverse(child);
　　}
}

注：涉及递归的问题，基本都是树的问题。

二、动态规划解题框架

（一）概述

1.动态规划通常是求最值的问题。核心问题是穷举。

2.重叠子问题：使用备忘录或DPtable优化穷举。

3.最优子结构：通过子问题的最值得到原始问题的最值。

4.状态转移方程（分段函数）：状态、选择、dp的定义。（思考最简单情况、问题的状态有什么、对每个状态可以进行什么操作得到什么新的状态、如何定义dp数组或函数来表现“状态”和“选择”。）

框架如下：

//初始化base case
dp[0][0][···]=base case
//进行状态转移
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ···
            dp[状态1][状态2][···]=求最值(选择1，选择2，···)

（二) 具体方法：

1.暴力递归

　　递归算法的时间复杂度：子问题个数乘以解决单个子问题需要的时间。

2.带备忘录的递归解法

　　一般用一个数组充当备忘录，也可以使用哈希表（字典），将子问题的答案记录在备忘录内，需要时直接取出来，就不用再耗时计算了。

3.dp数组的迭代解法

　　用一个独立的数组表示备忘录。如果当前状态之和前几个状态有关，可以用多个变量表示dpTable——状态压缩。

三、回溯算法解题套路框架（DFS深度优先搜索）

　　回溯方法即穷举，解决回溯问题就是决策树遍历的问题。具体包括：

　　1.路径：已经做出的选择。

　　2.选择列表：当前可以做的选择。

　　3.结束条件：到达决策树底层无法再做选择的条件。

　　回溯算法是动态规划的暴力求解阶段。

　　回溯算法是一个多叉树遍历的问题，关键是前序遍历和后序遍历位置的操作。写Backtrack函数时，需要维护走过的“路径”和当前可以做的“选择列表”，当触发“结束条件”时，将“路径”计入结果集。

回溯算法的况下如下：

result=[]
def backtrack(路径,选择列表);
    if 满足结束条件
        result.add(路径);
        return;
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径,选择列表)
        撤销选择

for循环中的递归在条用之前做选择，在调用递归之后撤销选择。

　　维护节点的选择列表和路径的方法：在递归之前做出选择，在递归之后撤销刚才的选择。

四、BFS广度优先搜索算法框架

　　核心思想：把问题想象成图，从一个点开始向四周扩散。每次将一个节点周围的所有节点加入队列。

　　BFS的特点：BFS找到的路径是最短的，但空间复杂度比DFS大得多。

　　应用场景：在一个图中，找到从起点到终点的最短距离。

　　算法框架如下所示：

//计算从起点到终点的最短距离
int BFS(Node start,Node target){
        Queue q; //核心数据结构
        Set visited; //避免走回头路

        q.offer(start); //将起点加入队列
        visited.add(start);
        int step=0; //记录扩散的步数

        while(q not empty){
        int sz=q.size();
//        将队列中的所有节点向四周扩散
        for(int i=0;i){
        Node cur=q.pool();
//            这里判断是否到达终点
        if(cur is target)
        return step;
//            将cur的相邻接点加入到队列，cur.adj()指cur相邻的节点
        for(Node X:cur.adj()){
        if(x not in visited){
        q.offer(x);
        visited.add(x);  //visited是防止走回头路，一般的二叉树没有子节点到父节点的指针，不需要visited
        }
        }
        }
//        在这里更新步数
        step++;
        }
        }

BFS和DFS的关系

1.寻找最短路径时，广度优先相当于面，深度优先相当于线，深度优先也可以找到最短路径。

2.DFS空间复杂度小，时间复杂度大。BFS空间复杂度大，时间复杂度小。