数据结构与算法学习笔记#

系统梳理数据结构与算法核心知识。每节先讲"是什么"和"为什么"，再给代码模板和常见陷阱。

1 · 复杂度分析#

1.1 时间复杂度#

时间复杂度描述的是：当输入规模 n 变大时，算法执行时间增长的趋势。它不关心实际跑多少秒，只关心"量级"。

常见量级：

• O(1)：哈希表查找、数组按索引访问
• O(log n)：二分查找、平衡树查找
• O(n)：遍历数组一次
• O(n log n)：快速排序、归并排序
• O(n²)：双重循环，冒泡排序
• O(2ⁿ)：递归枚举所有子集
• O(n!)：全排列

面试中一个常见错误：把 O(2n) 说成 O(n²)。常量系数不写，低阶项忽略，所以 O(2n) 就是 O(n)。

1.2 空间复杂度#

空间复杂度衡量的是算法运行过程中额外占用的内存随 n 的变化趋势。

• O(1)：原地修改，如反转链表
• O(n)：开辟大小为 n 的辅助数组
• O(log n)：递归调用栈深度，如二分查找、快速排序
• O(n)：递归深度达到 n，如链表递归

空间换时间是常见策略。比如用哈希表把两层循环的 O(n²) 查找降到 O(n)。

1.3 最好 / 最坏 / 平均复杂度#

以快排为例：

• 最好：O(n log n)，每次 pivot 正好在中间
• 平均：O(n log n)
• 最坏：O(n²)，数组已经有序且每次选最左端作为 pivot

实际工程中常常用"随机选 pivot"或"三数取中"来规避最坏情况。

2 · 数组与链表#

2.1 数组#

数组是连续内存存储的同类型数据集合。

int arr[5] = {1, 2, 3, 4, 5};  // C++ 静态数组
vector<int> v = {1, 2, 3};     // C++ 动态数组

优点：

• 随机访问 O(1)：通过 arr[i] 直接计算地址
• CPU 缓存友好：连续内存命中率高

缺点：

• 插入/删除 O(n)，因为需要搬移后续元素
• 大小固定或扩容时需要重新分配内存（如 vector 扩容通常是 2 倍）

2.2 链表#

链表是非连续内存，每个节点保存数据和下一个节点的指针。

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

优点：

• 插入/删除已知位置节点 O(1)
• 大小动态变化，无需扩容

缺点：

• 随机访问 O(n)
• 每个节点多一个指针开销
• CPU 缓存不友好

链表三板斧：

1. 快慢指针：找中点、判环
2. 虚拟头节点：统一头节点和非头节点的处理
3. 反转链表：迭代法和递归法都要会

2.3 什么时候用数组，什么时候用链表？#

3 · 栈与队列#

3.1 栈（Stack）#

后进先出（LIFO）。想象一摞盘子，只能从最上面取和放。

stack<int> st;
st.push(1);
st.push(2);
int top = st.top(); // 2
st.pop();

经典应用：

• 括号匹配：左括号入栈，右括号出栈匹配
• 表达式求值：中缀转后缀、后缀表达式求值
• DFS 非递归实现：栈模拟递归
• 单调栈：求"下一个更大元素"，维护单调递减栈

3.2 队列（Queue）#

先进先出（FIFO）。想象排队买票。

queue<int> q;
q.push(1);
q.push(2);
int front = q.front(); // 1
q.pop();

经典应用：

• BFS：图的层序遍历
• 任务调度：按顺序处理任务
• 滑动窗口最大值：单调队列

3.3 单调栈 / 单调队列#

单调栈用于解决：数组中每个元素左边/右边第一个比它大/小的元素。

vector<int> nextGreater(vector<int>& nums) {
    stack<int> st;
    vector<int> res(nums.size(), -1);
    for (int i = 0; i < nums.size(); i++) {
        while (!st.empty() && nums[i] > nums[st.top()]) {
            res[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}

单调队列用于解决：滑动窗口最值问题。

4 · 哈希表#

4.1 核心原理#

哈希表 = 数组 + 哈希函数。

• 哈希函数把 key 映射成数组下标
• 理想情况下查找、插入、删除都是 O(1)

d = {}
d["apple"] = 5
print(d["apple"])  # 5

4.2 哈希冲突#

不同 key 映射到同一个下标，称为冲突。解决方式：

• 链地址法：每个桶维护一个链表
• 开放地址法：冲突时按某种策略探测下一个位置
  • 线性探测、二次探测、双重哈希

负载因子 = 元素个数 / 桶数量。负载因子过大时性能下降，需要扩容（rehash）。

4.3 常见应用#

1. 计数 / 频率统计：

   from collections import Counter
   cnt = Counter([1, 2, 2, 3, 3, 3])

2. 去重：

   unique = list(set(nums))

3. 两数之和：用哈希表把 O(n²) 降到 O(n)

   def twoSum(nums, target):
       seen = {}
       for i, x in enumerate(nums):
           if target - x in seen:
               return [seen[target - x], i]
           seen[x] = i

4. LRU 缓存：哈希表 + 双向链表实现 O(1) 的 get 和 put

5 · 树与二叉树#

5.1 二叉树基础#

二叉树：每个节点最多有两个子节点。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

遍历方式：

• 前序：根 → 左 → 右
• 中序：左 → 根 → 右
• 后序：左 → 右 → 根
• 层序：BFS

重要性质：二叉搜索树的中序遍历结果是有序的。

5.2 二叉搜索树（BST）#

• 左子树所有节点 < 根节点
• 右子树所有节点 > 根节点
• 查找 / 插入 / 删除：O(log n) 平均，O(n) 最坏

5.3 平衡树#

BST 退化成链表后效率变成 O(n)。平衡树通过旋转保持平衡：

• AVL 树：左右子树高度差不超过 1
• 红黑树：更宽松的平衡规则，旋转次数少
  • C++ std::map/set、Java TreeMap、Linux 内核 CFS 都用红黑树

5.4 堆（优先队列）#

堆是完全二叉树，满足父节点 ≥ 子节点（大顶堆）或父节点 ≤ 子节点（小顶堆）。

priority_queue<int, vector<int>, greater<int>> minHeap; // 小顶堆

应用：

• 堆排序：O(n log n)，原地排序
• Top-K 问题：维护 K 个最大/最小元素
• Dijkstra 最短路径：每次取距离最近的节点

6 · 图论基础#

6.1 图的表示#

• 邻接矩阵：graph[i][j] 表示 i 到 j 是否有边
  • 适合稠密图，空间 O(V²)
• 邻接表：每个节点保存邻居列表
  • 适合稀疏图，空间 O(V + E)

vector<vector<int>> graph(n); // 邻接表
graph[u].push_back(v);        // u -> v

6.2 遍历#

BFS：

queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : graph[u]) {
        if (!visited[v]) {
            visited[v] = true;
            q.push(v);
        }
    }
}

DFS：递归或栈实现。

6.3 最短路径#

• Dijkstra：单源最短路径，无负权边
• Bellman-Ford：可处理负权边，检测负环
• Floyd：多源最短路径，O(V³)

6.4 最小生成树#

• Kruskal：按边权排序，用并查集判断是否成环
• Prim：从一个点出发，逐步加入最小边

7 · 排序算法#

• 快排：实际最快，但最坏 O(n²)，可用随机 pivot 规避
• 归并：稳定排序，适合链表和外部排序
• 堆排：空间 O(1)，适合内存受限场景

8 · 二分查找#

二分查找前提是数组有序。核心代码：

int left = 0, right = n - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
}
return -1;

为什么 mid = left + (right - left) / 2 而不是 (left + right) / 2？ 防止 left + right 整数溢出。

二分查找的变体：

• 查找第一个等于 target 的位置
• 查找最后一个等于 target 的位置
• 查找第一个大于 target 的位置
• 查找最后一个小于 target 的位置

二分答案：答案具有单调性时，对值域二分而非下标二分。例如"最小化最大值"类问题。

9 · 动态规划#

9.1 核心思想#

动态规划 = 递归 + 记忆化，或自底向上的填表。

三个关键问题：

1. 状态定义：dp[i] 代表什么？
2. 状态转移方程：dp[i] 如何从前面状态推导？
3. 初始化：边界条件是什么？

9.2 爬楼梯问题#

def climbStairs(n):
    if n <= 2: return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

状态转移：dp[i] = dp[i-1] + dp[i-2] 含义：爬到第 i 级，可以从 i-1 迈一步，或从 i-2 迈两步。

空间优化：只保留前两个状态：

def climbStairs(n):
    if n <= 2: return n
    prev2, prev1 = 1, 2
    for i in range(3, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

9.3 背包问题#

0/1 背包：每件物品只能用一次。

for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

注意内层循环从大到小，保证每件物品只用一次。

完全背包：每件物品可以用无限次。

for (int i = 0; i < n; i++) {
    for (int j = w[i]; j <= W; j++) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

内层循环从小到大。

9.4 最长公共子序列（LCS）#

dp[i][j] = 表示 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度
if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

10 · 刷题策略#

10.1 高频题型#

1. 双指针 / 滑动窗口
2. 前缀和 / 差分
3. 单调栈 / 单调队列
4. 二分查找与二分答案
5. BFS / DFS / 回溯
6. 动态规划
7. 贪心
8. 并查集
9. 拓扑排序
10. Trie / 线段树 / 树状数组

10.2 刷题方法#

• 按专题刷，不要随机刷。比如连续一周只刷动态规划。
• 先独立思考 15-20 分钟。想不出再看题解。
• 看懂后自己写一遍，不要直接复制。
• 总结模板：把同类型题目的套路整理下来。
• 定期复习：一周前的错题重做一遍。
• 周赛练手速：LeetCode Weekly Contest、Codeforces。

10.3 面试准备#

• 算法题 + 项目经历 + 系统设计 = 面试铁三角
• 写题时边写边讲思路，不要闷头写
• 先给出暴力解法，再优化，体现思考过程
• 边界条件：空输入、单元素、最大值/最小值