1. 为什么“数据结构与算法”是程序员绕不开的坎如果你问一个工作三五年的程序员面试中最怕什么十有八九会提到“数据结构与算法”。这玩意儿就像武侠小说里的内功心法招式编程语言、框架可以速成但内功不行。很多人觉得日常业务开发就是增删改查用不到什么高深的算法学它干嘛这种想法在我刚入行时也有过直到后来踩了几个大坑才彻底改变了看法。有一次我负责一个用户行为日志分析的后台模块。需求很简单实时接收前端上报的用户点击事件按用户ID聚合计算最近一小时内每个用户的点击次数然后推给下游的风控系统。最初我图省事用了一个最直观的方法来了一个事件就把它塞进一个大的List里。每次查询时遍历整个列表过滤出目标用户ID和最近一小时的数据然后计数。在开发环境数据量小跑得飞快。一上线流量进来服务器CPU直接飙到100%接口响应时间从几十毫秒变成了好几秒下游系统疯狂告警。问题的根源就在于我选错了“数据结构”。我用了一个线性表List来存储动态增长、且需要频繁按条件筛选的数据。遍历的复杂度是O(n)数据量n一大性能呈线性劣化。后来我把结构改成了“哈希表有序集合”的组合用一个哈希表HashMap以用户ID为键存储一个按时间戳排序的列表如TreeSet。插入新事件时通过哈希表O(1)定位到用户的集合再插入有序集合O(log n)。清理过期数据和统计次数时也只需要在有序集合中进行范围操作效率极高。这个改动让我深刻理解数据结构决定了你程序处理数据的“先天效率”算法则是利用这些结构高效解决问题的“方法论”。不懂这些就像用勺子砍树不是不能砍是事倍功半迟早累死。所以这份学习笔记不是应付面试的八股文而是我作为一个过来人将那些抽象的概念、枯燥的代码与真实开发中遇到的性能瓶颈、设计抉择联系起来的一次系统梳理。目标很明确帮你建立一种“计算思维”在面对问题时能本能地评估数据规模、操作频率从而选择最合适的“工具”数据结构和“使用技巧”算法。2. 从数组到链表理解数据组织的“物理”与“逻辑”我们学习数据结构往往从最基础的“数组”和“链表”开始。这俩是两种最根本、也最对比鲜明的数据组织方式理解了它们就理解了后续几乎所有复杂结构的基石。2.1 数组连续空间的效率与束缚数组Array可以想象成一排紧密相连的储物柜。你申请一块连续的内存空间每个“柜子”元素大小固定并且通过一个从0开始的“编号”索引来直接访问。它的核心优势是“随机访问”。因为内存是连续的我知道第一个柜子的地址要拿第5个柜子里的东西直接“基地址 5 * 每个柜子大小”就能算出来时间复杂度是O(1)。这就像你知道朋友住在一条街上的5号直接走过去就行不用问路。但它的缺点也同样源于“连续”大小固定创建时就要确定长度。就像那排储物柜造好了就不能轻易加长。在C或Java的原始数组中扩容意味着要申请一块更大的新连续空间然后把所有东西搬过去成本很高O(n)。虽然像Java的ArrayList、Python的list提供了动态扩容的便利但其底层依然是数组扩容操作本身是有开销的。插入/删除低效如果你想在数组中间插入或删除一个元素为了保证连续性需要把这个位置之后的所有元素都向后移动或向前移动。平均时间复杂度是O(n)。这就像在排队中间有个人要加进来或离开后面所有人都得动一动。实战心得数组适合“读多写少”且访问模式以随机访问为主的场景。比如存储一个已经加载到内存的、不再变化的配置表通过ID快速查找配置项。又比如实现一个哈希表时底层存储桶bucket经常就用数组来实现因为需要根据哈希值快速定位到某个桶。2.2 链表离散节点的灵活与代价链表Linked List则像是一串分散在各处的珍珠每颗珍珠节点除了存储数据还记录着下一颗珍珠在哪里指针/引用。它的核心优势是“动态”和“插入删除高效”。因为节点在内存中不需要连续所以可以随时随地创建新节点。在已知某个节点的情况下在其后插入或删除一个节点只需要修改几个指针的指向时间复杂度是O(1)。这就像火车车厢在中间加挂或卸下一节车厢只需要改变前后车厢的连接钩不需要移动整列火车。但它的代价是“顺序访问”无法随机访问要找到第i个节点你必须从第一个节点头节点开始一个接一个地“遍历”i次。时间复杂度是O(n)。你不知道第5颗珍珠具体在哪必须从第一颗开始一颗颗数过去。空间开销稍大每个节点除了存数据还要额外存指针空间利用率比数组低。链表的主要变体单向链表每个节点只指向下一个。简单但想找前一个节点很麻烦。双向链表每个节点有指向前一个和后一个的指针。插入删除更灵活可以向前遍历但每个节点多一个指针开销。Java的LinkedList、C的std::list就是双向链表。循环链表尾节点指向头节点形成一个环。适合需要循环处理的场景如操作系统中的进程调度队列。实战踩坑链表虽然插入删除快但这个“快”的前提是“你已经定位到了要操作节点的前驱节点”。如果你只知道“要在第i个位置插入”但链表没有索引你还是得从头遍历i-1次找到那个位置整体复杂度依然是O(n)。所以链表真正的优势场景是频繁在已知节点附近进行插入删除且不需要按索引快速查找。比如实现一个LRU最近最少使用缓存淘汰算法时我们经常用“哈希表双向链表”的组合。哈希表保证O(1)找到缓存项双向链表保证在找到节点后能O(1)地将其移动到头部表示最近使用。注意在现代编程中除非有非常极致的性能需求或特殊场景如嵌入式开发内存受限否则优先使用语言标准库提供的高级容器如ArrayList,Vector,LinkedList它们已经做了高度优化。理解底层原理是为了让你在更高层次选型时比如选ArrayList还是LinkedList做出正确决策。3. 栈与队列理解操作受限的线性表栈和队列是两种“操作受限”的线性表。它们规定了数据进出的特定顺序这种限制恰恰解决了特定领域的问题。3.1 栈后进先出的“叠盘子”栈Stack的特点是后进先出。就像一叠盘子你总是把新盘子放在最上面入栈push也总是从最上面拿走盘子出栈pop。你没法直接抽走中间或底部的盘子。核心操作push(element): 元素入栈。pop(): 弹出栈顶元素。peek() / top(): 获取栈顶元素但不弹出。isEmpty(): 判断栈是否为空。应用场景无处不在函数调用栈这是栈最经典的应用。每次调用一个函数系统会将当前函数的返回地址、参数、局部变量等信息“压栈”。函数执行完毕再“弹栈”恢复到调用者现场。递归函数深度的限制本质上就是调用栈的深度限制。表达式求值编译器处理算术表达式如3 5 * (2 - 1)时需要两个栈一个操作数栈一个运算符栈。利用栈来处理运算符的优先级和括号。括号匹配检查代码中的括号(),[],{}是否成对且嵌套正确。遇到左括号就入栈遇到右括号就检查栈顶是否是对应的左括号。浏览器的前进后退用两个栈Stack A, Stack B可以实现。点击新页面压入A栈点击后退从A栈弹出并压入B栈点击前进从B栈弹出并压入A栈。撤销操作编辑器的撤销功能通常将操作命令压栈撤销时弹栈执行逆操作。实现方式栈的底层既可以用数组顺序栈实现也可以用链表链式栈实现。数组实现更简单但可能有扩容问题链表实现更灵活无容量限制受限于内存但每个节点有额外开销。3.2 队列先进先出的“排队”队列Queue的特点是先进先出。就像排队买票后来的人排在队尾先来的人从队头先被服务。核心操作enqueue(element) / offer(element): 元素入队到队尾。dequeue() / poll(): 元素出队从队头移除并返回。peek() / front(): 获取队头元素但不移除。isEmpty(): 判断队列是否为空。应用场景消息队列这是分布式系统的核心组件。生产者将消息放入队列消费者从队列取出处理实现了系统间的解耦和异步处理。RabbitMQ, Kafka等中间件的核心思想即源于此。广度优先搜索在图或树的遍历中BFS需要使用队列来存储待访问的节点。线程池任务队列提交给线程池的任务会被放入一个阻塞队列中空闲的线程从队列中取出任务执行。CPU进程调度操作系统常用的先来先服务调度算法就是基于队列。队列的变体双端队列这就是你提供的热词中提到的Deque。它允许在队头和队尾两端进行插入和删除。它融合了栈和队列的特性功能更强大。Java中的ArrayDeque和LinkedList都实现了Deque接口。循环队列用数组实现队列时为了避免“假溢出”队头有空位但队尾已到数组末尾将数组首尾相连。这是实现有界队列的高效方式。优先队列出队顺序不是先进先出而是按照元素的优先级。底层通常用“堆”这种数据结构实现。Java的PriorityQueue就是基于堆的优先队列。实战心得选择栈还是队列根本在于你对数据消费顺序的需求。是“后来居上”还是“先到先得”在涉及“回退”、“嵌套”、“递归”语义时想想栈在涉及“缓冲”、“排队”、“公平调度”时想想队列。而Deque是一个更通用的工具当你需要在两端操作时它是比单纯栈或队列更好的选择例如实现一个滑动窗口最大值算法时用一个单调递减的双端队列会非常高效。4. 哈希表理解键值映射的魔法与碰撞如果说数组通过“下标”访问元素是O(1)那么哈希表Hash Table的野心就是让通过“任意键”访问也能接近O(1)。它是现代编程中应用最广泛的数据结构之一Python的dict、Java的HashMap、JavaScript的Object和Map都是它的实现。4.1 哈希表是如何工作的它的核心思想是“映射”。通过一个哈希函数将任意大小的键Key转换成一个固定范围的整数哈希值然后用这个整数作为数组通常称为“桶数组”或“散列表”的索引将值Value存储在该位置。理想过程存入键值对(key, value)hash hashFunction(key)-index hash % arraySize- 将value存入array[index]。通过键key查找值hash hashFunction(key)-index hash % arraySize- 直接返回array[index]。如果每个键都映射到唯一的数组索引那查找就是完美的O(1)。但现实很骨感哈希冲突不可避免两个不同的键经过哈希函数计算后得到了相同的数组索引。4.2 解决哈希冲突的两种主流方法链地址法这是最常用的方法Java的HashMap就采用此方法。数组的每个位置不再直接存储一个值而是存储一个链表或红黑树的头节点。当发生冲突时就将新的键值对作为节点添加到这个索引对应的链表中。查找时先定位到索引再遍历这个小链表找到匹配的键。优点实现简单有效地处理冲突链表节点可以动态申请内存利用率高。缺点如果某个链表变得很长比如所有键都冲突到同一个桶查找效率会退化为O(n)。在Java 8的HashMap中当链表长度超过阈值默认为8时会将链表转换为红黑树将查找效率提升至O(log n)。开放地址法当发生冲突时不建立链表而是按照某种探测序列如线性探测、二次探测、双重哈希在数组中寻找下一个空闲位置。线性探测如果位置i冲突就尝试i1, i2, ... 直到找到空位。优点所有数据都存储在数组中利用缓存局部性更好没有额外的指针开销。缺点容易产生“聚集”现象删除操作复杂需要特殊标记表满时需要扩容且扩容成本高。4.3 影响哈希表性能的关键因素哈希函数一个好的哈希函数应该能将键均匀地分布到所有桶中减少冲突。它还需要计算速度快。对于整数常用取模对于字符串常用像“乘常数循环相加”等方法。负载因子负载因子 元素个数 / 桶数组大小。它衡量哈希表的拥挤程度。当负载因子超过某个阈值如0.75冲突概率会显著增加性能下降。此时需要扩容创建一个更大的新数组通常是原大小的2倍然后重新计算所有键的哈希值和新索引将元素重新插入。这是一个O(n)的昂贵操作但摊还下来平均插入成本仍是O(1)。扩容策略扩容时机和扩容大小是关键。太早扩容浪费空间太晚扩容影响性能。通常设置一个合理的负载因子阈值。实战踩坑与心得键对象必须正确重写hashCode()和equals()方法在Java中。这是哈希表正常工作的基石。hashCode决定了元素进入哪个桶equals用于在桶内链表/树中精确匹配键。如果两个对象equals为 true它们的hashCode必须相等。反之hashCode相等的两个对象equals不一定为 true这就是哈希冲突。哈希表是无序的。如果你需要保持插入顺序应该使用LinkedHashMap内部维护一个链表如果需要自然顺序或自定义顺序使用TreeMap基于红黑树。在多线程环境下HashMap不是线程安全的。并发修改可能导致死循环或数据丢失。需要使用ConcurrentHashMap或Collections.synchronizedMap进行包装。理解时间复杂度在均匀哈希的理想情况下插入、删除、查找的平均时间复杂度是O(1)。但在最坏情况下所有键都冲突链地址法会退化为O(n)链表或O(log n)树。因此选择一个分布均匀的哈希函数至关重要。哈希表是“空间换时间”的典型代表。它用额外的内存数组链表/树结构和计算哈希函数换来了近乎常数时间的查找效率是处理大量数据快速查找、去重、统计的利器。5. 树形结构从二叉树到平衡的奥秘当数据之间存在明确的层级或从属关系时线性结构就显得力不从心了。树Tree是一种非常重要的非线性数据结构它能高效地表示这种关系并在查找、排序等领域大放异彩。5.1 二叉树与二叉搜索树二叉树是每个节点最多有两个子节点的树结构称为左子节点和右子节点。二叉搜索树是一种特殊的二叉树它满足左子树上所有节点的值均小于它的根节点的值。右子树上所有节点的值均大于它的根节点的值。左右子树也分别为二叉搜索树。这个性质带来了一个巨大优势中序遍历BST可以得到一个有序序列。同时查找、插入、删除一个值理想情况下都可以在O(log n)时间内完成因为每次比较都能排除一半的子树。操作逻辑查找从根开始比当前节点小就往左走大就往右走等于就找到。插入先执行查找直到到达一个空的子节点位置将新节点插入此处。删除情况稍复杂分三种删除叶子节点直接删除。删除只有一个子节点的节点用其子节点替代自己。删除有两个子节点的节点找到其右子树中的最小节点或左子树中的最大节点用这个节点的值替换待删除节点的值然后递归删除那个最小或最大节点。BST的缺陷BST的性能严重依赖于树的形状。如果插入的数据本身就是有序的如1,2,3,4,5BST会退化成一条链表所有操作的时间复杂度都退化为O(n)。这就引出了“平衡”的需求。5.2 平衡二叉搜索树AVL与红黑树为了维持BST的查找效率我们需要在插入和删除时通过旋转操作来保持树的“平衡”即左右子树的高度差不能太大。常见的平衡二叉搜索树有AVL树和红黑树。AVL树它是最早被发明的自平衡BST。它要求每个节点的左右子树高度差绝对值不超过1。通过四种基本的旋转操作左旋、右旋、左右旋、右左旋来维持平衡。因为平衡度要求严格所以AVL树的查找效率是O(log n)的稳定保证是几种平衡树中最高的。但正因如此插入和删除可能需要频繁的旋转来再平衡维护开销较大。红黑树它通过一套复杂的着色规则和旋转规则提供了一种“近似平衡”的解决方案。红黑树满足以下5条性质每个节点非红即黑。根节点是黑色。每个叶子节点NIL空节点是黑色。红色节点的两个子节点必须是黑色即不能有两个连续的红色节点。从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。性质4和5保证了从根到叶子的最长可能路径不会超过最短可能路径的两倍。这样树虽然不是严格平衡的但依然是近似平衡的查找、插入、删除的时间复杂度都能保持在O(log n)。与AVL树相比红黑树在插入和删除时需要的旋转操作更少因此在需要频繁修改的场景下如关联容器性能更优。应用对比AVL树更适合读多写少的场景例如数据库索引的某些实现对查找性能有极致要求。红黑树更适合读写都频繁的场景。Java的TreeMap,TreeSetC的std::map,std::set以及Linux内核的进程调度等底层都使用了红黑树。实战心得作为应用开发者我们很少需要手写红黑树太复杂了但必须理解它的特性。当你需要一个能自动维护键值有序且支持高效查找、插入、删除的容器时就应该想到基于红黑树的TreeMap或std::map。而HashMap虽然平均查找更快但它不保证顺序。5.3 堆一种特殊的树形结构堆Heap虽然也叫“树”但它不是为了查找而是为了快速获取最大值或最小值而设计的。堆是一种完全二叉树并且满足堆属性最大堆父节点的值总是大于或等于其子节点的值。堆顶是最大值。最小堆父节点的值总是小于或等于其子节点的值。堆顶是最小值。堆通常用数组来实现。对于数组中下标为i的节点其父节点下标为(i-1)/2。其左子节点下标为2*i 1。其右子节点下标为2*i 2。核心操作insert(val)将新元素添加到数组末尾然后执行“上浮”操作与其父节点比较如果违反堆属性则交换直到满足为止。时间复杂度O(log n)。extractMax() / extractMin()取出堆顶元素数组第一个元素。将数组末尾元素移到堆顶然后执行“下沉”操作与其较大的子节点比较如果违反堆属性则交换直到满足为止。时间复杂度O(log n)。应用场景优先队列如前所述堆是实现优先队列最理想的数据结构。Java的PriorityQueue就是基于最小堆。堆排序一种原地、时间复杂度为O(n log n)的排序算法。求Top K问题在海量数据中找出最大或最小的K个元素。维护一个大小为K的最小堆求最大K个或最大堆求最小K个遍历数据并与堆顶比较即可。定时任务调度操作系统或框架中将即将执行的任务按执行时间构建最小堆堆顶总是最近要执行的任务。堆的精妙之处在于它用数组这种简单结构通过父子节点下标的关系高效地维护了部分有序性使得获取极值的操作非常高效。6. 图论基础表示与遍历的现实映射图Graph是比树更一般的非线性结构用于表示多对多的关系。社交网络用户是顶点关注关系是边、交通网络车站是顶点线路是边、知识图谱实体是顶点关系是边都是图的典型应用。6.1 图的两种表示方法如何在计算机中存储一个图主要有两种方式邻接矩阵用一个二维数组matrix表示。matrix[i][j]的值表示顶点i到顶点j的边的权值无权图可用1/0表示有无边。优点直观容易理解检查任意两个顶点间是否有边非常快O(1)适合表示稠密图边很多。缺点占用空间大为O(V²)V为顶点数。对于稀疏图边很少空间浪费严重添加或删除顶点成本高。邻接表为每个顶点维护一个列表数组、链表等存储与该顶点直接相连的所有邻接顶点及边的权值。优点空间利用率高为O(V E)E为边数特别适合稀疏图遍历某个顶点的所有邻接点很快。缺点检查两个顶点间是否有边需要遍历其中一个顶点的邻接表最坏O(V)表示不如矩阵直观。选型建议绝大多数情况下尤其是处理现实中的大型网络社交、网页链接图都是稀疏的邻接表是更通用和高效的选择。邻接矩阵通常只在图非常稠密或需要频繁判断任意两点间是否有边时使用。6.2 图的深度与广度优先遍历遍历图意味着访问图中的每一个顶点且每个顶点只访问一次。这是图算法的基础。深度优先搜索它沿着一条路径一直走到底直到无法前进然后回溯到上一个分叉点走另一条路。这个过程天然适合用递归或栈来实现。思想“不撞南墙不回头”。类似于走迷宫遇到岔路先选一条走到底。应用拓扑排序、寻找连通分量、解决迷宫问题、判断图中是否有环等。广度优先搜索它从起点开始先访问所有距离为1的邻接点再访问所有距离为2的邻接点以此类推。这个过程天然适合用队列来实现。思想“层层推进”。类似于水波扩散。应用寻找无权图中的最短路径因为BFS第一次访问到某个节点的路径就是起点到该节点的最短路径、社交网络中的“六度空间”理论、网络爬虫按层级抓取网页等。代码框架对比伪代码# DFS - 递归版 def dfs(node, visited): if node in visited: return visited.add(node) # 处理当前节点 node for neighbor in graph[node]: dfs(neighbor, visited) # BFS - 迭代版 from collections import deque def bfs(start): visited set([start]) queue deque([start]) while queue: node queue.popleft() # 处理当前节点 node for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)实战心得DFS和BFS不仅是遍历方法更是两种不同的解题思路。当问题需要探索所有可能路径、或与“递归”、“回溯”相关时优先考虑DFS。当问题与“最短距离”、“最小步骤”、“层级关系”相关时优先考虑BFS。在很多复杂问题中如二叉树的层序遍历就是BFS二叉树的最大深度可以用DFS识别出问题本质对应哪种遍历模式是解题的关键第一步。7. 经典算法思想分治、动态规划与贪心掌握了数据结构就像拥有了各种精良的工具。而算法思想则是教你如何运用这些工具解决复杂问题的“心法”。这里探讨三种最核心的思想。7.1 分治算法化整为零各个击破分治法的思想很直观把一个复杂的大问题分解成若干个规模较小、相互独立且与原问题形式相同的子问题递归地解决这些子问题然后再合并其结果得到原问题的解。经典三步走分解将原问题分解为若干子问题。解决递归地求解各个子问题。若子问题足够小则直接求解。合并将子问题的解合并为原问题的解。典型案例归并排序将数组不断二分直到子数组长度为1已有序然后合并两个有序子数组。时间复杂度O(n log n)是稳定排序。快速排序选择一个基准元素将数组分成小于基准和大于基准的两部分递归排序这两部分。平均时间复杂度O(n log n)但不稳定。二分查找在有序数组中查找目标值每次与中间元素比较将搜索范围缩小一半。时间复杂度O(log n)。大规模计算如MapReduce编程模型就是分治思想在分布式系统中的体现。心得分治法的核心在于“如何分”和“如何合”。子问题必须独立这是能递归求解的前提。合并操作的成本不能太高否则会抵消分解带来的好处。归并排序的合并操作是O(n)而快速排序的“合并”实际上在分区时已经隐含完成了。7.2 动态规划记住过往节省未来动态规划用于解决具有“重叠子问题”和“最优子结构”的问题。它的核心是避免重复计算通过空间通常是数组或哈希表来存储中间子问题的解。关键特征最优子结构一个问题的最优解包含其子问题的最优解。重叠子问题在递归求解过程中相同的子问题会被反复计算多次。解题思路定义状态明确dp[i]或dp[i][j]代表什么含义。这是最难也最关键的一步。找到状态转移方程确定dp[i]如何由之前的dp值推导出来。这是DP的核心公式。确定初始条件base case最小的、不可再分的子问题的解是什么。确定计算顺序按什么顺序计算dp数组才能保证在计算当前状态时它所依赖的状态已经被计算出来。返回最终结果。典型案例斐波那契数列F(n) F(n-1) F(n-2)。朴素递归存在大量重复计算用DP数组存储已计算的结果时间复杂度从O(2^n)降为O(n)。背包问题0-1背包、完全背包等是DP的经典模型。dp[i][w]表示考虑前i件物品在容量为w的背包下能获得的最大价值。最长公共子序列dp[i][j]表示字符串A前i个字符和字符串B前j个字符的LCS长度。最短路径问题如Floyd算法多源最短路径和Dijkstra算法单源最短路径属于贪心思想但也可用DP理解。心得学习DP不要死记硬背题目要理解其“自底向上”的填表过程。先从简单的1维DP如爬楼梯、打家劫舍开始熟练后再挑战2维DP如编辑距离、不同路径。很多时候写出状态转移方程问题就解决了一大半。另外DP的“滚动数组”优化技巧可以节省空间将二维DP数组压缩为一维。7.3 贪心算法眼前最优未必全局最优贪心算法在每一步都做出当前看起来最优的选择并希望这样的局部最优选择能导致全局最优解。它不像DP那样考虑所有子问题而是活在当下。使用前提比DP更苛刻贪心选择性质可以通过局部最优选择来构造全局最优解。最优子结构与DP相同。贪心算法通常更高效代码更简洁但它不能保证得到所有问题的最优解。只有在问题满足上述性质时贪心才是正确的。典型案例霍夫曼编码用于数据压缩每次选择频率最低的两个节点合并构造最优前缀码。Dijkstra算法用于非负权图的单源最短路径。每次从未确定的节点中选择距离起点最近的那个认为这个距离就是最短距离。Kruskal和Prim算法用于求最小生成树。Kruskal每次选权值最小的边且不构成环Prim每次选连接已选顶点集和未选顶点集的最小权边。区间调度问题给定一系列会议开始、结束时间问最多能参加多少个不冲突的会议。贪心策略每次选择结束时间最早的会议。心得面对一个问题先判断它是否具有明显的“贪心”性质。一个简单的检验方法是举一个反例。如果能轻易构造一个例子证明“眼前最优”会导致后面更差的结果那么贪心算法就不适用。例如经典的“找零钱”问题用最少的硬币凑出某个金额如果硬币面额是[1, 3, 4]要凑6元贪心先选4再选1再选1需要3个而最优解是两个3元硬币。此时就需要用DP。贪心算法更像是一种“启发式”策略在可以证明其正确性的场景下它是非常犀利的工具。8. 字符串匹配与排序算法拾遗最后我们快速过一下两个在实战中高频出现的算法领域字符串匹配和排序。它们虽然基础但细节中藏着魔鬼。8.1 KMP算法理解字符串匹配的优化字符串匹配就是在一个主串文本S中查找一个模式串P出现的位置。暴力匹配Brute-Force的时间复杂度是O(m*n)其中m和n分别是模式串和主串的长度。当主串很长时效率低下。KMP算法的核心思想是当出现字符不匹配时利用已经匹配的部分信息避免主串指针的回退。它通过一个“部分匹配表”也称为next数组来实现。next数组的含义next[i]表示模式串P的前i个字符即P[0...i-1]中最长的相等前后缀的长度。前缀指除了最后一个字符以外一个字符串的全部头部组合。后缀指除了第一个字符以外一个字符串的全部尾部组合。例如字符串ababa其前缀有a,ab,aba,abab后缀有a,ba,aba,baba。最长的相等前后缀是aba长度为3。算法流程预处理模式串P计算next数组。用两个指针i主串S和j模式串P进行匹配。如果S[i] P[j]则i,j。如果S[i] ! P[j]如果j 0说明模式串第一个字符就不匹配则i。否则令j next[j]。注意这里i不动。这意味着模式串P向右滑动j - next[j]位继续与S[i]比较。重复3-4直到j走到模式串末尾匹配成功或i走到主串末尾匹配失败。为什么有效当在P[j]处失配时next[j]告诉我们P[0...j-1]这个已匹配的子串中有多长的前缀和后缀是相同的。既然后缀已经和主串匹配上了那么相同的前缀也必然和主串匹配。所以我们可以直接把模式串的前缀滑动到刚才后缀的位置j回退到next[j]继续比较而主串指针i不需要回溯。实战心得KMP算法理解起来有门槛关键是理解next数组的构建和用法。在面试或竞赛中直接手写KMP有难度但必须理解其思想。在实际开发中编程语言自带的字符串查找函数如Java的indexOf Python的find已经做了高度优化通常比手写的KMP更快因为它们可能使用了更先进的算法如Boyer-Moore或Sunday算法。但理解KMP是深入字符串算法领域的基础。8.2 排序算法全景与选型指南排序是算法中的“ Hello World ”但不同的排序算法适用于不同的场景。这里不展开每个算法的细节而是提供一个选型指南。算法平均时间复杂度最坏时间复杂度空间复杂度稳定性特点与适用场景冒泡排序O(n²)O(n²)O(1)稳定简单效率低仅用于教学或极小数据量。选择排序O(n²)O(n²)O(1)不稳定交换次数少但比较次数多。同样效率低。插入排序O(n²)O(n²)O(1)稳定对小规模或基本有序的数据非常高效。常作为快速排序等算法的子过程。希尔排序O(n log n) ~ O(n²)O(n²)O(1)不稳定插入排序的改进通过分组插入来提升效率。中等规模数据可选。归并排序O(n log n)O(n log n)O(n)稳定稳定时间复杂度有保证。需要额外空间。适用于链表排序、外部排序大数据量无法全部装入内存。快速排序O(n log n)O(n²)O(log n) ~ O(n)不稳定平均性能最好原地排序。但最坏情况如已有序数组性能差。需要精心选择基准。绝大多数语言标准库的排序实现基于快速排序的优化变体如内省排序IntroSort。堆排序O(n log n)O(n log n)O(1)不稳定时间复杂度稳定原地排序。但缓存局部性较差实际性能常不如快速排序。适合求Top K问题。计数排序O(n k)O(n k)O(n k)稳定非比较排序k是数据范围。要求输入数据是有确定范围的整数。速度快但适用范围窄。桶排序O(n k)O(n²)O(n k)稳定将数据分到有限数量的桶里每个桶再单独排序。适用于数据均匀分布在一定区间的情况。基数排序O(d*(nk))O(d*(nk))O(n k)稳定非比较排序d是关键字的位数k是基数如十进制为10。适用于整数或字符串排序。通用选型建议默认选择对于通用目的的排序直接使用语言标准库的排序函数如C的std::sort Java的Arrays.sort() Python的list.sort()。它们经过了极致优化综合了快速排序、堆排序、插入排序的优点如内省排序在绝大多数情况下都是最佳选择。需要稳定性时如果排序后相等元素的原始相对顺序必须保持不变选择归并排序、计数排序、桶排序等稳定算法。Java中对象数组的Arrays.sort()使用TimSort一种归并排序的优化变体是稳定的。数据量小或基本有序插入排序表现优异。数据为整数且有明确范围优先考虑计数排序或基数排序速度可以远超基于比较的排序。链表排序归并排序是链表排序的首选因为它不需要随机访问且是稳定的。外部排序数据量太大内存放不下归并排序是基础。最后一点体会学习排序算法目的不是为了在工作中自己实现它们除非有极其特殊的性能需求而是为了理解不同算法背后的思想分治、减治、桶思想等并能在适当的场景下做出正确的选择。当有人问你“为什么这里不用冒泡排序”时你能从时间、空间复杂度、稳定性、数据特性等多个维度给出专业的回答这才是学习的价值所在。数据结构与算法的学习最终目的是培养一种高效、优雅地解决问题的思维习惯这种习惯会让你在编程道路上走得更远、更稳。