1. 从“练气”到“算法”一个程序员的修炼隐喻最近在整理自己的算法学习笔记翻到几年前写的一个系列标题就叫“算法修炼之练气篇”。当时觉得挺中二现在回头看这个“修炼”的比喻其实意外地贴合算法学习的本质。我们总说程序员要“修炼内功”算法和数据结构就是最核心的内功心法。而“练气篇”对应的正是算法入门与基础夯实阶段。今天我想把这个系列里最核心的二十一个基础知识点重新梳理一遍分享给正在“练气”路上的朋友们。这二十一层不是凭空捏造的关卡而是我结合自己从零开始、面试刷题、再到实际工作中应用算法的经验总结出的二十一个必须打牢的基石。它们环环相扣层层递进就像修炼内功气走经脉每一层都为了下一层更顺畅的运行。很多人学算法一上来就直奔“动态规划”、“图论”这些听起来很高级的章节结果往往碰一鼻子灰信心受挫。问题出在哪根基不牢。算法学习就像盖楼数组、链表、栈、队列这些基础数据结构就是地基和砖块时间复杂度、空间复杂度就是施工图纸上的标尺而递归、排序、查找这些基础思想就是砌墙抹灰的基本功。没有这些“高楼大厦”无从谈起。“练气二十一层”的目的就是帮你把这最底层、最枯燥但最重要的二十一块砖打磨扎实。掌握了这些你再去看那些复杂的算法会发现它们大多是由这些基础模块以不同的方式组合、演化而来的学习起来会事半功倍。2. 第一层到第七层数据结构筑基——理解数据的容器算法作用于数据而数据需要容器来盛放。这前七层我们聚焦于最基础、最常用的线性数据结构。理解它们的物理结构、操作特性以及适用场景是后续所有复杂操作的前提。2.1 第一层数组——最直接的连续空间数组大概是所有人接触到的第一个数据结构。它在内存中占据一块连续的地址空间。这个“连续”特性带来了两个核心特点一是支持随机访问因为你知道首地址通过下标索引就能直接计算出目标元素的内存位置访问时间复杂度是O(1)二是插入和删除效率可能较低因为为了保持连续性在中间位置进行插入或删除时需要移动后续的所有元素。注意很多初学者容易混淆数组的“访问”和“查找”。访问指定下标的元素是O(1)但查找一个值等于target的元素即搜索在无序数组中需要遍历是O(n)。在实际应用中数组是构建更复杂结构如哈希表的基础。在算法题中双指针技巧、滑动窗口算法其底层遍历的载体常常就是数组。理解数组的边界索引从0开始、长度固定静态数组或可变动态数组/列表等特性是基本功中的基本功。2.2 第二层链表——灵活的链式存储链表是为了克服数组插入删除需要移动数据的问题而生的。它的数据元素节点在内存中不必连续每个节点除了存储数据还存储了指向下一个节点地址的指针或引用。正是这个指针像链条一样把零散的节点串了起来。链表的优势在于插入和删除。在已知节点位置的情况下你只需要修改相邻节点的指针指向时间复杂度是O(1)。但它的劣势也源于非连续性不支持随机访问。要访问第N个节点你必须从头节点开始一个一个“next”下去时间复杂度是O(n)。链表主要分为单链表、双链表每个节点有指向前驱和后继的指针和循环链表。双链表在需要向前回溯的场景下更有优势。链表是理解许多高级数据结构如栈、队列、树、图的桥梁也是面试中考查指针操作和边界条件处理如头节点、尾节点、空链表的常客。2.3 第三层栈——后进先出的线性表栈是一种操作受限的线性表只允许在一端栈顶进行插入入栈/push和删除出栈/pop操作遵循后进先出的原则。你可以把它想象成一个羽毛球筒你只能从筒口放入或取出羽毛球最后放进去的总是最先被拿出来。栈的核心应用场景都与“回溯”、“撤销”相关。比如函数调用栈系统在执行函数调用时会压入当前函数的上下文返回地址、局部变量等函数返回时再弹出确保了调用顺序的正确性。表达式求值编译器利用栈来处理运算符的优先级如中缀表达式转后缀表达式。括号匹配遍历字符串遇到左括号就入栈遇到右括号就检查栈顶是否匹配的左括号。浏览器的前进后退通常使用两个栈来实现。栈的实现可以基于数组顺序栈或链表链式栈。理解栈的LIFO特性是解决许多需要“最近相关性”问题的关键。2.4 第四层队列——先进先出的线性表队列是另一种操作受限的线性表它允许在一端队尾插入入队/enqueue在另一端队头删除出队/dequeue遵循先进先出的原则。这就像现实生活中的排队讲究先来后到。队列的应用非常广泛任务调度操作系统中的进程就绪队列。消息队列分布式系统中解耦生产者和消费者。广度优先搜索在图和树的遍历中BFS算法必须使用队列来维护待访问的节点顺序。除了普通队列还有两种重要的变体双端队列两端都可以进行入队和出队操作灵活性更高。循环队列基于数组实现时为了高效利用空间将数组首尾相连。判断队列“空”和“满”的条件是关键通常使用(tail 1) % capacity head判断满head tail判断空。2.5 第五层哈希表——基于快速查找的魔法哈希表散列表是这七层中的一个“质变”。它通过一个哈希函数将任意大小的输入键映射到一个固定范围的索引地址从而支持近似O(1)时间复杂度的查找、插入和删除操作。这就像一本有目录的书你想找某个章节不是一页一页翻而是先查目录找到页码。哈希表的核心在于两个部分哈希函数设计目标是计算快、冲突少、分布均匀。常见的如除留余数法。冲突解决当两个不同的键被映射到同一个索引时怎么办主流方法有链地址法每个索引位置维护一个链表或其他容器所有冲突的元素都放在这个链表里。Java的HashMap就采用此法。开放地址法当发生冲突时按照某种探测序列线性探测、二次探测寻找下一个空闲位置。哈希表的性能在很大程度上取决于负载因子元素数量/桶数量。负载因子过高会导致冲突激增性能退化。因此通常需要设置一个阈值如0.75超过时进行扩容Rehashing。理解哈希表是理解现代编程语言中Dictionary、Map、Set等集合类的基础。2.6 第六层与第七层字符串与字符编码字符串可以看作一个字符数组但它有自己独特的操作如拼接、分割、子串查找、模式匹配等。这一层的关键在于理解字符串的不可变性在许多语言中如Java、Python字符串对象一旦创建其内容就不能改变任何修改操作都会生成一个新对象以及常用的算法如暴力匹配、KMP算法用于高效子串查找。更深一层要意识到字符串背后是字符编码。从ASCII到UnicodeUTF-8, UTF-16等理解编码有助于你处理国际化文本、避免乱码以及在涉及位操作的算法题中某些题目巧妙利用字符的ASCII码范围能洞察本质。例如判断一个字符是否是字母不要写死a到z而应理解其编码规律。3. 第八层到第十二层核心思想初探——理解算法的“套路”掌握了数据的容器接下来要学习操作数据的“思想”。这五层介绍了四种最基础、最强大的算法思想与工具。3.1 第八层时间复杂度与空间复杂度——算法的度量衡这是评估算法优劣的基石。时间复杂度描述算法执行时间随数据规模增长的趋势空间复杂度描述算法占用存储空间随数据规模增长的趋势。我们关注的是渐进复杂度通常用大O记号表示。常见的复杂度有O(1): 常数阶与数据规模无关。O(log n): 对数阶非常高效如二分查找。O(n): 线性阶性能随规模线性增长。O(n log n): 线性对数阶许多高效排序算法的复杂度如归并排序、快速排序的平均复杂度。O(n²): 平方阶常见于简单嵌套循环。O(2^n), O(n!): 指数阶、阶乘阶通常不可接受。分析复杂度时要抓住主要矛盾忽略常数项和低阶项。例如一个循环套一个二分查找的算法复杂度是O(n log n)而不是O(n) * O(log n)。建立复杂度的直觉能帮助你在设计算法时第一时间排除掉那些显然低效的方案。3.2 第九层递归——自己调用自己的艺术递归是函数直接或间接调用自身的过程。它提供了一种优雅的问题解决思路将一个大问题分解成一个或几个规模更小的、同类型的子问题直到子问题简单到可以直接求解。递归包含两个关键部分递归边界定义最简单的情况直接返回结果防止无限递归。递归式定义如何将原问题分解为子问题。以计算阶乘f(n) n!为例递归边界f(1) 1递归式f(n) n * f(n-1)递归代码简洁但需要注意栈溢出的风险递归深度太大以及可能存在的大量重复计算如经典的斐波那契数列递归实现。后者通常通过“记忆化搜索”缓存已计算的结果或转为“动态规划”来解决。理解递归的执行过程画出递归树是掌握递归思维的关键。3.3 第十层排序算法上——比较排序的世界排序是将一组数据按特定顺序重新排列的过程。这里我们先讨论基于比较的排序。冒泡排序重复遍历比较相邻元素顺序错误就交换将最大小元素“冒泡”到末端。时间复杂度O(n²)稳定。选择排序每次遍历从未排序部分选出最小大元素放到已排序部分的末尾。时间复杂度O(n²)不稳定。插入排序将未排序部分的元素逐个插入到已排序部分的正确位置。对于近乎有序的数据效率很高时间复杂度O(n²)稳定。希尔排序插入排序的改进版通过设定一个递减的增量序列对间隔增量的子序列进行插入排序最终增量为1时整体基本有序再进行一次插入排序。时间复杂度优于O(n²)。理解这些基础排序算法不仅是为了掌握它们本身更是为了理解排序算法的基本操作比较、交换、移动和评价维度时间复杂度、空间复杂度、稳定性、原地性。3.4 第十一层排序算法下——分治思想的威力这一层引入了分治思想效率有质的飞跃。归并排序典型的分治算法。将数组不断二分直到子数组长度为1有序然后合并两个有序子数组。整个过程需要额外的O(n)空间。时间复杂度稳定为O(n log n)是稳定的排序算法。它的“合并”操作是很多外部排序和复杂算法的基础。快速排序另一种分治算法但思路不同。选择一个“基准”元素将数组分为小于基准和大于基准的两部分然后递归地对两部分排序。关键在于分区操作。快速排序的平均时间复杂度是O(n log n)最坏情况如数组已有序会退化为O(n²)但可以通过随机选择基准来避免。它是原地排序但不稳定。归并排序和快速排序是面试和实际应用中最常被问到的两种高效排序算法。理解它们的分治流程、递归实现、以及时间复杂度的推导至关重要。3.5 第十二层二分查找——高效的搜索策略二分查找针对的是已排序的数据集合。它每次将待查找区间缩小一半时间复杂度为O(log n)效率极高。二分查找的代码框架看似简单但边界条件while循环用还是right初始值是n-1还是n更新区间时是mid还是mid±1是极易出错的地方。我个人的经验是确定一种自己熟悉的写法并始终坚持比如使用左闭右开区间[left, right)循环条件为while left right更新时left mid 1,right mid。理解其变种如寻找第一个等于目标值的位置、最后一个等于目标值的位置、第一个大于等于目标值的位置等是应对面试题的关键。4. 第十三到十六层树形结构入门——从链表到分叉树是典型的非线性数据结构能很好地表达层次关系。这四层是树的基础。4.1 第十三层树与二叉树——基本概念与遍历树是n个节点的有限集其中一个为根节点其余节点可分为m个互不相交的子树。二叉树是每个节点最多有两个子树的树结构子树有左右之分。二叉树的遍历是基础中的基础分为深度优先遍历沿着树的深度遍历节点。前序遍历根 - 左 - 右中序遍历左 - 根 - 右后序遍历左 - 右 - 根广度优先遍历按层次遍历节点需要借助队列。递归实现遍历代码非常简洁。非递归实现使用栈或队列则需要更深刻的理解也是常考内容。遍历是解决几乎所有二叉树问题如求深度、找路径、序列化等的出发点。4.2 第十四层二叉搜索树——有序的二叉树二叉搜索树是一种特殊的二叉树对于任意节点其左子树所有节点的值小于它右子树所有节点的值大于它。这个性质使得BST的中序遍历结果是一个升序序列。BST支持高效的查找、插入和删除操作理想情况下的时间复杂度是O(log n)。但是如果插入的顺序不当例如按升序插入BST会退化成一条链表时间复杂度恶化到O(n)。这正是BST的缺陷也为下一层的平衡二叉树埋下了伏笔。4.3 第十五层堆与优先队列——快速获取极值堆是一种特殊的完全二叉树它满足堆属性每个节点的值都大于等于大顶堆或小于等于小顶堆其子节点的值。堆通常用数组来存储利用完全二叉树的性质可以通过下标计算父子节点位置。堆的核心操作是插入上浮和删除堆顶元素下沉时间复杂度都是O(log n)。构建堆的时间复杂度是O(n)。堆是实现优先队列的理想数据结构。优先队列不再遵循先进先出而是按优先级出队。这在很多场景下非常有用如操作系统的进程调度、Dijkstra最短路径算法、哈夫曼编码等。在算法题中求Top K问题用小顶堆或合并K个有序链表用堆维护每个链表的头节点是经典应用。4.4 第十六层并查集——处理不相交集合并查集是一种用于处理一些不交集合并及查询问题的数据结构。它支持两种操作查找确定某个元素属于哪个子集。合并将两个子集合并成一个集合。并查集通过树形结构实现每个集合用一棵树代表树根是代表元素。优化手段包括“路径压缩”在查找时将查找路径上的所有节点直接指向根和“按秩合并”将较矮的树合并到较高的树上。这两种优化能将近乎所有操作的时间复杂度降到接近O(1)。并查集在解决连通性问题、朋友圈问题、最小生成树Kruskal算法等方面有奇效。理解并查集能为你打开解决另一大类问题的大门。5. 第十七到二十一层思想深化与经典问题最后五层我们接触更抽象的算法思想和几个经典问题模型。5.1 第十七层深度优先搜索与广度优先搜索——图的遍历基石虽然我们在树中已经接触了DFS和BFS但它们在图论中更为通用和重要。图由顶点和边组成可以表示网络、关系等复杂结构。深度优先搜索沿着一条路径走到底直到无法继续然后回溯到上一个分叉点。通常用递归或栈实现。DFS适合寻找所有路径、检测环、拓扑排序等。广度优先搜索从起点开始一层一层向外扩展。通常用队列实现。BFS适合寻找最短路径在无权图中、按层次处理问题。对于图需要记录节点是否被访问过以防止重复访问和陷入循环。DFS和BFS是解决绝大多数图论问题的起点必须熟练掌握它们的递归与非递归写法并能根据问题特点选择合适的方法。5.2 第十八层贪心算法——局部最优的抉择贪心算法在每一步选择中都采取当前状态下最好或最优的选择从而希望导致结果是全局最好或最优的。它不像动态规划那样考虑所有子问题而是做出一个选择后不可回退。贪心算法高效但难点在于证明其正确性。一个问题是否能用贪心解决通常需要满足“贪心选择性质”和“最优子结构”。经典的贪心问题包括区间调度问题、霍夫曼编码、找零钱问题针对特定币值、Kruskal最小生成树算法等。在面试中遇到一个问题如果其具有“通过局部最优能导向全局最优”的明显特征可以尝试贪心思路。但务必小心很多问题看似贪心实则需要动态规划。5.3 第十九层回溯算法——试错与回退回溯算法是DFS的一种应用用于系统地搜索一个问题的所有可能解。它通过尝试分步去解决一个问题当发现当前分步答案不能得到有效的正确解时它将取消上一步甚至上几步的计算再通过其他的可能分步再次尝试寻找答案。回溯法通常用递归实现其核心框架是做出选择。递归进入下一层决策。撤销选择回溯。经典的回溯问题包括N皇后问题、全排列、组合总和、子集、数独等。回溯是解决“所有可能”这类枚举问题的利器理解其“选择列表”、“路径”、“结束条件”以及“剪枝”优化是掌握它的关键。5.4 第二十层动态规划入门——记忆化与状态转移动态规划是解决重叠子问题和最优子结构性质问题的高效方法。它的核心思想是避免重复计算通过把原问题分解为相对简单的子问题的方式保存子问题的解每个子问题只解一次。DP解题通常有以下几个步骤定义状态用一个或多个变量表示问题的某个子问题。例如dp[i]表示以第i个元素结尾的某种最优值。确定状态转移方程找出状态之间的关系即如何从已知状态推导出未知状态。这是DP最核心也最难的部分。初始化给出最简单子问题的解边界条件。确定计算顺序保证在计算一个状态时它所依赖的状态已经被计算出来。返回结果。可以从最简单的斐波那契数列记忆化递归或迭代、爬楼梯问题开始逐步过渡到背包问题、最长公共子序列、最长递增子序列等经典模型。理解“自顶向下”的记忆化搜索和“自底向上”的递推填表两种实现方式有助于融会贯通。5.5 第二十一层双指针与滑动窗口——线性结构的技巧这是两种在数组和字符串上非常高效的技巧通常能将O(n²)的暴力解法优化到O(n)。双指针使用两个指针协同遍历数组。根据指针移动方向可分为对撞指针一个在头一个在尾向中间移动。用于有序数组的Two Sum问题、反转数组等。快慢指针两个指针从同一起点出发速度不同。用于判断链表是否有环、寻找链表中点等。同向指针两个指针从头开始一前一后。用于移除数组中的特定元素等。滑动窗口可以看作是双指针的一种特殊形式维护一个窗口由左右指针界定通过移动右指针扩大窗口移动左指针缩小窗口来寻找满足条件的子区间。常用于求解子串、子数组问题如“长度最小的子数组”、“无重复字符的最长子串”。掌握这两种技巧能让你在面对许多线性结构问题时写出既高效又优雅的代码。它们本质上是利用问题本身的特性避免了不必要的重复计算。走完这“练气二十一层”你对算法和数据结构的认知应该有了一个扎实的框架。这并非终点而是一个坚实的起点。后续的“筑基篇”、“金丹篇”可能涉及更复杂的图论算法、字符串高级算法、复杂的动态规划、并查集进阶、线段树、树状数组等高级数据结构。但只要你牢牢掌握了这二十一层的基础在遇到更复杂的问题时你就有能力将它们拆解、归类并调用这些基础模块去理解和构建解决方案。算法修炼路漫漫其修远兮打好地基方能筑起万丈高楼。