一、双指针

• fast、slow 快慢指针，slow 走一步，fast 走两步：
  • 在环形链表中能解决相遇问题；
  • 在非环形链表中能解决中点问题；
• fast、slow 一前一后：
  • 在非环形链表中，可以解决 k 距离问题，倒数第 k 个节点问题；
• 滑动窗口问题：
  • 疑难点：如何判断窗口的收缩条件

  // 滑动窗口算法伪码框架
  func slidingWindow(s string) {
      // 用合适的数据结构记录窗口中的数据，根据具体场景变通
      // 比如说，我想记录窗口中元素出现的次数，就用 map
      // 如果我想记录窗口中的元素和，就可以只用一个 int
      var window = ...
  
      left, right := 0, 0
      for right < len(s) {
          // c 是将移入窗口的字符
          c := rune(s[right])
          window[c]++
          // 增大窗口
          right++
          // 进行窗口内数据的一系列更新
          ...
  
          // 判断左侧窗口是否要收缩
          for left < right && window needs shrink { //replace "window needs shrink" with actual condition
              // d 是将移出窗口的字符
              d := rune(s[left])
              window[d]--
              // 缩小窗口
              left++
              // 进行窗口内数据的一系列更新
              ...
          }
      }
  }
  

• 左右指针相向而行：

二、回溯

• 疑难点：如何做出选择以及提前剪枝；
• 决策树遍历时的基本模型：
  • 1、路径：就是已经做出的选择。
  • 2、选择列表：就是当前可以做的选择。
  • 3、剪枝条件：就是过滤不合法的节点，避免走回头路和重复。
  • 4、结束条件：就是到达决策树底层，无法再做选择的条件。

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

• 其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」；
• 常见题型：
  • 排列组合问题、子集问题、N皇后问题、数独问题；
  • 球盒模型，分别为「球」的视角穷举和「盒」的视角穷举，对应两种不同的代码写法。

三、多叉树回溯

void backtrack(Node root) {
    if (root == null) {
        return;
    }

    for (Node child : root.children) {
        // 做选择
        printf("我在 %s 和 %s 中间的树枝上做选择", root, child);

        backtrack(child);

        // 撤销选择
        printf("我在 %s 和 %s 中间的树枝上撤销选择", root, child);
    }
}

四、多叉树DFS

// DFS 算法框架模板
void dfs(Node root) {
    if (root == null) {
        return;
    }
    // 做选择
    printf("我在 %s 节点上做选择", root);

    for (Node child : root.children) {
        dfs(child);
    }

    // 撤销选择
    printf("我在 %s 节点上撤销选择", root);
}

• 回溯算法的关注点在「树枝」，DFS 算法的关注点在「节点」。

五、网格DFS

• 整体思想：遍历到某个节点时，递归遍历其周围节点，沿着某个方向直至到边界节点，再逐步返回，重复该步骤；
• 遍历到当前节点的第一个周围节点时，继续递归遍历该周围节点的周围节点，直到最后一个节点（边界节点）；
• 遍历到最后一个节点时，依次遍历其所有的周围节点，直到该节点的所有周围节点都遍历完成，再逐步返回；
• 遍历倒数第二个节点的第二个周围节点，直到倒数第二个节点的所有周围节点都遍历完成，再逐步返回；
• 不断重复上述部分，直至返回到当前节点，再继续遍历当前节点的第二个周围节点，继续重复上述步骤，直到当前节点的所有周围节点遍历完成；
• 继续遍历与当前节点同级的下个节点，直到所有节点遍历完成；
• 在这个遍历过程中，不同节点的周围节点可能存在重复的情况，需要记录节点是否已经被遍历过，避免重复遍历；

// 二维矩阵遍历框架
func dfs(grid [][]int, i, j int, visited [][]bool) {
    m, n := len(grid), len(grid[0])
    if i < 0 || j < 0 || i >= m || j >= n {
        // 超出索引边界
        return
    }
    if visited[i][j] {
        // 已遍历过 (i, j)
        return
    }

    // 进入当前节点 (i, j)
    visited[i][j] = true

    // 进入相邻节点（四叉树）
    // 上
    dfs(grid, i - 1, j, visited)
    // 下
    dfs(grid, i + 1, j, visited)
    // 左
    dfs(grid, i, j - 1, visited)
    // 右
    dfs(grid, i, j + 1, visited)
}

六、网格BFS

• 整体思想：遍历到某个节点时，遍历其周围节点，先把周围所有的节点都遍历完，再遍历下个节点，重复该步骤遍历其周围节点；
• 遍历到第一个节点时，将其所有的周围节点加入到某个队列中，这个队列表示下一次应该要遍历完的节点；
• 在遍历该队列中的节点时，依次将队列中的每个节点的周围节点继续加入一个队列中，表示下一次应该要遍历的节点；
• 不断重复上述步骤，直到队列中的所有节点都已经遍历完成；
• 继续遍历第二个节点，重复上述步骤，直到所有节点遍历完成；
• 在这个遍历过程中，不同节点的周围节点可能存在重复的情况，需要记录节点是否已经被遍历过，避免重复遍历；

// 计算从起点 start 到终点 target 的最近距离
func BFS(start Node, target Node) int {
    q := make([]Node, 0) // 核心数据结构
    visited := make(map[Node]bool) // 避免走回头路
  
    q = append(q, start) // 将起点加入队列
    visited[start] = true
    step := 0

    for len(q) > 0 {
        sz := len(q)
        /* 将当前队列中的所有节点向四周扩散 */
        for i := 0; i < sz; i++ {
            cur := q[0]
            q = q[1:]
            /* 划重点：这里判断是否到达终点 */
            if cur == target {
                return step
            }
            /* 将 cur 的相邻节点加入队列 */
            for _, x := range cur.adj() {
                if _, ok := visited[x]; !ok {
                    q = append(q, x)
                    visited[x] = true
                }
            }
        }
        step++
    }
    // 如果走到这里，说明在图中没有找到目标节点
    return step
}

func dfs(grid [][]int, r, c int) {
    // 判断 base case
    // 如果坐标 (r, c) 超出了网格范围，直接返回
    if (!inArea(grid, r, c)) {
        return;
    }

    // 避免重复
    if (grid[r][c] != 1) {
        // 如果这个格子已经遍历过直接返回
        return;
    }
    grid[r][c] = 2; // 将格子标记为「已遍历过」

    // 访问上、下、左、右四个相邻结点
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
func inArea(grid [][]int, r, c int) bool {
    return 0 <= r && r < len(grid)
        	&& 0 <= c && c < len(grid[0]);
}

七、二叉树BFS

// TODO
func traverse(root *TreeNode) {
    // 判断 base case
    if (root == nil) {
        return;
    }
    // 访问两个相邻结点：左子结点、右子结点
    traverse(root.left);
    traverse(root.right);
}

八、动态规划

• 疑难点：如何列出状态转移方程

# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)