链表遍历框架，兼具迭代和递归结构

/* 基本的单链表节点 */
class ListNode {
    int val;
    ListNode next;
}
void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 迭代访问 p.val
    }
}
void traverse(ListNode head) {
    // 递归访问 head.val
    traverse(head.next)
}

二叉树遍历框架

• 典型的非线性递归遍历结构

/* 基本的二叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    /* 执行逻辑 1*/
    traverse(root.left);
    /* 执行逻辑 2*/
    traverse(root.right);
    /* 执行逻辑 3*/
}

• 可以扩展为 N 叉树

/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

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

二分搜索树遍历框架

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

深度优先搜索 DFS 模版

借助栈

// 4个移动方向
int xx[4] = {-1, 1, 0, 0}, yy[4] = {0, 0, -1, 1};
int vis[][] = {0};  // 标记是否访问过
int res = 0;        // 方案数
int ex, ey;         // 代表终点的下标

void dfs(int x, int y) {
    if (x == ex && y == ey) {
        res++;
        return;
    }
    vis[x][y] = 1;  // 标记访问过
    for (int i = 0; i < 4; ++i) {
        int nx = x + xx[i];
        int ny = y + yy[i];
        if (!vis[nx][ny] || (nx, ny)不能越界 ) {
            dfs(nx, ny);
        }
    }
    vis[x][y] = 0;  // 取消标记
}

广度优先搜索 BFS 模版

借助队列

// 4个移动方向
int xx[4] = {-1, 1, 0, 0}, yy[4] = {0, 0, -1, 1};
int vis[][] = {0};  // 标记是否访问过
int res = 0;        // 方案数
// 每个位置的信息
struct node {
    int x, y;
    node(int x, int y) : x(x), y(y) {}
};

void bfs(int sx, int sy) {
    queue<node> q;
    q.push(node(sx, sy));   // 将起点放入队列中
    vis[sx][sy] = 1;
    while (!q.empty()) {
        // 取出队列元素(x, y)
        node tmp = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = tmp.x + xx[i];
            int ny = tmp.y + yy[i];
            if ( (nx, ny)合法可以进行搜索 ) {
                走到(nx, ny)的步数 = 走到(tmp.x, tmp.y) + 1;
                q.push(node(nx, ny));
            	vis[nx][ny] = 1;
            }
        }
    }
}

拓扑排序

参考：检测循环依赖

vector<int> haveCircularDependency(int n, vector<vector<int>> &prerequisites) {
    vector<vector<int>> g(n); //邻接表存储图结构
    vector<int> indeg(n); //每个点的入度
    vector<int> res; //存储结果序列
    for(int i = 0; i < prerequisites.size(); i ++) {
        int a = prerequisites[i][0], b = prerequisites[i][1]; 
        g[a].push_back(b);
        indeg[b] ++;
    }
    queue<int> q;
    //一次性将入度为0的点全部入队
    for(int i = 0; i < n; i ++) {
        if(indeg[i] == 0) q.push(i);
    }
    while(q.size()) {
        int t = q.front();
        q.pop();
        res.push_back(t);
        //删除边时，将终点的入度-1。若入度为0，果断入队
        for(int i = 0; i < g[t].size(); i ++) {
            int j = g[t][i];
            indeg[j] --;
            if(indeg[j] == 0) {
                q.push(j);
            }
        }
    }
    if(res.size() == n) return res;
    else return {};
}

滑动窗口算法框架

void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

递归三部曲

1. 明确递归函数的参数和返回值
2. 明确终止条件
3. 明确单层递归的逻辑

回溯三部曲

1. 回溯函数模板返回值以及参数
2. 回溯函数终止条件
3. 回溯搜索的遍历过程

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

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

动规五部曲

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp 数组初始化
4. 确定遍历顺序
5. 举例推导 dp 数组