Quartz 4

算法入门

23 min read

  1. 阶段一：算法入门。我们需要熟悉各种数据结构的特点和用法，学习不同算法的原理、流程、用途和效率等方面的内容。
  2. 阶段二：刷算法题。建议从热门题目开刷，先积累至少 100 道题目，熟悉主流的算法问题。初次刷题时，“知识遗忘”可能是一个挑战，但请放心，这是很正常的。我们可以按照“艾宾浩斯遗忘曲线”来复习题目，通常在进行 3～5 轮的重复后，就能将其牢记在心。推荐的题单和刷题计划请见此 GitHub 仓库。
  3. 阶段三：搭建知识体系。在学习方面，我们可以阅读算法专栏文章、解题框架和算法教材，以不断丰富知识体系。在刷题方面，可以尝试采用进阶刷题策略，如按专题分类、一题多解、一解多题等，相关的刷题心得可以在各个社区找到。
  • 清华数据结构与算法：
  • 刷题
    • leetcode 通关手册：侧重对数据结构和算法原理的分析，比如一个数据结构具体的设计原理和复杂度分析。有些题解实现不是很高效。
    • 代码随想录：侧重对各个算法和数据结构在解题时的分析，比如具体的循环条件和区间判断
    • leetcode101：题解丰富，讲解少
    • https://labuladong.online/algo/
    • 算法笔记胡凡
  • 书
    • Data Structures and Algorithms in C++：详尽地讲解了所有可能遇到的数算，不适合入门
    • 算法导论：注重理论推导算法导论中过于注重问题的建模、公式推导，有点难以理解。
    • 算法 4：

线性、图、堆、树

红黑树

布隆过滤

进程、内存管理；OSI，TCP/IP，HTTP1

373 查找寻找最小 k 对

146 LRU

215 第 k 大

445 两数相加 2

200 岛屿数量

240 搜索二维矩阵

31 下一个排列

数算系统整理

🔹 基础核心数据结构

1. 线性结构

结构C++ 实现Python 实现核心操作应用场景
数组（Array）std::array<T, N>, T[]list, array随机访问 O(1)基础存储
动态数组（Vector）std::vector<T>list（动态）扩容 O(1) amortized变长序列
链表（List）std::list<T>（双向）
std::forward_list<T>（单向）		collections.deque（双端）
手动实现		插入/删除 O(1)频繁插入删除
栈（Stack）std::stack<T>list（append, pop）LIFODFS、表达式求值
队列（Queue）std::queue<T>collections.dequeFIFOBFS、任务调度
双端队列（Deque）std::deque<T>collections.deque头尾 O(1)滑动窗口

✅ 重点掌握：vector vs list 的性能权衡，deque 的缓存友好性。

2. 树形结构

结构C++ 实现Python 实现核心操作应用场景
二叉树（Binary Tree）手动定义类类或字典遍历（前/中/后/层序）递归基础
二叉搜索树（BST）std::set<T>, std::map<K,V>dict（非 BST）
需手动实现		查找 O(log n) 平均有序集合
堆（Heap）std::priority_queue<T>
std::make_heap		heapq 模块插入/删除 O(log n)优先级任务、Top-K
并查集（Union-Find）手动实现手动实现Union/Find O(α(n))连通性问题

✅ 重点掌握：BST 的中序遍历 = 有序序列，堆的数组表示。

3. 哈希结构

结构C++ 实现Python 实现核心操作应用场景
哈希表（Hash Table）std::unordered_map<K,V>
std::unordered_set<T>		dict, set查找 O(1) 平均去重、计数、缓存
哈希函数与冲突处理STL 内置内置开放寻址、链地址法理解底层原理

✅ 重点掌握：哈希冲突、负载因子、dict 的不可变键要求。

4. 图（Graph）

结构C++ 实现Python 实现核心操作应用场景
邻接表vector<vector<int>>
unordered_map<int, vector<int>>		dict of list遍历、建图通用图存储
邻接矩阵vector<vector<int>>二维 list空间 O(V²)稠密图
边列表vector<pair<int,int>>list of tupleKruskal、并查集最小生成树

✅ 重点掌握：图的遍历（DFS/BFS）、环检测、连通分量。

🎯 总结对比表（重要）

结构访问插入/删除（尾）插入/删除（头/中）查找缓存友好典型用途
数组O(1)-O(n)O(n)✅ 极佳固定大小数据
动态数组O(1)O(1) amortizedO(n)O(n)✅ 极佳通用序列
链表O(n)O(1)O(1)O(n)❌ 差频繁插入删除
栈O(1)O(1)O(1)O(n)依赖底层DFS、表达式
队列O(1)O(1)O(1)O(n)依赖底层BFS、调度
哈希表O(1)O(1)O(1)O(1)❌ 差（链式）快速查找、去重
二叉树O(n)O(n)O(n)O(n)❌ 差递归结构、BST
堆O(1)O(log n)O(log n)O(n)✅（数组实现）优先级、Top-K

🔹 算法设计范式

范式核心思想典型问题C++/Python 工具
分治（Divide & Conquer）分解 → 解决 → 合并归并排序、快速排序、大数乘法递归、std::sort
贪心（Greedy）每步选局部最优活动选择、Huffman 编码、Dijkstra（部分）priority_queue, heapq
动态规划（DP）状态定义 + 转移方程背包问题、最长公共子序列、编辑距离数组、记忆化（@lru_cache）
回溯（Backtracking）深度优先 + 剪枝N 皇后、全排列、子集递归、list 回溯
分支限界（Branch & Bound）BFS + 剪枝旅行商问题（TSP）priority_queue（类似 A*）
双指针（Two Pointers）左右夹逼两数之和、滑动窗口、环检测left, right 索引
滑动窗口（Sliding Window）维护窗口内状态最小覆盖子串、最长无重复子串unordered_map, dict
拓扑排序（Topological Sort）DAG 排序课程表、依赖解析BFS（Kahn）或 DFS
网络流（Network Flow）最大流、最小割二分图匹配、任务分配Ford-Fulkerson、Dinic（手动实现）

✅ 重点掌握：DP 状态设计、贪心选择性质证明、回溯剪枝技巧。

🔹 算法分析与复杂度

1. 时间复杂度（Big-O）

复杂度示例算法可处理数据规模（约）
O(1)哈希查找任意
O(log n)二分查找10^18
O(n)线性扫描10^7
O(n log n)排序、堆操作10^6
O(n²)暴力枚举10^4
O(n³)Floyd、矩阵乘法10^2~10^3
O(2ⁿ)子集枚举20~25
O(n!)全排列10~12

2. 空间复杂度

  • 栈空间（递归深度）
  • 堆空间（动态分配）
  • 注意空间换时间策略

3. 摊还分析（Amortized Analysis）

  • std::vector 扩容：O(1) 摊还
  • std::deque 插入：O(1) 摊还

🔹 应用场景与系统设计

场景推荐数据结构/算法
缓存系统（如 Redis）LRU/LFU Cache（哈希 + 双向链表）、跳表（有序集合）
搜索引擎倒排索引（哈希 + 链表）、Trie（自动补全）
数据库索引B+ 树、哈希索引
文件系统B 树、目录树
编译器符号表（哈希）、语法树（AST）、栈（表达式求值）
操作系统进程调度（优先队列）、内存管理（伙伴系统、页表）
推荐系统图算法（社交网络）、协同过滤（矩阵分解）

✅ 目标：能设计一个简单的 LRU Cache 或 Trie 搜索引擎。

终极目标

  • 能手写任何核心数据结构（如红黑树了解原理，能写 AVL、Trie）。
  • 看到问题能快速识别模式（是 DP？贪心？图？）。
  • 能用 C++ 或 Python 高效实现，并分析复杂度。
  • 能将算法应用于实际系统设计。

🔹 高级数据结构（可选）

结构C++ 实现Python 实现核心优势应用场景
平衡二叉搜索树（AVL, Red-Black）std::map, std::set（红黑树）需第三方库或手动实现查找 O(log n) 最坏有序集合、区间查询
B/B+ 树手动实现手动实现磁盘友好，多路搜索数据库索引、文件系统
线段树（Segment Tree）手动实现手动实现区间查询/更新 O(log n)区间最值、求和
树状数组（Fenwick Tree）手动实现手动实现前缀和、单点更新 O(log n)逆序对、差分
字典树（Trie）手动实现（指针或数组）字典嵌套字符串前缀匹配自动补全、IP 路由
跳表（Skip List）手动实现手动实现随机化平衡，O(log n)Redis 有序集合
LRU Cachestd::list + unordered_mapcollections.OrderedDict
@lru_cache		O(1) 插入/删除/查找缓存淘汰策略

✅ 建议：掌握 Trie、线段树、树状数组、LRU Cache 的手写实现。

基础数据结构

非常好。我们将重新系统化地梳理基础核心数据结构，完全聚焦于：

  • 组成原理（底层结构与工作机制）
  • 复杂度分析（时间/空间复杂度的推导过程）
  • 复杂度类型说明（最坏、平均、摊还等）

不涉及具体代码，只讲本质与逻辑。

一、数组（Array）

🔧 组成原理

  • 连续内存块：所有元素在内存中按顺序排列。
  • 固定大小：声明时确定容量，不可动态扩展。
  • 索引访问机制：通过 基地址 + 偏移量 直接定位元素。
    • 偏移量 = 索引 × 元素大小（单位字节）。
    • 因此访问是随机访问（Random Access）。

⏱️ 时间复杂度分析

操作复杂度推导
访问 arr[i]O(1)地址计算为常数时间，直接读取内存。
插入/删除（任意位置）O(n)必须移动插入点后的所有元素，平均移动 n/2 个元素。
查找（无序）O(n)需遍历所有元素，最坏情况查到最后一个。
查找（有序）O(log n)可用二分查找，每次排除一半数据。

✅ 复杂度类型：

  • 访问：最坏 O(1)（任何索引都一样快）
  • 插入/删除：最坏 O(n)（插入头部需移动全部）
  • 查找：最坏 O(n) 或 最坏 O(log n)（有序时）

📏 空间复杂度

  • O(n)，无额外开销，空间利用率 100%。

二、动态数组（Vector / Dynamic Array）

🔧 组成原理

  • 本质是带自动扩容机制的数组。
  • 维护三个关键量：
    • size：当前元素个数
    • capacity：已分配内存能容纳的元素总数
    • 当 size == capacity 时，触发扩容。
  • 扩容策略：通常分配 原容量的 2 倍（或 1.5 倍），将旧数据拷贝到新内存，释放旧内存。

⏱️ 时间复杂度分析

操作复杂度推导
访问 vec[i]O(1)同数组，随机访问。
尾部插入 push_back摊还 O(1)大多数情况 O(1)，但扩容时需 O(n) 拷贝。由于扩容频率低（每 2^k 次插入才扩一次），摊还后为 O(1)。
尾部删除 pop_backO(1)仅减少 size，不释放内存。
中间插入/删除O(n)需移动后续元素，平均移动 n/2 个。

✅ 复杂度类型：

  • 访问：最坏 O(1)
  • 尾插：摊还 O(1)（Amortized），最坏 O(n)（单次扩容）
  • 中间操作：最坏 O(n)

📏 空间复杂度

  • O(n)，但可能浪费空间（capacity > size），空间利用率在 50%~100% 之间。

三、链表（Linked List）

🔧 组成原理

  • 由**节点（Node）**构成，每个节点包含：
    • 数据域
    • 指针域（指向下一个节点，双向链表还有指向前一个的指针）
  • 节点在堆上动态分配，内存不连续。
  • 通过指针逐个跳转访问元素。

⏱️ 时间复杂度分析

操作复杂度推导
访问第 i 个元素O(n)必须从头节点开始，逐个遍历 i 次。
头部插入/删除O(1)只需修改头指针和第一个节点的指针。
尾部插入（有尾指针）O(1)有尾指针时直接操作。
尾部插入（无尾指针）O(n)需遍历到末尾。
中间插入/删除（已知位置）O(1)已知节点指针时，只需修改前后指针。
查找O(n)需遍历所有节点。

✅ 复杂度类型：

  • 访问：最坏 O(n)（访问最后一个）
  • 头插/删：最坏 O(1)
  • 中间操作（已知位置）：最坏 O(1)

📏 空间复杂度

  • O(n)，但每个节点有指针开销（单向：+8 字节，双向：+16 字节，64 位系统）。

四、栈（Stack）

🔧 组成原理

  • 后进先出（LIFO） 的线性结构。
  • 只允许在**一端（栈顶）**进行插入和删除。
  • 可用数组或链表实现：
    • 数组实现：维护一个 top 索引。
    • 链表实现：头节点即栈顶。

⏱️ 时间复杂度分析

操作复杂度推导
push(x)O(1)在栈顶添加元素，常数时间。
pop()O(1)删除栈顶元素，常数时间。
top()O(1)读取栈顶元素，常数时间。
empty()O(1)检查 top 是否为 -1 或头指针是否为空。

✅ 复杂度类型：所有操作均为 最坏 O(1)。

📏 空间复杂度

  • O(n)，与元素个数成正比。

五、队列（Queue）

🔧 组成原理

  • 先进先出（FIFO） 的线性结构。
  • 允许在一端（队尾）插入，在另一端（队头）删除。
  • 可用链表或循环数组实现：
    • 链表：头删尾插，O(1)。
    • 循环数组：用模运算实现“循环”，避免频繁移动。

⏱️ 时间复杂度分析

操作复杂度推导
enqueue(x)O(1)队尾插入，常数时间。
dequeue()O(1)队头删除，常数时间。
front()O(1)读取队头元素。
empty()O(1)检查头尾指针是否重合。

✅ 复杂度类型：所有操作均为 最坏 O(1)。

📏 空间复杂度

  • O(n)。

六、哈希表（Hash Table）

🔧 组成原理

  • 核心思想：将键（Key）映射到数组索引，实现快速查找。
  • 两个关键机制：
    1. 哈希函数：将任意键映射为整数（如 hash(key) % table_size）。
    2. 冲突处理：
      • 链地址法（Chaining）：每个桶是一个链表，冲突元素挂载其后。
      • 开放寻址法（Open Addressing）：冲突时探测下一个空位（线性、二次、双重哈希）。

⏱️ 时间复杂度分析

操作平均复杂度最坏复杂度推导
查找O(1)O(n)平均：哈希均匀分布，每个桶只有常数个元素。
最坏：所有键哈希到同一桶，退化为链表遍历。
插入O(1)O(n)同查找，插入前需检查是否已存在。
删除O(1)O(n)同查找。

✅ 复杂度类型：

  • 平均情况 O(1)：假设哈希函数良好，负载因子合理。
  • 最坏情况 O(n)：全冲突。
  • 摊还 O(1)：考虑扩容时的重新哈希，但频率低。

📏 空间复杂度

  • O(n + m)，n 为元素数，m 为桶数。
  • 负载因子 α = n/m，通常控制在 0.7~1.0 之间。

七、二叉树（Binary Tree）

🔧 组成原理

  • 每个节点最多有两个子节点：左子树 和 右子树。
  • 无结构约束时，树可能极度不平衡（退化为链表）。
  • 遍历方式决定访问顺序：
    • 前序：根 → 左 → 右
    • 中序：左 → 根 → 右
    • 后序：左 → 右 → 根
    • 层序（BFS）：按层从左到右

⏱️ 时间复杂度分析

操作复杂度推导
遍历所有节点O(n)每个节点访问一次。
查找/插入/删除（普通二叉树）O(n)树可能退化为链表，需遍历所有节点。
高度 hO(n) 最坏
O(log n) 最好		最坏：链状；最好：完全二叉树。

✅ 复杂度类型：

  • 遍历：最坏 O(n)
  • 单次操作：最坏 O(n)，最好 O(log n)

📏 空间复杂度

  • O(n) 存储节点。
  • 递归遍历时，调用栈深度为 O(h)，最坏 O(n)。

八、堆（Heap）

🔧 组成原理

  • 完全二叉树（用数组实现）。
  • 满足堆性质：
    • 大根堆：父节点 ≥ 子节点
    • 小根堆：父节点 ≤ 子节点
  • 数组索引关系：
    • 父节点 i → 左子 2i+1，右子 2i+2
    • 子节点 i → 父 (i-1)/2
  • 核心操作：
    • 上浮（heapify up）：插入后调整。
    • 下沉（heapify down）：删除根后调整。

⏱️ 时间复杂度分析

操作复杂度推导
插入 pushO(log n)上浮最多从叶到根，路径长度为树高 log n。
删除根 popO(log n)下沉最多从根到叶，路径长度 log n。
获取堆顶O(1)直接返回数组首元素。
构建堆（N 个元素）O(n)从最后一个非叶节点开始 heapify down，数学推导可得线性时间。

✅ 复杂度类型：均为 最坏 O(log n)（插入/删除），最坏 O(1)（取顶）。

📏 空间复杂度

  • O(n)。

🎯 总结：复杂度类型说明

类型含义举例
最坏情况（Worst-case）任何输入下的最大开销链表访问尾部：O(n)
平均情况（Average-case）所有输入的期望开销哈希表查找：O(1)
摊还（Amortized）一系列操作的平均开销vector 尾插：O(1) 摊还
最好情况（Best-case）最优输入下的开销二分查找第一下命中：O(1)

✅ 核心结论

结构随机访问动态扩展插入/删除快查找快缓存友好
数组✅ O(1)❌❌ O(n)❌ O(n)✅ 极佳
动态数组✅ O(1)✅❌ O(n)❌ O(n)✅ 极佳
链表❌ O(n)✅✅ O(1)❌ O(n)❌ 差
栈/队列❌✅✅ O(1)❌ O(n)依赖底层
哈希表✅ O(1)✅✅ O(1)✅ O(1)❌ 差
二叉树❌ O(n)✅❌ O(n)❌ O(n)❌ 差
堆✅ O(1)✅✅ O(log n)❌ O(n)✅（数组实现）

掌握这些结构的内在机制与复杂度来源，你就能在面对任何问题时，理性选择最合适的数据结构，而不是“凭感觉”或“背模板”。

算法笔记胡凡

11 DP

动态规划 (Dynamic Programming,DP) 是一种用来解决一类最优化问题的算法思想。简单来说,动态规划将一个复杂的问题分解成若干个子问题,通过综合子问题的最优解来得到原问题的最优解。需要注意的是,动态规划会将每个求解过的子问题的解记录下来,这样当下一次碰到同样的子问题时,就可以直接使用之前记录的结果,而不是重复计算。注意: 虽然动态规划采用这种方式来提高计算效率,但不能说这种做法就是动态规划的核心 (后面会说明这一点)。一般可以使用递归或者递推的写法来实现动态规划,其中递归写法在此处又称作记忆化搜索。

回溯

问题 -> 方法 -> 解答

输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

  • naive：按照不同的长度，依次遍历所有的子集，如长度 1 有 3 种、长度 2 有 3 种、等等。
    • 问题：

对比

维度动态规划（DP）回溯（Backtracking）
目标求路径数量求所有路径（或数量）
时间复杂度O(m×n)O(2^(m+n))（指数级）
空间复杂度O(m×n) 或 O(min(m,n))O(m+n)（递归栈）
是否重复计算否（记忆化）是（无记忆）
适合场景计数、最优化问题枚举所有解、构造路径
能否处理大网格✅ 可以（m,n 较大）❌ 会超时（m+n > 20 就慢）
问题回答
用 DP 还是回溯？✅ 动态规划，❌ 不要用回溯
为什么？DP 利用子问题重叠，O(mn) 时间；回溯是指数级
核心思想？dp[i][j] = 上 + 左，障碍处为 0
适用场景？网格路径计数、最短路径、最大路径和等

💡 记住：求“数量”用 DP，求“所有路径”用回溯。这是区分两者的关键！

Graph View

Backlinks