labuladong 算法笔记 — 算法套路与解题框架总结

来源：labuladong 的算法笔记
核心定位：模板化、框架化的思维模式，稳定复现 85 分水平

一、速成学习路线图

1.1 整体结构

数据结构基础 → 核心框架总纲 → 链表双指针 → 数组双指针
  → 滑动窗口 → 二分搜索 → 前缀和/差分 → 队列/栈/单调栈/单调队列
  → 二叉树 & 递归思想 → 二叉搜索树 → 图算法
  → DFS/回溯算法 → BFS 算法 → 动态规划 → 贪心/分治 → 数学技巧

1.2 建议用时（速成版）

二、核心思维框架（第零章）

2.1 学习数据结构和算法的框架思维

📎 文章：https://labuladong.online/zh/algo/essential-technique/algorithm-summary/

核心结论

• 数据结构本质：一切数据结构都是数组（顺序存储）和链表（链式存储）的变换与上层封装
• 算法本质：穷举。两个关键难点——无遗漏（靠框架保证）和无冗余（靠信息剪枝）

数据结构操作框架

任何数据结构操作 = 遍历 + 访问（增删查改）：

数组遍历 → for 循环迭代
链表遍历 → 指针迭代 或 递归
二叉树遍历 → 前/中/后序递归
N叉树/图遍历 → 递归 + visited 标记

两种核心思维模式

通用代码框架

// 数组遍历
void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) { /* 迭代访问 */ }
}

// 链表遍历（迭代）
void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) { /* 访问 */ }
}

// 链表遍历（递归）
void traverse(ListNode head) {
    if (head == null) return;
    traverse(head.next);  // 后序位置处理
}

// 二叉树递归遍历（根本大法）
void traverse(TreeNode root) {
    if (root == null) return;
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

// BFS/层序遍历框架
void levelTraverse(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            // 处理当前节点
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
    }
}

算法知识图谱

数组双指针 → 滑动窗口 → 二分搜索 → 前缀和/差分数组
链表双指针 → 快慢指针（环检测/中点）
二叉树 → 回溯算法 → 排列/组合/子集 → BFS
二叉树 → 图论（环判断/拓扑排序/二分图/Dijkstra）
二叉树 → 动态规划（分解问题思维） → 空间压缩优化

核心方法："刷一道题获得刷十道题的效果"——培养框架思维，看穿题目本质。

2.2 一个视角 + 两种思维模式搞定递归

📎 文章：https://labuladong.online/zh/algo/essential-technique/understand-recursion/

核心思想

理解和编写递归最有效的方法是从**「树」的视角**出发。递归函数的执行过程对应一棵递归树的遍历，每个递归调用对应树上的一个节点。

两种思维模式

// 遍历模式（回溯）
List<List<Integer>> res = new LinkedList<>();
List<Integer> track = new LinkedList<>();

void backtrack(int[] nums) {
    if (track.size() == nums.length) {
        res.add(new LinkedList<>(track));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        track.add(nums[i]);  // 做选择
        used[i] = true;
        backtrack(nums);
        track.removeLast();  // 撤销选择
        used[i] = false;
    }
}

// 分解问题模式
// 定义：输入一个节点，返回以该节点为根的二叉树的最大深度
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    return 1 + Math.max(leftMax, rightMax);  // 后序位置
}

编写递归的三步法

1. 判断：问题能否抽象成树结构？→ 用递归
2. 选择：适合「遍历」还是「分解问题」？
3. 编码：分解问题→写清楚函数定义；遍历→无返回值，收集结果

2.3 二叉树系列算法核心纲领

📎 文章：https://labuladong.online/zh/algo/essential-technique/binary-tree-summary/

前中后序位置的本质

不是三种顺序不同的列表，而是遍历过程中三个特殊时间点：

核心原则：如果题目和子树有关，大概率要给函数设置合理的定义和返回值，在后序位置写代码。

两种思维模式在二叉树中的具象化

遍历思维 → traverse(root) 无返回值 + 外部变量（累加/比较/收集）
分解问题思维 → f(root) 有返回值，由子树推导（后序位置）

快速排序 vs 归并排序

三大算法在二叉树视角下的统一

三、经典数据结构算法（第一章）

3.1 双指针技巧 — 链表

📎 文章：https://labuladong.online/zh/algo/essential-technique/linked-list-skills-summary/

链表双指针七大技巧

// 合并两个有序链表
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1), p = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val > l2.val) { p.next = l2; l2 = l2.next; }
        else { p.next = l1; l1 = l1.next; }
        p = p.next;
    }
    p.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

// 链表倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head, p2 = head;
    for (int i = 0; i < k; i++) p1 = p1.next;
    while (p1 != null) { p1 = p1.next; p2 = p2.next; }
    return p2;
}

// 环形链表检测 + 找环起点
ListNode detectCycle(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    if (fast == null || fast.next == null) return null;
    slow = head;
    while (slow != fast) { slow = slow.next; fast = fast.next; }
    return slow;
}

// 相交链表
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode p1 = headA, p2 = headB;
    while (p1 != p2) {
        p1 = (p1 == null) ? headB : p1.next;
        p2 = (p2 == null) ? headA : p2.next;
    }
    return p1;
}

复杂性：除合并K个有序链表 O(N log k) 外，其余均为 O(N)，空间 O(1)。

链表进阶技巧

回文链表（LeetCode 234）：快慢指针找中点 → 反转后半部分 → 逐节点比较。最优 O(n) 时间、O(1) 空间。

boolean isPalindrome(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    if (fast != null) slow = slow.next; // 奇数长度
    ListNode left = head, right = reverse(slow);
    while (right != null) {
        if (left.val != right.val) return false;
        left = left.next; right = right.next;
    }
    return true;
}

反转链表 — 四种变体统一模板：

// 1. 反转整个链表（迭代） — O(n), O(1)
ListNode reverse(ListNode head) {
    ListNode pre = null, cur = head;
    while (cur != null) {
        ListNode nxt = cur.next;
        cur.next = pre;
        pre = cur; cur = nxt;
    }
    return pre;
}

// 2. 反转整个链表（递归） — O(n), O(n)
ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode last = reverseList(head.next);
    head.next.next = head; head.next = null;
    return last;
}
TreeNode successor = null; // 后继节点

// 3. 反转前 N 个节点 — 记录第 N+1 个节点为 successor
ListNode reverseN(ListNode head, int n) {
    if (n == 1) { successor = head.next; return head; }
    ListNode last = reverseN(head.next, n - 1);
    head.next.next = head;
    head.next = successor;
    return last;
}

// 4. 反转 [m, n] 区间 → 递归定位到 m，调用 reverseN
// 5. K个一组反转 → 分组：先反转前K个，剩余递归

3.2 双指针技巧 — 数组

📎 文章：https://labuladong.online/zh/algo/essential-technique/array-two-pointers-summary/

数组双指针分类

// 快慢指针 — 原地删除重复元素
int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 0, fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
        fast++;
    }
    return slow + 1;
}

// 快慢指针 — 移动零
void moveZeroes(int[] nums) {
    int slow = 0, fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != 0) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    for (int i = slow; i < nums.length; i++) nums[i] = 0;
}

// 左右指针 — 两数之和 II（有序数组）
int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) return new int[]{left + 1, right + 1};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1};
}

// 左右指针 — 最长回文子串（中心扩展法）
String longestPalindrome(String s) {
    String res = "";
    for (int i = 0; i < s.length(); i++) {
        String s1 = palindrome(s, i, i);     // 奇数长度
        String s2 = palindrome(s, i, i + 1); // 偶数长度
        res = res.length() > s1.length() ? res : s1;
        res = res.length() > s2.length() ? res : s2;
    }
    return res;
}
String palindrome(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        l--; r++;
    }
    return s.substring(l + 1, r);
}

时间复杂度：最长回文 O(n²)，其余均为 O(n)。

二维数组遍历技巧

旋转矩阵（LeetCode 48）：两步翻转法——先对角线转置，再每行左右翻转。原地 O(1) 空间。

void rotate(int[][] matrix) {
    int n = matrix.length;
    // 1. 转置（沿主对角线镜像）
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            swap(matrix, i, j, j, i);
    // 2. 每行左右翻转
    for (int[] row : matrix) reverse(row);
}
// 逆时针 90 度：转置后上下翻转每列

螺旋遍历矩阵（LeetCode 54）：设置上下左右四个边界，按 右→下→左→上 顺序遍历并收缩边界。

3.3 滑动窗口算法

📎 文章：https://labuladong.online/zh/algo/essential-technique/sliding-window-framework/

核心思想

专门解决子数组/子串问题。维护一个窗口，通过 right 指针扩大、left 指针缩小，在 O(N) 时间内穷举所有满足条件的子串。

通用代码模板

void slidingWindow(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    while (right < s.length()) {
        // 1. 扩大窗口
        char c = s.charAt(right);
        right++;
        window.put(c, window.getOrDefault(c, 0) + 1);
        // 更新窗口内数据...

        // 2. 收缩窗口（debug 输出位置）
        while (left < right && 需要收缩的条件) {
            // 3. 缩小窗口
            char d = s.charAt(left);
            left++;
            window.put(d, window.get(d) - 1);
            // 更新窗口内数据...
        }

        // 4. 更新答案（依题而定，可能在扩大阶段或收缩阶段）
    }
}

设计滑动窗口模板只需回答三个问题：

1. 何时移动 right 扩大窗口？加入字符时更新哪些数据？
2. 何时开始移动 left 缩小窗口？移出字符时更新哪些数据？
3. 何时更新结果？

四道经典题适配

时间复杂度：O(N)，每个元素入窗一次、出窗一次。

3.4 二分搜索算法

📎 文章：https://labuladong.online/zh/algo/essential-technique/binary-search-framework/

核心原则

1. 搜索区间为空时停止
2. 搜索过程中不能漏掉元素

统一框架（两端都闭）

// 寻找一个数
int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else if (nums[mid] > target) right = mid - 1;
    }
    return -1;
}

// 寻找左侧边界
int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) right = mid - 1;  // 收缩右边界
        else if (nums[mid] < target) left = mid + 1;
        else if (nums[mid] > target) right = mid - 1;
    }
    if (left >= nums.length || nums[left] != target) return -1;
    return left;
}

// 寻找右侧边界
int rightBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) left = mid + 1;  // 收缩左边界
        else if (nums[mid] < target) left = mid + 1;
        else if (nums[mid] > target) right = mid - 1;
    }
    if (right < 0 || nums[right] != target) return -1;
    return right;
}

时间复杂度：O(log N)。适用条件：数据有序且支持随机访问。

二分搜索实际运用思维框架

泛化到求最值问题（最小速度、最低运载能力等），核心是找到单调函数 f(x) 和目标 target。

三步法：①确定 x, f(x), target → ②找 x 取值范围(左右边界) → ③判断单调性

// 抽象模板：在 f(x) 单调递增时找最小 x 使 f(x) >= target
int left = min_x, right = max_x;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (f(mid) >= target) right = mid - 1; // 收缩右边界
    else left = mid + 1;
}
return left;

3.5 前缀和与差分数组

📎 文章：
https://labuladong.online/zh/algo/data-structure/prefix-sum/
https://labuladong.online/zh/algo/data-structure/diff-array/

前缀和数组

核心思想：空间换时间，构建 preSum 数组使区间求和降为 O(1)。

// 一维前缀和
class NumArray {
    int[] preSum;
    public NumArray(int[] nums) {
        preSum = new int[nums.length + 1];
        for (int i = 1; i < preSum.length; i++)
            preSum[i] = preSum[i - 1] + nums[i - 1];
    }
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

// 二维前缀和
// 构造：preSum[i][j] = preSum[i-1][j] + preSum[i][j-1]
//                     + matrix[i-1][j-1] - preSum[i-1][j-1]
// 查询 [x1,y1] 到 [x2,y2]：
// sum = preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]

局限性：数组不可变，需要逆运算（求最大值不可用前缀和）。

差分数组

核心思想：频繁对区间进行增减操作时，将区间修改降为 O(1)。

class Difference {
    private int[] diff;

    public Difference(int[] nums) {
        diff = new int[nums.length];
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++)
            diff[i] = nums[i] - nums[i - 1];
    }

    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) diff[j + 1] -= val;
    }

    public int[] result() {
        int[] res = new int[diff.length];
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++)
            res[i] = res[i - 1] + diff[i];
        return res;
    }
}

典型题目：

• 370. 区间加法（直接模板）
• 1109. 航班预订统计（注意索引从 1 开始）
• 1094. 拼车（注意右开区间）

时间复杂度：N 个元素 M 次区间修改，总体 O(N+M)，远优于暴力 O(N×M)。

3.6 单调栈与单调队列

📎 文章：
https://labuladong.online/zh/algo/data-structure/monotonic-stack/
https://labuladong.online/zh/algo/data-structure/monotonic-queue/

单调栈

核心思想：维护栈内元素单调递增/递减，高效解决寻找每个元素的下一个更大（更小）元素问题。

// 标准模板：下一个更大元素
int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>();
    for (int i = n - 1; i >= 0; i--) {        // 倒序遍历
        while (!s.isEmpty() && s.peek() <= nums[i])
            s.pop();                            // 弹出小的
        res[i] = s.isEmpty() ? -1 : s.peek();
        s.push(nums[i]);
    }
    return res;
}

// 环形数组处理：遍历 2n-1 到 0，索引取模 i % n

三种变形：

时间复杂度：O(n)（摊还分析：每个元素最多入栈一次、出栈一次）。

单调队列

核心思想：在维护「先进先出」的同时，动态维护队列中所有元素的最值。

class MonotonicQueue {
    private LinkedList<Integer> q = new LinkedList<>();

    public void push(int n) {
        // 核心：删除尾部所有小于 n 的元素（维护单调递减）
        while (!q.isEmpty() && q.getLast() < n)
            q.pollLast();
        q.addLast(n);
    }

    public int max() { return q.getFirst(); } // 队头始终是最大值

    public void pop(int n) {
        // 惰性删除：仅当 n 等于队头时才删除
        if (n == q.getFirst()) q.pollFirst();
    }
}

典型场景：LeetCode 239. 滑动窗口最大值。时间复杂度 O(N)。

队列/栈互转

用栈实现队列（LeetCode 232）：两个栈 s1、s2，push 入 s1，pop/peek 时若 s2 为空则将 s1 全部倒入 s2。均摊 O(1)。

用队列实现栈（LeetCode 225）：单队列，pop 时将前 N-1 个元素出队再入队，队尾暴露到队头后弹出。pop O(N)，其余 O(1)。

单调栈变体

四种变体只需改比较符号和遍历方向：

覆盖题目：1019（链表下一个更大）、1475（商品折扣）、901（股票价格跨度）、402（移掉K位数字）、84（柱状图最大矩形）。

3.7 二叉树心法

📎 文章：
https://labuladong.online/zh/algo/data-structure/binary-tree-part1/ （思路篇）
https://labuladong.online/zh/algo/data-structure/binary-tree-part2/ （构造篇）

解题通用方法论

思考每个节点需要做什么，以及在前/中/后序哪个位置做，其余交给递归。

时间复杂度：均为 O(N)（每节点访问一次），空间 O(H)（递归栈深度）。

最近公共祖先 LCA（LeetCode 236）

本质：后序遍历 + 自底向上传递匹配信息。左右子树分别找，汇合时判断。

// 二叉树 LCA 核心框架
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root; // 分岔点即 LCA
    return left != null ? left : right;
}

完全二叉树的节点数（LeetCode 222）

核心：利用完全二叉树特性——如果左子树最左深度 == 右子树最左深度，则左子树是满二叉树，用公式 2^h - 1 直接算，避免遍历。

int countNodes(TreeNode root) {
    if (root == null) return 0;
    int lh = getDepth(root.left);  // 沿左子节点到底
    int rh = getDepth(root.right); // 沿右子节点到底
    if (lh == rh) return (1 << lh) + countNodes(root.right); // 左满
    else return (1 << rh) + countNodes(root.left);           // 右满
}

时间复杂度 O(log²N)，远优于普通遍历 O(N)。

3.8 二叉搜索树（BST）

📎 文章：
https://labuladong.online/zh/algo/data-structure/bst-part1/ （特性篇）
https://labuladong.online/zh/algo/data-structure/bst-part2/ （基操篇）
https://labuladong.online/zh/algo/data-structure/bst-part3/ （构造篇）

BST 核心特性：中序遍历有序

// 升序处理：中序遍历
void traverse(TreeNode root) {
    if (root == null) return;
    traverse(root.left);
    // 中序位置：核心逻辑
    traverse(root.right);
}

// 降序处理：反向中序遍历
void traverse(TreeNode root) {
    if (root == null) return;
    traverse(root.right);
    // 反向中序位置：核心逻辑
    traverse(root.left);
}

BST 四大操作

// 1. 判断 BST 合法性（LeetCode 98）
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
    if (root == null) return true;
    if (min != null && root.val <= min.val) return false;
    if (max != null && root.val >= max.val) return false;
    return isValidBST(root.left, min, root)
        && isValidBST(root.right, root, max);
}

// 2. 搜索元素（LeetCode 700）
TreeNode searchBST(TreeNode root, int target) {
    if (root == null) return null;
    if (root.val > target) return searchBST(root.left, target);
    if (root.val < target) return searchBST(root.right, target);
    return root;
}

// 3. 插入元素（LeetCode 701）
TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (root.val < val) root.right = insertIntoBST(root.right, val);
    if (root.val > val) root.left = insertIntoBST(root.left, val);
    return root;
}

// 4. 删除元素（LeetCode 450）
TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (root.val == key) {
        // 情况1: 叶子节点 → 直接删除
        if (root.left == null && root.right == null) return null;
        // 情况2: 只有一个子节点 → 子节点接替
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        // 情况3: 有两个子节点 → 右子树最小节点替换
        TreeNode minNode = getMin(root.right);
        root.right = deleteNode(root.right, minNode.val);
        minNode.left = root.left;
        minNode.right = root.right;
        root = minNode;
    } else if (root.val > key) {
        root.left = deleteNode(root.left, key);
    } else {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

3.9 数据结构设计

📎 文章：https://labuladong.online/zh/algo/data-structure/lru-cache/

LRU 缓存 — 哈希链表

核心数据结构：哈希表（HashMap） + 双向链表 = O(1) 查找 + O(1) 插入/删除。

class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();

    public LRUCache(int capacity) { this.cap = capacity; }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        makeRecently(key);
        return cache.get(key);
    }

    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            cache.put(key, val);
            makeRecently(key);
            return;
        }
        if (cache.size() >= cap) {
            int oldest = cache.keySet().iterator().next();
            cache.remove(oldest);
        }
        cache.put(key, val);
    }

    private void makeRecently(int key) {
        int val = cache.get(key);
        cache.remove(key);
        cache.put(key, val);
    }
}

时间复杂度：get 和 put 均为 O(1)。

关键设计理念：算法就像搭乐高，用已有的"零件"（数据结构）组合出想要的功能。

字典树（Trie）实现

核心思想：利用字符串公共前缀优化存储和查询。每个节点代表一个字符，从根到叶节点的路径是一个完整字符串。

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}
class Trie {
    TrieNode root = new TrieNode();
    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) node.children[idx] = new TrieNode();
            node = node.children[idx];
        }
        node.isEnd = true;
    }
    boolean search(String word) { /* 同 insert 遍历，最后查 isEnd */ }
    boolean startsWith(String prefix) { /* 同 insert 遍历，中途 null 则 false */ }
}

适用场景：搜索框自动补全、拼写检查、IP路由最长前缀匹配、词频统计。

如何实现一个计算器

四步递进法：①字符串转整数 → ②加减法（用栈存符号+数字对）→ ③乘除法（遇乘除弹出栈顶运算后再入栈）→ ④括号（递归调用自身）。

// 核心框架（处理 +-/* 和括号）
int calculate(String s) {
    Stack<Integer> stk = new Stack<>();
    int num = 0; char sign = '+';
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) num = 10 * num + (c - '0');
        if (c == '(') { /* 递归计算括号内容 */ }
        if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
            switch (sign) {
                case '+': stk.push(num); break;
                case '-': stk.push(-num); break;
                case '*': stk.push(stk.pop() * num); break;
                case '/': stk.push(stk.pop() / num); break;
            }
            sign = c; num = 0;
        }
    }
    int res = 0;
    while (!stk.isEmpty()) res += stk.pop();
    return res;
}

时间复杂度 O(n)。覆盖题目：224（加减+括号）、227（乘除）、772（完整版）。

3.10 图算法核心

📎 核心文章：环检测、拓扑排序、UnionFind、Dijkstra

环检测算法

// DFS 版本
boolean[] visited, onPath;
boolean hasCycle = false;

void traverse(List<Integer>[] graph, int s) {
    if (onPath[s]) { hasCycle = true; return; }
    if (visited[s] || hasCycle) return;
    visited[s] = true;
    onPath[s] = true;
    for (int t : graph[s]) traverse(graph, t);
    onPath[s] = false;
}

// BFS 版本（入度法/Kahn算法）
int[] indegree = new int[n];
for (int[] edge : edges) indegree[edge[0]]++;
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++)
    if (indegree[i] == 0) q.offer(i);
int count = 0;
while (!q.isEmpty()) {
    int cur = q.poll(); count++;
    for (int next : graph[cur]) {
        indegree[next]--;
        if (indegree[next] == 0) q.offer(next);
    }
}
return count == n; // 能遍历完所有节点 → 无环

拓扑排序算法

• DFS版本：后序遍历 + 反转 → 拓扑序
• BFS版本：入度为0的节点出队顺序即拓扑序

时间复杂度：O(V+E)。

Union-Find 并查集

class UF {
    private int[] parent, size;
    private int count;

    public UF(int n) {
        count = n;
        parent = new int[n]; size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }

    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
        return parent[x];
    }

    public void union(int p, int q) {
        int rootP = find(p), rootQ = find(q);
        if (rootP == rootQ) return;
        // 按秩合并：小树接大树下
        if (size[rootP] < size[rootQ]) { parent[rootP] = rootQ; size[rootQ] += size[rootP]; }
        else { parent[rootQ] = rootP; size[rootP] += size[rootQ]; }
        count--;
    }

    public boolean connected(int p, int q) { return find(p) == find(q); }
    public int count() { return count; }
}

单次操作均摊：近似 O(1)（阿克曼函数反函数）。

Dijkstra 最短路径算法

本质：标准 BFS + 贪心思想。用优先级队列替代普通队列，用 distTo 数组替代 visited。

// State: { int node; int dist; } (按 dist 排序的优先队列)
int[] dijkstra(int start, List<int[]>[] graph) {
    int[] distTo = new int[graph.length];
    Arrays.fill(distTo, Integer.MAX_VALUE);
    distTo[start] = 0;
    PriorityQueue<State> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist);
    pq.offer(new State(start, 0));

    while (!pq.isEmpty()) {
        State cur = pq.poll();
        if (cur.dist > distTo[cur.node]) continue; // 跳过旧记录
        for (int[] edge : graph[cur.node]) {
            int next = edge[0], weight = edge[1];
            int newDist = distTo[cur.node] + weight;
            if (newDist < distTo[next]) {
                distTo[next] = newDist;
                pq.offer(new State(next, newDist));
            }
        }
    }
    return distTo;
}

时间复杂度：O(E log V)（二叉堆实现）。仅适用非负权重。

二分图判定（LeetCode 785）

核心：双色问题——用两种颜色给所有顶点染色，任意边两端颜色不同。DFS/BFS 遍历染色，检测冲突。

boolean[] color, visited;
boolean ok = true;
void traverse(int[][] graph, int v) {
    if (!ok) return;
    visited[v] = true;
    for (int w : graph[v]) {
        if (!visited[w]) { color[w] = !color[v]; traverse(graph, w); }
        else if (color[w] == color[v]) { ok = false; }
    }
}

时间复杂度 O(V+E)。适用：二分图判定、分组/互斥关系问题（如 886. 可能的二分法）。

Kruskal 最小生成树

本质：贪心 + UnionFind。按权重升序排序所有边，依次加入不形成环的边，直到选出 V-1 条。

def kruskal(n, edges):
    edges.sort(key=lambda e: e[2])    # 按权重排序
    uf = UnionFind(n)
    mst_cost, count = 0, 0
    for u, v, w in edges:
        if uf.union(u, v):            # 不形成环
            mst_cost += w
            count += 1
            if count == n - 1: break
    return mst_cost if count == n-1 else -1

时间复杂度 O(E log E)（瓶颈在排序）。适用：最低成本连通所有城市（1135）、连接所有点最小费用（1584）。

四、经典暴力搜索算法（第二章）

4.1 回溯算法

📎 文章：
https://labuladong.online/zh/algo/essential-technique/backtrack-framework/
https://labuladong.online/zh/algo/essential-technique/permutation-combination-subset-all-in-one/

核心本质

回溯算法 = 遍历一棵决策树。站在树的任意节点思考三个问题：

1. 路径：已经做出的选择
2. 选择列表：当前可做的选择
3. 结束条件：到达决策树底层

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

核心在 for 循环里的递归：递归前「做选择」，递归后「撤销选择」。

排列/组合/子集 统一解法

三种基本形式 × 三种题型 = 九种组合：

记忆口诀：

1. 子集/组合用 start（防止回头重复组合）
2. 排列用 used（标记已选元素）
3. 有重复先排序，if (i > start && nums[i] == nums[i-1]) continue;
4. 可复选递归传 i 而非 i+1

// 子集/组合 — 元素无重不可复选（模板）
void backtrack(int[] nums, int start) {
    res.add(new LinkedList<>(track));  // 前序位置，收集所有节点
    for (int i = start; i < nums.length; i++) {
        track.add(nums[i]);
        backtrack(nums, i + 1);
        track.removeLast();
    }
}

// 排列 — 元素无重不可复选（模板）
void backtrack(int[] nums, boolean[] used) {
    if (track.size() == nums.length) {
        res.add(new LinkedList<>(track));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        track.add(nums[i]); used[i] = true;
        backtrack(nums, used);
        track.removeLast(); used[i] = false;
    }
}

// 有重复元素的去重剪枝（子集/组合 + 排序）
// 在 for 循环内添加：if (i > start && nums[i] == nums[i-1]) continue;

// 有重复元素的去重剪枝（排列 + 排序）
// 在 for 循环内添加：if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;

三大算法区分

时间复杂度：

• 子集：O(n × 2ⁿ) × 构造时间
• 排列：O(n × n!) × 构造时间

题型识别：要求枚举所有可能解、解空间可组织成决策树、每个选择影响后续可选项。

岛屿问题 DFS 模板

def dfs(grid, i, j):
    if i < 0 or j < 0 or i >= m or j >= n: return
    if grid[i][j] == '0': return
    grid[i][j] = '0'  # 淹没当前陆地
    dfs(grid, i-1, j)
    dfs(grid, i+1, j)
    dfs(grid, i, j-1)
    dfs(grid, i, j+1)

覆盖题目：岛屿数量(200)、封闭岛屿(1254)、飞地数量(1020)、岛屿最大面积(695)、子岛屿(1905)、不同岛屿数量(694)。时间复杂度 O(M×N)。

回溯实践：数独和 N 皇后

数独：遍历空格，尝试 1~9，校验同行/同列/同宫格无冲突后递归，遇无解回溯。最坏 O(9^空位数)，剪枝后远小于此。

N 皇后：按行逐层放置，每行选一列，用三个布尔数组记录列/左对角线/右对角线的占用状态。O(N!)，剪枝后更快。

// N皇后核心框架
void backtrack(int row) {
    if (row == n) { res.add(生成棋盘); return; }
    for (int col = 0; col < n; col++) {
        if (cols[col] || diag1[row+col] || diag2[row-col+n-1]) continue;
        cols[col] = diag1[row+col] = diag2[row-col+n-1] = true;
        board[row][col] = 'Q';
        backtrack(row + 1);
        board[row][col] = '.';
        cols[col] = diag1[row+col] = diag2[row-col+n-1] = false;
    }
}

4.2 BFS 算法

📎 文章：https://labuladong.online/zh/algo/essential-technique/bfs-framework/

核心本质

BFS = 图的层序遍历。擅长解决最短路径问题，因为层序遍历不需要遍历所有节点就能最短路径找到目标。

通用代码框架

int bfs(Node start, Node target) {
    Queue<Node> q = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    q.offer(start);
    visited.add(start);
    int step = 0;

    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            if (cur.equals(target)) return step; // 到达终点
            for (Node neighbor : cur.neighbors()) {
                if (!visited.contains(neighbor)) {
                    q.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        step++;
    }
    return -1;
}

双向 BFS 优化

前提：知道终点在哪。

用两个 HashSet 替代 Queue，从起点和终点同时扩散，当两个集合有交集时即找到最短路径。每次优先扩散较小集合。

时间复杂度：Big O 层面与普通 BFS 一致（O(N)），但实际速度更快（遍历节点数更少）。

题型识别：最短路径/最少步数、状态可穷举、可抽象为图/树模型。

五、经典动态规划算法（第三章）

5.1 DP 解题套路框架

📎 文章：https://labuladong.online/zh/algo/essential-technique/dynamic-programming-framework/

三大要素

1. 重叠子问题 — 暴力穷举存在大量重复计算
2. 最优子结构 — 子问题独立，可通过子问题最值得出原问题最值
3. 状态转移方程 — 描述问题结构的数学形式（最难写）

思维三步法

1. 明确「状态」：原问题和子问题中会变化的变量
2. 明确「选择」：导致状态变化的行为
3. 定义 dp 数组/函数：参数是状态，返回值是题目所求

两套框架

# 自顶向下（递归 + 备忘录）
def dp(状态1, 状态2, ...):
    # base case
    # 查备忘录
    for 选择 in 所有可能的选择:
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上（迭代 + DP table）
dp[0][0][...] = base case
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        dp[状态1][状态2][...] = 求最值(选择1, 选择2, ...)

方法论总结

1. 先写出暴力解（状态转移方程）— 这是最难的一步
2. 用备忘录或 DP table 消除重叠子问题（空间换时间）

时间复杂度：子问题个数 × 解决每个子问题的时间。

题型识别

• 求最值（最少、最长、最大、最小等）
• 最优子结构 + 重叠子问题
• 常见题目模式：斐波那契、零钱兑换、最长递增子序列、编辑距离、背包

5.2 经典 DP 问题详解

最长递增子序列（LIS）

📎 文章：https://labuladong.online/zh/algo/dynamic-programming/longest-increasing-subsequence/

int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];  // dp[i] = 以 nums[i] 结尾的最长递增子序列长度
    Arrays.fill(dp, 1);
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i])
                dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
    int res = 0;
    for (int d : dp) res = Math.max(res, d); // 注意：返回 dp 最大值
    return res;
}

二分查找优化（patience sorting）：O(N log N)。牌堆数即为 LIS 长度。

二维扩展（俄罗斯套娃信封，LeetCode 354）：按宽升序、宽相同按高降序排列，对高求 LIS。

编辑距离（LeetCode 72）

📎 文章：https://labuladong.online/zh/algo/dynamic-programming/edit-distance/

int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    // dp[i][j] = s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离
    for (int i = 1; i <= m; i++) dp[i][0] = i; // 全删
    for (int j = 1; j <= n; j++) dp[0][j] = j; // 全插

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1];   // 跳过
            else
                dp[i][j] = min(
                    dp[i - 1][j] + 1,           // 删除
                    dp[i][j - 1] + 1,           // 插入
                    dp[i - 1][j - 1] + 1        // 替换
                );
        }
    }
    return dp[m][n];
}

时间复杂度 O(mn)，空间可优化至 O(min(m,n))。

0-1 背包问题

📎 文章：https://labuladong.online/zh/algo/dynamic-programming/knapsack1/

int knapsack(int W, int[] wt, int[] val) {
    int N = wt.length;
    int[][] dp = new int[N + 1][W + 1];
    // dp[i][w] = 对于前 i 个物品，当前背包容量为 w，可装的最大价值
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0)
                dp[i][w] = dp[i - 1][w];           // 装不下
            else
                dp[i][w] = Math.max(
                    dp[i - 1][w],                   // 不装
                    dp[i - 1][w - wt[i - 1]] + val[i - 1]  // 装
                );
        }
    }
    return dp[N][W];
}

时间复杂度 O(N×W)。空间可优化至 O(W)。

题型识别：物品不可分割、每个物品只能用一次、在容量约束下求最大价值。

子集背包问题（LeetCode 416）

本质：0-1 背包的布尔判定版。判断能否选出若干数使其和等于 sum/2。

// 一维优化版
boolean canPartition(int[] nums) {
    int sum = Arrays.stream(nums).sum();
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int num : nums)
        for (int w = target; w >= num; w--)     // 倒序遍历！
            dp[w] = dp[w] || dp[w - num];
    return dp[target];
}

时间复杂度 O(N × sum/2)，空间 O(sum/2)。与 0-1 背包区别：求能否恰好装满（布尔），而非最大值。

完全背包问题（LeetCode 518）

本质：每种物品无限个。与 0-1 背包的唯一区别：内层遍历正序！

int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins)
        for (int j = coin; j <= amount; j++)    // 正序遍历！可重复选
            dp[j] += dp[j - coin];
    return dp[amount];
}

若交换内外循环（金额外层、硬币内层），得到的是排列数而非组合数。

最长公共子序列 LCS（LeetCode 1143）

两字符串问题通用技巧：两个指针 i, j 分别指向两个字符串尾部。

int longestCommonSubsequence(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];  // dp[i][j] = s1[0..i-1] 和 s2[0..j-1] 的 LCS
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (s1.charAt(i-1) == s2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    return dp[m][n];
}

时间复杂度 O(mn)。空间可优化至 O(min(m,n))。

最大子数组和（LeetCode 53，Kadane 算法）

int maxSubArray(int[] nums) {
    int cur = nums[0], res = nums[0];
    for (int i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]); // 自立门户 vs 延续前缘
        res = Math.max(res, cur);
    }
    return res;
}
// dp[i] = 以 nums[i] 结尾的最大子数组和
// 转移：dp[i] = max(nums[i], dp[i-1] + nums[i])

时间复杂度 O(n)，空间 O(1)。关键技巧：定义"以 i 结尾"保证子数组连续性。

DP 常见问题补充

Base Case / 备忘录初始值判定：

• base case：到达递归终止状态时返回什么值
• 备忘录初始值：用一个不可能出现的值标记"未计算"（如值范围[-100,100]时用 66666）
• 边界越界：返回极大/极小值使其不会被 min/max 选中

dp 数组遍历方向：取决于状态转移方程的依赖关系——计算 dp[i][j] 时，其所依赖的子状态必须已计算完毕。画状态转移图决定正序/倒序/斜序遍历。

动态规划设计方法论总结

六、其他常见算法技巧（第四章）

6.1 贪心算法

📎 文章：https://labuladong.online/zh/algo/essential-technique/greedy/

核心思想：不需要完整穷举所有可行解。识别出某条决策路径天然优于其他所有路径，直接沿着该路径前进。

// 穷举 → 贪心 三步演化：
// 阶段一：递归穷举（指数级）
// 阶段二：发现贪心性质后剪枝
// 阶段三：迭代/公式（O(1)）

三步法：

1. 先构建决策树，明确所有可行解
2. 分析局部最优是否直接导向全局最优（贪心选择性质）
3. 将贪心策略转化为公式或循环

vs 回溯/DP：回溯/DP 穷举所有可能；贪心利用信息直接排除不可能的解。

典型题目：跳跃游戏 I/II（LeetCode 55/45）。

6.2 分治算法

📎 文章：https://labuladong.online/zh/algo/essential-technique/divide-and-conquer/

广义分治：问题分解为结构相同的子问题，求解后合并。 狭义分治：分解求解后，总体复杂度比不分解更低。

经典三步：

1. 分解 — 划分独立子问题
2. 求解 — 递归求解（足够小时直接解）
3. 合并 — 组合得到原问题解

典型例子：归并排序（后序位置合并）、快速排序（前序位置分界）、桶排序。

6.3 数学与经典技巧

nSum 问题

📎 文章：https://labuladong.online/zh/algo/practice-in-action/nsum/

核心思路：排序 + 双指针，通过递归将 nSum 降维到 twoSum。

// 通用模板：排序后递归降维
List<List<Integer>> nSumTarget(int[] nums, int n, int start, long target) {
    int sz = nums.length;
    List<List<Integer>> res = new ArrayList<>();
    if (n < 2 || sz < n) return res;
    if (n == 2) {
        // twoSum 双指针
        int lo = start, hi = sz - 1;
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            if (sum < target) lo++;
            else if (sum > target) hi--;
            else {
                res.add(Arrays.asList(nums[lo], nums[hi]));
                while (lo < hi && nums[lo] == nums[lo + 1]) lo++; // 跳过重复
                while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
                lo++; hi--;
            }
        }
    } else {
        for (int i = start; i < sz; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue; // 跳过重复
            List<List<Integer>> subs = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
            for (List<Integer> sub : subs) {
                List<Integer> combined = new ArrayList<>(sub);
                combined.add(0, nums[i]);
                res.add(combined);
            }
        }
    }
    return res;
}

时间复杂度：kSum 总体 O(n^(k-1))。

6.4 经典面试题精选

接雨水（LeetCode 42）

核心公式：water[i] = min(left_max[i], right_max[i]) - height[i]

最优解 — 双指针 O(N)/O(1)：哪侧当前最大值更小就处理哪侧。

int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int lMax = 0, rMax = 0, res = 0;
    while (left <= right) {
        if (lMax < rMax) {
            lMax = Math.max(lMax, height[left]);
            res += lMax - height[left++];
        } else {
            rMax = Math.max(rMax, height[right]);
            res += rMax - height[right--];
        }
    }
    return res;
}

扫描线技巧：会议室（LeetCode 253）

将每个会议拆为开始(+1)和结束(-1)事件，按时间排序后遍历，累加得最大重叠数即最少会议室数。O(N log N)。

丑数系列

带权重的随机选择（LeetCode 528）

前缀和 + 二分搜索。构建前缀和数组，随机生成 [1, total] 内整数，二分搜索找第一个 ≥ target 的位置。构造 O(n)，查询 O(log n)。

6.5 必知必会数学技巧

模运算

(a+b)%k = (a%k + b%k)%k，(a*b)%k = (a%k)*(b%k)%k，(a-b)%k = (a%k - b%k + k)%k

快速幂

long quickPow(long a, long b, long mod) {
    long res = 1; a %= mod;
    while (b > 0) {
        if ((b & 1) == 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
// O(log b) 时间

最大公约数 GCD — 欧几里得算法

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

最小公倍数 LCM

int lcm(int a, int b) { return (a / gcd(a, b)) * b; } // 先除后乘防溢出

素数筛法（埃拉托色尼筛法）

int countPrimes(int n) {
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    for (int i = 2; i * i < n; i++)
        if (isPrime[i])
            for (int j = i * i; j < n; j += i)  // 从 i*i 开始
                isPrime[j] = false;
    int count = 0;
    for (int i = 2; i < n; i++) if (isPrime[i]) count++;
    return count;
}

时间复杂度 O(N log log N)。

一行代码就能解决的算法题

七、设计思想总结

7.1 解题方法论全景

┌──────────────────────────────────────────────────┐
│              算法的本质 = 穷举                      │
│  ┌─────────────┐  ┌─────────────────────────┐    │
│  │ 无遗漏：框架保证 │  │ 无冗余：剪枝/备忘录/贪心      │    │
│  └─────────────┘  └─────────────────────────┘    │
│                                                      │
│  穷举手段：                                          │
│  ├── 递归（基于树结构）                                │
│  │   ├── 遍历思维 → 回溯/DFS                         │
│  │   └── 分解问题思维 → 动态规划/分治                   │
│  └── 迭代                                            │
│      ├── BFS（层序遍历） → 最短路径                    │
│      └── 数组双指针/滑动窗口/二分搜索                    │
└──────────────────────────────────────────────────┘

7.2 算法选择决策树

问题类型？
├── 求所有可能解 → 回溯算法
│   ├── 子集/组合 → 用 start
│   └── 排列 → 用 used
├── 求最值？存在最优子结构？
│   ├── 存在重叠子问题 → 动态规划
│   │   ├── 子序列 → LIS 模式
│   │   ├── 双字符串 → 编辑距离 / LCS
│   │   ├── 容量约束 → 背包问题
│   │   └── 区间 → dp[i][j] + 状态转移
│   └── 贪心选择性质 → 贪心算法
├── 求最短路径/最少步数？
│   ├── 无权图 → BFS（层序遍历）
│   ├── 非负权重 → Dijkstra（BFS+贪心）
│   └── 知道终点 → 双向 BFS
├── 数组/子串问题？
│   ├── 子数组/子串 → 滑动窗口 / 前缀和 / 差分
│   ├── 有序数组搜索 → 二分搜索
│   ├── 下一个更大/更小 → 单调栈
│   └── 窗口最值 → 单调队列
├── 链表问题？
│   ├── 中点/环 → 快慢指针
│   ├── 倒数第k个 → 前后指针
│   └── 相交 → 双指针拼接
├── 图问题？
│   ├── 依赖关系 → 环检测/拓扑排序
│   ├── 连通性 → Union-Find
│   └── 最短路径 → Dijkstra / BFS
└── 二叉树问题？
    ├── 子树问题 → 分解（后序位置）
    ├── 结构修改 → 遍历（前/中/后序）
    └── 层级问题 → BFS/层序遍历

7.3 核心设计思想

附录：全站文章索引

基础：数据结构及排序精讲

• 数组/链表基本原理 → 环形数组 → 队列栈 → 哈希表 → LinkedHashMap/ArrayHashMap
• 二叉树基础/遍历 → 多叉树遍历 → DFS/BFS场景 → 二叉搜索树 → 二叉堆 → 图结构

第零章：核心刷题框架汇总

• 算法框架思维 → 递归方法论 → 二叉树纲领

第一章：经典数据结构算法

• 链表双指针 → 回文链表 → 链表反转（4种变体）→ 数组双指针 → 二维数组遍历
• 滑动窗口 → 二分搜索（基础+实际运用框架）→ 前缀和/差分
• 队列/栈互转 → 单调栈/单调队列（含变体）→ 二叉树心法（思路/构造/序列化）
• LCA系列（5种变体）→ 完全二叉树节点数 → BST（特性/基操/构造）
• 字典树（Trie）→ LRU/LFU → 计算器实现 → 数据结构设计
• 图：环检测/拓扑排序 → 二分图判定 → UnionFind → Kruskal → Dijkstra

第二章：经典暴力搜索算法

• 回溯框架 → 排列/组合/子集（9种组合）→ 数独/N皇后 → 岛屿DFS → DFS vs 回溯
• BFS框架 → 双向BFS

第三章：经典动态规划算法

• DP框架（三步法）→ base case/备忘录 → 最优子结构/遍历方向
• LIS（含二分优化）→ 编辑距离 → 最大子数组 → LCS
• 0-1背包 → 子集背包 → 完全背包（三种背包对比）

第四章：其他常见算法技巧

• 贪心 → 分治 → nSum通用模板
• 接雨水（三种解法演进）→ 扫描线（会议室）→ 丑数系列（三种变体）
• 带权随机选择 → 一行代码系列
• 数学：模运算/快速幂/GCD/LCM/素数筛法
• 排序算法导读（十大排序概述）