跳到主要内容

Algorithms & Data Structures

"An algorithm must be seen to be believed." — Donald Knuth

掌握算法的关键在于识别模式，而非记忆答案。本综合指南涵盖了面试准备和实际后端工程中必不可少的数据结构与算法模式。

🎯 为什么这很重要​

面试角度​

  • 80%+ 的编程面试题目集中在数组、字符串和数据结构上
  • 公司期望你对核心算法（DFS、BFS、DP、二分查找）非常熟练
  • 模式识别有助于通过类比已知模式来解决未见过的题目

后端工程角度​

  • 数据结构直接影响系统性能（HashMap 实现 O(1) 查找，B+ 树用于数据库索引）
  • 算法驱动关键功能（搜索引擎使用字典树，路径规划使用 Dijkstra 算法）
  • O(n²) 和 O(n log n) 之间的性能差异可能决定系统的可扩展性

实际影响：后端工程师选择错误的数据结构可能会使 API 响应时间从 10ms 退化到 1 秒——100 倍的性能下降，严重影响用户体验。

📚 学习路径​

阶段一：基础（从这里开始）​

这些是面试中出现频率最高的主题：

  1. 数组与字符串 - 内存布局、StringBuilder、二维数组
  2. HashMap 与 HashSet - 哈希函数、冲突解决、负载因子
  3. 树 - BST、遍历、LCA、序列化
  4. 双指针 - 对向指针、快慢指针

时间投入：2-3 周 | 面试频率：60%+

阶段二：核心模式​

在基础上学习算法模式：

  1. 链表 - 反转、环检测、合并操作
  2. 栈与队列 - ArrayDeque、单调栈、优先队列
  3. 滑动窗口 - 固定窗口和动态窗口、子串问题
  4. 二分查找 - 标准二分查找、旋转数组、下界/上界

时间投入：2-3 周 | 面试频率：25%+

阶段三：进阶主题​

攻克更复杂的数据结构：

  1. 堆 - 二叉堆、PriorityQueue、Top K 问题
  2. 图 - BFS/DFS、Dijkstra、拓扑排序
  3. 动态规划 - 记忆化搜索、列表法、优化问题

时间投入：3-4 周 | 面试频率：15%+

阶段四：专项专题​

专用数据结构：

  1. 字典树 - 前缀树、自动补全、字典应用
  2. 排序 - 归并排序、快速排序、TimSort、非比较排序
  3. 贪心算法 - 活动选择、区间调度、哈夫曼编码
  4. 回溯 - 排列、组合、N 皇后
  5. 搜索策略 - 插值搜索、指数搜索、矩阵搜索

时间投入：2-3 周 | 面试频率：5%+

🏗️ 数据结构参考​

复杂度一览​

结构访问查找插入删除使用场景
ArrayO(1)O(n)O(n)O(n)随机访问，小型数据集
ArrayListO(1)O(n)O(1)*O(n)动态数组，频繁访问
LinkedListO(n)O(n)O(1)O(1)频繁插入/删除
HashMap-O(1)*O(1)*O(1)*快速查找，缓存
TreeMap-O(log n)O(log n)O(log n)有序迭代，范围查询
HashSet-O(1)*O(1)*O(1)*去重，成员判断
PriorityQueue-O(n)O(log n)O(log n)优先级任务，Top K
Trie-O(L)O(L)O(L)前缀搜索，自动补全

*平均情况；哈希函数不佳时最坏情况为 O(n)

Java 集合快速参考​

// Lists
List<Integer> arrayList = new ArrayList<>();      // 快速访问
List<Integer> linkedList = new LinkedList<>();     // 快速插入/删除

// Sets
Set<Integer> hashSet = new HashSet<>();             // 快速，无序
Set<Integer> treeSet = new TreeSet<>();             // 有序，O(log n)

// Maps
Map<K, V> hashMap = new HashMap<>();                // 快速，无序
Map<K, V> treeMap = new TreeMap<>();                // 有序，O(log n)
Map<K, V> linkedMap = new LinkedHashMap<>();        // 插入顺序

// Deque
Deque<Integer> deque = new ArrayDeque<>();          // 快速，可调整大小
Queue<Integer> queue = new LinkedList<>();         // FIFO
Stack<Integer> stack = new Stack<>();              // LIFO（遗留类）

// Priority Queue
PriorityQueue<Integer> minHeap = new PriorityQueue<>();  // 最小值在顶部
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
    Collections.reverseOrder());                     // 最大值在顶部

🧠 算法模式​

模式识别指南​

模式使用时机核心洞察
双指针有序数组，配对求和，回文串从两端向中间收缩
滑动窗口带约束的子串/子数组维护有效窗口
快慢指针环检测，中间元素以不同速度移动
合并区间重叠区间按起始时间排序
二分查找有序数组，单调谓词每次迭代排除一半
贪心局部最优 → 全局最优当下做出最优选择
回溯所有组合/排列探索所有可能，剪枝无效方案
DP重叠子问题，最优子结构缓存计算结果
BFS最短路径（无权），层序遍历基于队列的探索
DFS路径查找，连通性基于栈/递归的探索

📊 面试准备清单​

必须掌握（85% 的面试）​

  • ✅ 数组/字符串操作
  • ✅ HashMap 的使用和内部原理
  • ✅ 二叉树遍历（递归 + 迭代）
  • ✅ BST 操作（查找、插入、验证）
  • ✅ BFS/DFS 基础
  • ✅ 双指针技巧
  • ✅ 二分查找实现
  • ✅ 时间/空间复杂度分析

应该掌握（12% 的面试）​

  • ✅ 堆和 PriorityQueue
  • ✅ 图的环检测
  • ✅ 拓扑排序
  • ✅ 动态规划基础（一维 DP）
  • ✅ 带记忆化的递归
  • ✅ 链表反转

锦上添花（3% 的面试）​

  • ⭐ 进阶 DP（二维 DP，状态机）
  • ⭐ 进阶图算法（Dijkstra，A*）
  • ⭐ 字典树和基数树
  • ⭐ 高级排序算法
  • ⭐ 字符串算法（KMP，Rabin-Karp）

🔗 交叉引用​

相关主题​

📝 学习建议​

高效练习策略​

  1. 学习模式，而非题目

    • 每个模式做 2-3 道题
    • 关注解题思路，不要死记硬背

  2. 从零实现

    • 核心算法不要使用库函数
    • 自己构建 HashMap、BST、Queue

  3. 解题后分析

    • 空间可以优化吗？
    • 如果输入已排序会怎样？
    • 考虑了边界情况吗？

  4. 间隔重复

    • 1 周、1 个月后重温题目
    • 主动回忆 > 被动阅读

复杂度分析经验法则​

  • 对 n 个元素的单层循环：O(n)
  • 对 n 个元素的嵌套循环：O(n²)
  • 对 n 个元素的二分查找：O(log n)
  • 对 n 个元素的排序：O(n log n)
  • 遍历二维数组（m × n）：O(m × n)
  • 递归调用分支到 k 个规模为 n 的子问题：无记忆化时为 O(kⁿ)

🚀 快速开始​

初学者？从这里开始​

  1. 阅读 数组与字符串 → 实现示例
  2. 练习 双指针 → 在 LeetCode 上做 5 道题
  3. 学习 HashMap → 理解冲突
  4. 复习 树 → 掌握遍历

中级水平？填补空白​

  1. 略读 堆 → 用数组实现堆
  2. 学习 图 → BFS 与 DFS 的使用场景
  3. 练习 DP → 从一维 DP 开始
  4. 学习 滑动窗口 → 子串问题

高级水平？优化提升​

  1. 掌握 进阶 DP → 二维 DP，状态机
  2. 学习 贪心算法 → 证明技巧
  3. 学习 字典树 → 空间优化
  4. 练习 回溯 → 剪枝策略

准备好开始了吗？ 从侧边栏选择一个主题，开始构建你的算法工具箱！