面试字节跳动的时候，面试官问了我一道算法题：在二叉树里找两个节点的最近公共祖先。我当时脑子一片空白，憋了半天想出来的解法漏洞百出。面试官很有耐心，引导我想出了正确答案，但我知道这次大概率是挂了。

回去之后痛定思痛，开始系统性地学习算法和数据结构。每天刷两道题，周末复盘总结。两个月后算法能力明显提升，后来再面试不管是社招还是校招，算法题基本都能做出来。

这篇文章把我学习算法和数据结构的心得整理了一下，希望能帮到有需要的人。不讲太底层的东西，重点是梳理知识体系和常见题型。

时间复杂度和空间复杂度要搞懂

评价一个算法好不好，首先看时间复杂度和空间复杂度。时间复杂度是指执行时间随数据规模增长的趋势，空间复杂度是指内存占用随数据规模增长的趋势。

常见的时间复杂度按从小到大排：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)、O(n!)。面试中常考的是前四种，后两种数据规模稍大就不可用了。

分析复杂度的时候，不要被代码行数迷惑。关键看循环嵌套的层数，以及循环里数据规模的变化。比如二分查找每次把问题规模减半，所以是O(log n)；冒泡排序有两层循环，所以是O(n²)。

刷题的时候养成习惯，做之前先想想复杂度，初步思路确定后再动手写。写完了再分析一遍，看看有没有更优的解法。

数组和链表是基础

数组是最基本的数据结构，存储连续内存，支持随机访问。优点是访问快，缺点是插入删除要搬移数据。链表解决了数组插入删除效率低的问题，但访问需要顺序查找。

常见的链表问题有：反转链表、合并两个有序链表、删除倒数第N个节点、环形链表检测。这些问题用双指针技巧就能解决，面试中经常出现。

数组问题常见的技巧有：二分查找（有序数组）、双指针（对撞指针、快慢指针）、滑动窗口（前缀和、子数组问题）、前缀和思想（二维矩阵路径问题）。

有些问题用数组思路不好解，换成链表思路就简单了；反过来也一样。刷题多了会有感觉，什么时候该用什么数据结构。

栈和队列要会用

栈的特点是后进先出，队列的特点是先进先出。这两个数据结构看起来简单，但组合起来能解决很多问题。

单调栈能解决的问题：Next Greater Element、柱状图最大矩形、每日温度。单调队列能解决的问题：滑动窗口最大值、限流算法。

括号匹配、表达式求值、函数调用栈这些场景，用栈处理很自然。广度优先搜索用队列，深度优先搜索用栈或者递归。

优先队列（堆）是一种特殊的数据结构，能以O(1)时间获取最大或最小元素，常用于TopK问题、合并有序文件、中位数计算等场景。

哈希表是神器

哈希表能以O(1)平均时间完成查找、插入、删除。这么好的特性让它成为面试和工程中的利器。

常见的哈希问题：两数之和（利用target减去当前数来查找）、三数之和（两数之和的扩展）、快乐数（检测循环）、前K个高频元素（统计频率）。

要注意哈希冲突和哈希碰撞。实际工程中用的哈希函数和哈希表实现是经过精心设计的，但在算法面试里一般不需要考虑这些底层问题。

有些问题表面上看不是哈希问题，但如果你找到了合适的key映射，就能用哈希表来优化。比如字符串匹配用滑动窗口加哈希来判断是否是字母异位词。

树结构很常见

面试中常见的树结构是二叉树。二叉树的遍历有前序、中序、后序、层序四种，各有各的应用场景。

前序遍历用于复制树、序列化二叉树；中序遍历在二叉搜索树里能得到有序序列，用于查找某个值的排名或者某个排名的值；后序遍历用于删除树、计算路径和。

二叉搜索树（BST）是一种特殊的二叉树，左子树所有节点小于根，右子树所有节点大于根，天然支持二分查找。常见的面试题有：验证BST、查找 BST中第K小的元素、BST的结构转换。

二叉树的最近公共祖先（LCA）是个经典问题，递归和非递归两种解法都要会。递归的思路是，如果当前节点是p或q，或者p和q分别在左右子树里，则当前节点就是LCA。

图论基础要掌握

图在工程中很常见：社交网络、推荐系统、路径规划都用图来表示。面试中一般考的是有向图、无向图、加权图的最短路径问题。

图的表示有两种方法：邻接矩阵和邻接表。邻接矩阵适合稠密图，邻接表适合稀疏图。实际工程中邻接表用得更多。

图的遍历有深度优先搜索（DFS）和广度优先搜索（BFS）。DFS适合递归实现，能用栈模拟；BFS适合用队列，按层次遍历。

最短路径的经典算法：Dijkstra（单源最短路径，适合非负权图）、Bellman-Ford（能检测负权环）、Floyd-Warshall（多源最短路径）。Dijkstra用堆优化后效率很高。

排序和查找要熟练

排序算法里，快排和归排是重点。快排平均O(n log n)，最坏O(n²)，但实践中往往比归排快；归排稳定O(n log n)，适合对稳定性有要求的场景。

面试常问的还有:topK问题用堆或者快速选择算法、排序数组查找某个元素用二分查找、旋转数组查找用变体二分。

二分查找要注意边界条件：是left < right还是left <= right，mid要不要+1，查找左边界和右边界有什么区别。这些细节没搞清楚，代码很容易写错。

还有一个重要的是二分答案法：当答案具有单调性的时候，可以把求解问题转成判定问题，然后用二分来找最优解。比如求最小最大值、分配问题等。

动态规划很难但很重要

动态规划（DP）是面试中最难的部分，也是区分度最大的部分。DP问题没有固定的模式，关键是找到状态定义和状态转移方程。

常见的DP问题类型：斐波那契数列（入门）、爬楼梯（简单）、打家劫舍（简单）、股票买卖（中等）、字符串编辑距离（中等）、最长递增子序列（中等）。

DP的思路是：把原问题拆成子问题，先求子问题的最优解，再由子问题的最优解组合成原问题的最优解。关键是要找到不同时刻的状态，以及状态之间的转移关系。

做DP问题的一般步骤：定义dp数组的含义、找出状态转移方程、确定初始条件、确定遍历顺序（是从前到后还是从后往前）、举例验证。代码写出来往往很简洁，关键是思路要对。

写在最后

算法和数据结构不是一朝一夕能学好的，需要长期积累。我的经验是每天刷一两道题，理解每道题背后的思路和套路，比盲目追求数量重要得多。

刷题的时候不要死磕，一道题想二十分钟还没思路就看题解，理解了之后自己写一遍。刚开始会觉得很难，坚持下去会越来越顺。

推荐几个我常用的刷题资源：LeetCode中文站按类型刷题、代码随想录的讲解很详细、《算法导论》适合深入理解原理。祝你刷题愉快，面试顺利。