1. 从“练气”到“算法”一个程序员的修炼隐喻最近在整理自己的算法学习笔记翻到几年前写下的“算法修炼之练气篇”这个标题不禁哑然失笑。这大概是每个程序员在入门算法时都会有的心路历程面对那些看似玄奥的排序、搜索、动态规划感觉就像在修炼一门高深的内功需要一层层地打基础、破瓶颈。今天我想把这个有点中二但无比贴切的“练气十九层”体系重新梳理一遍分享给正在算法之路上“筑基”的你。所谓的“练气篇”指的就是算法与数据结构中最基础、最核心、最必须掌握的那部分知识。它不追求奇技淫巧而是扎扎实实地构建你对计算思维的理解。这“十九层”并非严格的等级划分而是十九个关键的知识模块或能力阶段。每突破一层你对程序世界的理解就更通透一分解决实际编码问题的“内力”也就更深厚一分。无论你是正在准备面试的校招生还是希望夯实基础的在职工程师这套“心法”都能帮你系统地查漏补缺建立起稳固的算法思维大厦。2. 练气前五层数据结构筑基——理解程序的“容器”如果把算法比作武功招式那么数据结构就是承载这些招式的身体与经脉。前五层我们专注于打造最坚实的数据容器基础。2.1 第一层数组与字符串——万物之始数组是内存中一段连续的存储空间这是所有数据结构的物理基础。理解数组关键在于掌握其随机访问O(1)时间复杂度和连续内存两大特性。为什么很多算法题喜欢用数组因为它的访问效率极高。但硬币的另一面是插入和删除元素可能需要移动大量后续元素代价是O(n)。字符串可以看作是字符数组但它有独特的操作如子串匹配、翻转、分割等。这一层的修炼要点是边界处理循环时对索引i和长度n的把握是无数bug的源头。“差一错误”Off-by-one error是这一层最常见的“心魔”。双指针技巧这是处理数组/字符串的利器。快慢指针用于链表环检测、有序数组去重左右指针用于二分查找、两数之和、反转字符串等。理解双指针的本质是通过两个索引的协同遍历降低时间复杂度。原地操作很多题目要求“原地修改”不占用额外空间。这需要你巧妙利用已有数组空间进行元素交换或覆盖例如“移动零”问题。注意在Java中String是不可变的任何修改都会生成新对象。而在C或Python中字符串有时可视为可变字符列表。这个语言特性差异会直接影响解题策略。2.2 第二层链表——指针的艺术链表通过指针将离散的内存块串联起来。它解决了数组插入删除慢的问题在已知节点位置时链表操作是O(1)但牺牲了随机访问能力访问需要O(n)遍历。这一层的核心是建立清晰的“指针”或“引用”心智模型。你需要像在脑海中画图一样跟踪每个节点的next和prev指针的指向变化。虚拟头节点Dummy Node这是链表题中最实用的技巧之一。当链表的头节点可能发生变化时例如删除头节点引入一个dummy节点指向真正的头可以极大简化边界条件判断让代码更统一、更健壮。经典问题链反转链表、合并两个有序链表、寻找链表中点、判断链表是否有环并找到环入口。这些问题层层递进是检验指针操作熟练度的最佳试金石。以反转链表为例不仅要知道迭代的三指针法还要理解递归解法是如何从后向前重建链接的这有助于理解递归栈与链表结构的关系。2.3 第三层栈与队列——受限的线性表栈LIFO后进先出和队列FIFO先进先出是两种操作受限的线性表。它们的威力不在于存储而在于其特定的操作顺序所蕴含的算法逻辑。栈非常适合处理具有“最近相关性”的问题。例如括号匹配({[]})、表达式求值、函数调用栈模拟、浏览器的前进后退。递归的本质就是栈所以很多递归问题可以用栈来迭代实现。队列常用于“公平排队”的场景如BFS广度优先搜索、缓存实现如LRU Cache的辅助结构、任务调度。双端队列Deque则结合了两者的特点在滑动窗口最大值等问题中表现出色。这一层的修炼要习惯用栈来“暂存”数据等待后续处理。例如在单调栈中我们利用栈维护一个单调递增或递减的序列可以高效找到每个元素左边或右边第一个比它大或小的元素这是解决“接雨水”、“柱状图中最大矩形”等难题的关键。2.4 第四层哈希表——时空转换的魔法哈希表是算法世界里的“空间换时间”的典范。通过哈希函数它将键Key映射到存储位置从而实现近乎O(1)的查找、插入和删除。这一层的核心是理解其原理与代价。冲突解决再好的哈希函数也可能产生冲突两个不同的键映射到同一位置。链地址法拉链法和开放地址法是两种主流策略。你需要知道它们各自的优缺点。应用场景快速查找两数之和、去重、计数统计频率、缓存Memoization用于优化递归如斐波那契数列。在Python中dict和set就是基于哈希表实现的在Java中是HashMap和HashSet。实践心得很多题目中哈希表扮演着“记录员”或“索引表”的角色。当你在暴力解法中发现需要反复在一个集合中查找某个元素是否存在时就该立刻想到哈希表。例如判断链表是否有环除了快慢指针法用HashSet记录已访问节点也是一种直观解法虽然空间复杂度为O(n)。2.5 第五层基础树结构——层次与分治的体现树是典型的非线性数据结构代表着层次关系和分治思想。二叉树是其中最基础、最重要的形态。遍历前序、中序、后序的递归写法必须信手拈来。更重要的是掌握它们的迭代写法使用栈这能加深你对遍历过程的理解。层次遍历使用队列则用于BFS。递归思维树的大部分操作天然适合递归。“处理当前节点然后递归处理左右子树”是基本模式。例如求树的高度、判断对称二叉树、计算路径和等。二叉搜索树BST这是树的特化其中序遍历是升序序列。BST的查找、插入、删除操作的平均时间复杂度是O(log n)。理解BST的性质是后续理解平衡二叉树如AVL、红黑树以及数据库索引B树的基础。修炼至此你已经拥有了最常用的几类“容器”。接下来我们要学习如何用这些容器去施展更精妙的“算法”。3. 练气六至十层核心算法初成——掌握解决问题的“套路”有了数据结构作为武器接下来要学习通用的算法范式。这五层是算法思维的骨架。3.1 第六层排序算法——秩序的建立排序是计算机科学的经典问题它不仅是算法效率的直观体现其思想也渗透在其他算法中。比较排序的极限基于比较的排序算法时间复杂度下界是O(n log n)。归并排序和快速排序达到了这个最优界。分治思想实践归并排序是“先分后治”的典范稳定但需要额外空间。快速排序是“治中带分”的代表原地排序平均效率高但不稳定。理解它们的递归树和分区Partition过程至关重要。线性排序当数据有特殊性质时桶排序、计数排序、基数排序可以在O(n)时间内完成它们突破了比较排序的下界是“空间换时间”的另一个例子。实战选择在实际开发中我们通常直接调用语言库的排序函数如Arrays.sort()、sorted()。但面试中手写快速排序的partition或者分析不同排序算法在特定数据如近乎有序数组、大量重复值下的表现是常见的考察点。3.2 第七层二分查找——高效的搜索哲学二分查找不仅仅是在有序数组里找某个数。它是一种基于“有序”和“可二分性”的将问题规模指数级缩小每次砍掉一半的搜索思想。框架统一经典的二分查找有三种写法对应不同的循环条件和边界更新。我推荐掌握一种清晰且不易出错的模板并始终坚持使用。核心在于明确搜索区间左闭右闭[left, right]还是左闭右开[left, right)以及循环终止条件。变体与应用查找第一个等于目标值的位置、最后一个等于目标值的位置、第一个大于等于目标值的位置……这些变体是面试高频题。更重要的是二分思想可以应用于答案本身具有单调性的问题例如“在有序矩阵中搜索”、“寻找旋转排序数组中的最小值”、“吃香蕉的珂珂”、“分割数组的最大值”。这类问题的关键是构建一个判定函数f(x)使得答案ans左侧都满足条件右侧都不满足然后对ans进行二分搜索。3.3 第八层双指针与滑动窗口——线性时间的优雅双指针我们在数组层提过这里将其升华为一类算法思想。滑动窗口是双指针的一种特殊形式维护一个动态的区间。同向双指针通常用于处理有序数组的合并、去重或链表问题。快慢指针是典型代表。相向双指针常用于有序数组的“两数之和”、“三数之和”或反转类问题。滑动窗口用于解决子串、子数组的相关问题如“无重复字符的最长子串”、“最小覆盖子串”、“长度最小的子数组”。其核心是用left和right指针界定窗口。right向右扩张寻找可行解。当窗口满足条件后left向右收缩优化可行解并寻找下一个可能解。在扩张和收缩过程中用合适的数据结构如哈希表记录字符频次高效更新窗口状态。 掌握滑动窗口关键在于识别出“窗口内性质”可以在指针移动时被增量更新从而避免每次重新计算整个窗口。3.4 第九层广度优先搜索BFS与深度优先搜索DFS——遍历与搜索的基石这是处理图、树、网格等结构最根本的两种策略。BFS借助队列一层一层向外扩散。它天然适合求解最短路径、最小步数等问题在无权图中。例如二叉树的层序遍历、迷宫的最短路径、单词接龙。DFS借助递归栈或显式栈一条路走到黑走不通再回溯。它适合求解所有可能解排列、组合、连通性、拓扑排序等问题。回溯法是DFS的一种通过“尝试-回退”来搜索解空间。visited集合在图中遍历时必须使用visited集合或数组来标记已访问节点防止重复访问陷入循环。这是新手极易忽略的点。网格类DFS/BFS题目常给出一个二维字符网格如“岛屿数量”、“被围绕的区域”。这类问题有固定套路遍历每个单元格如果是目标元素如‘1’则启动DFS/BFS将其所有相连的同元素标记计数加一。注意处理网格边界。3.5 第十层递归与回溯——自己调用自己的艺术递归是理解许多高级算法如DFS、分治、动态规划的钥匙。回溯则是构建所有可能解的 systematic 方法。递归三要素明确递归函数定义这个函数要干什么、找到基线条件何时停止递归、确定递归关系如何缩小问题规模并调用自身。写递归时一定要相信递归函数能完成它的子任务递归信任。回溯框架回溯问题通常是在一个集合中寻找满足条件的所有子集或排列。其代码框架像一棵决策树的深度遍历def backtrack(路径 选择列表): if 满足结束条件: 结果.add(路径) return for 选择 in 选择列表: 做选择将选择加入路径 backtrack(路径 新的选择列表) # 递归 撤销选择从路径中移除该选择剪枝这是回溯算法的优化灵魂。在递归树的每一层如果提前判断当前分支不可能产生有效解就直接跳过不再深入。例如在求解“N皇后”时在同一列或对角线上已有皇后当前行的这个位置就不用尝试了。有效的剪枝能将指数级复杂度大大降低。4. 练气十一至十五层进阶思维塑造——从暴力到优化掌握了基础套路后我们需要学习如何优化如何将看似复杂的问题分解或转化。4.1 第十一层分治算法——化整为零分而治之分治是递归的典型应用将一个大问题分解成若干个规模较小的相同子问题递归解决再合并结果。归并排序和快速排序是分治的完美例子。与动态规划的区别分治的子问题通常互不重叠各自独立。而动态规划的子问题有重叠因此可以用记忆化来避免重复计算。经典应用除了排序还有“计算逆序对”、“最大子数组和”这里的分治解法不是最优但有助于理解思想、“为运算表达式设计优先级”等。分治思想在MapReduce等分布式计算框架中也是核心。4.2 第十二层贪心算法——局部最优的冒险贪心算法在每一步都做出当前看来最优的选择希望以此导致全局最优解。它高效但并不总能得到全局最优解。因此使用贪心必须能证明其正确性或者问题本身满足贪心选择性质。适用场景活动选择问题选择最多不重叠活动、霍夫曼编码、最小生成树Prim/Kruskal算法、最短路径Dijkstra算法。以及一些简单的区间问题如“用最少数量的箭引爆气球”。无法使用贪心的情况经典的“背包问题”0-1背包就不能用贪心按价值重量比排序因为局部最优无法保证全局最优。这时就需要动态规划。实践技巧当一个问题看起来可以“每一步都选最好的”先尝试举反例。如果举不出反例再思考如何证明。面试中通常考察的是经典的、已知的贪心问题。4.3 第十三层动态规划入门——记忆化搜索与状态定义动态规划是算法学习的第一个大分水岭。它的核心思想是将复杂问题分解为重叠子问题并通过保存子问题的解来避免重复计算。从递归到记忆化搜索这是理解DP的最佳路径。先写出暴力递归解法通常是指数复杂度然后你会发现递归树中有大量重复计算。这时加入一个缓存通常是数组或字典在递归函数返回前存储计算结果下次遇到相同参数直接返回缓存值。这就是“自顶向下”的记忆化搜索它已经具备了DP的核心思想。状态定义这是DP最关键的步骤。dp[i]或者dp[i][j]到底代表什么必须清晰无误。例如在“爬楼梯”问题中dp[i]表示爬到第i阶楼梯的方法数在“最长递增子序列”中dp[i]表示以第i个数字结尾的最长递增子序列长度。经典一维DP斐波那契数列、爬楼梯、打家劫舍、零钱兑换求最少硬币数。通过这些题目掌握状态转移方程的推导。4.4 第十四层动态规划进阶——二维与背包问题当状态由一个变量无法描述时就需要升维。二维DP状态由两个维度定义通常是dp[i][j]。例如“最长公共子序列”中dp[i][j]表示text1[0...i]和text2[0...j]的最长公共子序列长度。“编辑距离”、“不同路径”也都是经典二维DP。背包问题这是DP的“必修课”。0-1背包每个物品最多选一次、完全背包每个物品无限选、多重背包。核心是理解dp[i][j]定义考虑前i件物品在容量为j的背包下所能获得的最大价值。状态转移对于0-1背包dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])。空间优化可以将二维DP数组优化为一维数组但遍历顺序需要特别注意0-1背包逆序完全背包正序。解题框架拿到一个问题先判断它是否具有“最优子结构”和“重叠子问题”。然后尝试定义状态推导状态转移方程确定初始条件和遍历顺序。多画DP表手动模拟填表过程是理解的不二法门。4.5 第十五层位运算——底层效率的利器位运算直接操作整数在内存中的二进制位速度极快。在一些特定场景下它能用简洁的代码实现巧妙的功能。基本操作与、或|、异或^、取反~、左移、右移。要熟悉它们的运算规则。常用技巧判断奇偶x 1结果为1则是奇数0则是偶数。取最低位的1lowbit x -x。这在树状数组中广泛应用。消去最低位的1x x (x - 1)。可用于统计一个数二进制中1的个数Brian Kernighan算法。异或的妙用a ^ a 0,a ^ 0 a。可用于“只出现一次的数字”其他数字出现两次这类问题。状态压缩当状态可以用少量布尔值表示时可以用一个整数的不同二进制位来存储这在DFS/BFS中用于表示访问状态或在动态规划中表示子集如“旅行商问题”的雏形。注意位运算的优先级通常较低使用时务必加上括号避免意想不到的错误。5. 练气十六至十九层融会贯通与实战淬炼最后四层不再局限于单一知识点而是综合运用并面向真实场景。5.1 第十六层高级数据结构初探——树结构的深化基础二叉树之外还有更多强大的树形结构。堆优先队列一种特殊的完全二叉树父节点的值总是大于等于最大堆或小于等于最小堆子节点的值。它可以在O(log n)时间内插入元素和取出最值。应用场景求Top K问题用最小堆、实时数据流的中位数用两个堆维护、Dijkstra算法中高效获取当前最短路径节点。并查集用于处理不相交集合的合并与查询问题。它支持两种操作find查找元素所属集合代表和union合并两个集合。通过路径压缩和按秩合并优化这两个操作的平均时间复杂度接近常数。应用场景判断图中两个节点是否连通、朋友圈问题、岛屿数量动态连接问题。字典树Trie专门用于处理字符串集合的数据结构。它能高效地存储和检索字符串特别是用于前缀匹配。搜索引擎的自动补全、单词拼写检查是其典型应用。实现时每个节点包含一个字符指针数组和一个标志位表示是否为一个单词的结尾。5.2 第十七层图论基础——关系网络的抽象图是比树更一般的结构由顶点和边组成。算法面试中图论问题通常不会涉及太复杂的算法但基础必须牢固。图的表示邻接矩阵适合稠密图、邻接表适合稀疏图更省空间。你需要熟悉如何用代码构建这两种结构。遍历DFS和BFS同样适用于图。这是解决许多图论问题的起点如判断连通性、寻找路径。拓扑排序针对有向无环图DAG将顶点排成一个线性序列使得对于任何有向边u-vu在序列中都出现在v之前。这是课程安排、编译依赖解析等问题的核心。通常用BFS入度表或DFS实现。最短路径掌握Dijkstra算法非负权图单源最短路径和Floyd-Warshall算法多源最短路径的思想。面试中通常不要求手写完整代码但需要理解其基于贪心或动态规划的原理。并查集的应用在图论中并查集常用于判断无向图中是否有环或进行连通分量的划分。5.3 第十八层设计类问题——面向对象的算法思维这类问题考察你将算法和数据结构封装成实际可用的“工具”或“系统”的能力。它更贴近真实工程场景。经典设计LRU缓存、LFU缓存、实现Trie、实现计算器、扁平化嵌套列表迭代器、二叉树的序列化与反序列化。解题思路明确需求仔细阅读题目明确每个方法的功能、输入、输出和边界条件。选择数据结构这是最关键的一步。例如LRU缓存需要快速查找哈希表和维护访问顺序双向链表。LFU缓存则需要同时维护频率和访问时间结构更复杂。设计API与内部状态定义类的数据成员和方法签名。思考哪些操作是高频的如何设计能使这些操作高效。处理并发如果提到面试中如果提到“线程安全”通常需要指出关键操作需要加锁但一般不要求实现具体的锁机制。沟通能力在面试中设计类问题往往需要你边写边讲解释为什么选择这个数据结构时间复杂度如何。清晰的沟通和有条理的分析比一次性写出完美代码更重要。5.4 第十九层模拟与代码实现——细节是魔鬼最后一层回归到最朴素的“模拟”和“实现”。有些问题没有取巧的算法就是考察你对过程的理解和代码实现的严谨性。模拟题如“螺旋矩阵”、“旋转图像”、“生命游戏”、“字符串转换整数”。这类题目通常逻辑清晰但边界条件极多代码容易写乱。实现题要求你实现一个特定的数据结构或算法如“实现一个线程池”简化版、“实现一个阻塞队列”。这考察你对底层机制的理解。修炼要点画图在动手写代码前用几个简单的例子在纸上模拟整个过程找出规律和边界。模块化将复杂过程分解成几个清晰的函数或步骤。例如旋转图像可以先转置再翻转每一行。防御性编程对输入进行合法性检查空值、越界。在循环中谨慎处理索引。测试驱动写完代码后用题目给的例子、边界例子空、单元素、最大值、最小值和自创的反例进行测试。 这一层没有高深的技巧比拼的是扎实的基本功、清晰的逻辑和严谨的态度。这是将前面所有“内力”转化为无错误“输出”的最后一步也是最见功力的一步。走完这“练气十九层”你便算是在算法世界里打下了坚实的地基。但这仅仅是开始后面还有“筑基”、“金丹”等更广阔的境界如高级图论、字符串匹配、数学与数论、系统设计等等待探索。真正的修炼在于持续地思考、刷题、总结将每一个知识点内化于心外化于行。当你拿到一个新问题能迅速将其归类并调动脑海中的“武器库”组合出击时你就真正拥有了算法工程师的“内力”。