Data Structures & Algorithm
笔记列表 20
四种遍历 A / \ B C / \ \ D E F 遍历 顺序 结果 先序（Preorder） 根 → 左 → 右 A B D E C F 中序（Inorder） …
自动关联目录：Tree 树是图的一个特例：连通且无环，nnn 个点恰好 n−1n-1n−1 条边。 但它值得单独成章，因为： 递归结构天然适配分治和 DP 大量问题（文件系统、语法树、组织架构、决策树）本身就是树 图上的很多问题在树上简单…
自动关联目录：Data Structures & Algorithm 这里记录的是解题方法，不是"把 STL 用熟"。核心是三类能力： 看出问题的结构（能归约到哪个模型） 选对工具（哪种数据结构/算法能支撑所需…
自动关联目录：LeetCode C++ 标准库速查 这不是 C++ 标准库百科，而是一份刷 LeetCode 时够用、能直接查代码的标准库清单。范围包括容器、算法、数值工具、字符串处理、函数对象和常用辅助类型。目标只有三个： 看到题目特征…
自动关联目录：Basic Algorithm 这一组是不依赖特定数据结构的通用算法思想。它们不是"某一类题的解法"，而是思考问题的方式——后面所有高级算法都是它们的组合。 一张表 思想 一句话 适用信号 枚…
二分在做什么 二分的本质不是"在有序数组里找数"，而是： 在一个单调的判定函数上，用 O(logn)O(\log n)O(logn) 次询问定位分界点。 把问题看成：有一个序列 [false, false, ...…
枚举在做什么 **枚举（Enumeration / Brute Force）**是最诚实的算法：把所有候选答案试一遍，取最优或计数。 复杂度通常是指数级，所以枚举不是"随便写个 for"，而是：如何高效、不重不漏地遍历答…
递归 递归是用函数自己定义自己。一个正确的递归需要两样东西： 1. 基础情形（Base Case）：最小规模直接给出答案，不再递归 2. 递归情形（Recursive Case）：把问题化归为更小的同类问题 缺了 base case → 无…
排序是所有算法的前置步骤 排序本身很少是目的，更多是手段——排完序之后： 二分查找成为可能 双指针成为可能 贪心策略有了明确的顺序 相同元素聚在一起（去重、计数） **"先排序再说"**是解题时最常用的一步。 比较排…
一对对偶操作 前缀和（Prefix Sum）和差分（Difference）是互逆的： 差分→前缀和原数组,原数组→差分差分数组\text{差分} \xrightarrow{\text{前缀和}} \text{原数组}, \qquad \te…
自动关联目录：Dynamic Programming 动态规划（DP）的本质：把穷举中的重复计算缓存下来。 穷举: 枚举所有方案，每个方案 O(n) 计算 → O(2^n · n) DP: 发现不同方案共享"子方案&quo…
动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。 原理 最优子结构 具有最优子结构也可能是适合用贪心的方法求解。 注意要确保我们考察了最…
自动关联目录：Graph 图是表达"关系"的通用模型。很多看起来不像图的题，建出图来就迎刃而解。 术语 术语 含义 顶点 / 边 vertex / edge 有向图 / 无向图 边有没有方向 度 /…
两种遍历 DFS（深度优先） BFS（广度优先） 数据结构 栈（递归 / 显式栈） 队列 顺序 一条路走到底再回溯 一层一层扩散 找什么 路径、连通性、拓扑序 最短（少）步数 空间 O(深度)O(\text{深度…
自动关联目录：Hash 哈希（Hash）回答的是：如何用 O(1)O(1)O(1) 的代价，判断"我见过这个东西吗"。 它的代价是放弃有序性——哈希表里取不出"最小的元素"，也做不了范围查询。 需要范…
自动关联目录：Linear 线性结构是元素排成一列的结构。区别在于允许在哪些位置插入/删除。 总览 结构 插入/删除位置 访问 典型用途 数组 任意（但要搬移） O(1)O(1)O(1) 随机 默认选择 链表 已知位置 O…
自动关联目录：Misc 不属于单一主题，但到处都在用的东西。 复杂度分析 三种记号 记号 含义 类比 OOO（大 O） 上界，不超过 ≤\le≤ Ω\OmegaΩ（大 Ω） 下界，至少 ≥\ge≥ Θ\ThetaΘ（大…
倍增在做什么 **倍增（Binary Lifting）**的核心思想： 预处理出"跳 2k2^k2k 步"的信息，之后任意 nnn 步都拆成二进制，用 O(logn)O(\log n)O(logn) 次跳跃拼出来。 …
自动关联目录：String 字符串问题的三个层次： 单串：在一个串里找结构（回文、周期、子串） 双串：两个串的关系（匹配、最长公共子串/子序列） 多串：一堆串的查询（Trie、AC 自动机、后缀数组） 字符串匹配 在文本 TTT（长 …
贪心在做什么 贪心（Greedy）：每一步都做当前看起来最优的选择，不回头。 贪心: 局部最优 → 局部最优 → ... → 全局最优（？） DP: 枚举所有选择，取全局最优 核心难点：贪心不一定对。它的正确性必须证明，不能靠&…