2026年数据结构与算法学习指南：从入门到精通，程序员的必修之路

一、写在前面：算法是程序员的"内功心法"

2026年的春天，我参加了一场程序员的技术分享会。分享会上，一个在大厂做面试官的朋友，分享了他面试过的一个候选人的故事。这个候选人，简历非常漂亮——985名校毕业，在知名互联网公司工作了三年，做过好几个大型项目，技术栈也很全面，Java、Python、Go、前端、后端、数据库，什么都会。面试的时候，这个候选人表现得也很好。问他项目经验，他能滔滔不绝地讲半个小时；问他技术细节，他也能对答如流；问他系统设计，他也能说得头头是道。但是，当面试官让他写一道算法题的时候，他卡住了。那是一道很简单的算法题——给定一个数组，找出数组中出现次数最多的元素。这个候选人，想了半天，写了一个嵌套循环，时间复杂度是O(n²)。面试官提醒他，有没有更高效的方法？他想了半天，还是没想出来。最后，面试没有通过。面试官说：“这个候选人，工程能力很强，项目经验也很丰富，但是算法基础太差了。这么简单的一道题，都写不出最优解，我们不敢要。“我听了这个故事，感触很深。很多程序员，特别是做业务开发的程序员，都有一个误区：觉得算法不重要，觉得工作中用不到算法，觉得只要会用框架、会调API、能把业务功能做出来就行了。但是，真的是这样吗？不是的。算法是什么？算法是程序员的"内功心法”。就像武侠小说里的武功，招式是外功，内功是心法。没有内功，招式再花哨，也是花架子，中看不中用。有了深厚的内功，就算是最简单的招式，也能发挥出巨大的威力。编程也是一样的。框架、API、编程语言，这些都是"招式”，是外功。数据结构与算法，是"内功心法"，是根基。没有扎实的算法基础，就算你会用再多的框架，会调再多的API，也只是一个"API调用工程师"，遇到复杂的问题，就不知道怎么解决了。有了扎实的算法基础，你才能真正理解计算机的本质，才能写出高效、优雅、健壮的代码，才能解决复杂的问题，才能成为一个真正优秀的程序员。而且，现在的大厂面试，算法是必考的。不管你是校招还是社招，不管你是做前端还是后端，不管你是做业务还是做基础架构，算法都是绕不过去的坎。所以，不管你是刚入门的新手，还是已经工作多年的老手，都应该好好学习数据结构与算法。那么，数据结构与算法到底该怎么学？从哪里开始？学到什么程度？有什么好的学习方法和资源？这就是我想在这篇文章里和大家聊的话题。—# 二、数据结构与算法是什么？为什么要学？## 2.1 什么是数据结构？在讲怎么学之前，我们先搞清楚一个基本概念：什么是数据结构？什么是算法？先说说数据结构。数据结构，顾名思义，就是"数据的结构"。什么意思呢？就是数据在计算机中是怎么组织、怎么存储的。我们知道，计算机里有很多数据——数字、文字、图片、视频、音频等等。这些数据，不能乱七八糟地堆在那里，得有组织、有结构地存储起来，这样才能高效地访问、修改、删除。这就像什么？就像你家里的衣柜。你的衣柜里，有很多衣服——外套、衬衫、裤子、裙子、袜子、内衣等等。这些衣服，不能乱七八糟地堆在衣柜里，不然找的时候会很麻烦，而且也容易皱。所以，你会把衣服分门别类地放好——外套挂在衣架上，衬衫叠好放在抽屉里，裤子放在裤子架上，袜子放在袜子盒里，内衣放在内衣盒里。这样，找的时候就很方便，一眼就能找到。数据结构也是一样的道理。计算机里的数据，也需要分门别类地组织好、存储好，这样才能高效地访问、修改、删除。常见的数据结构有哪些呢？最基础的，有数组、链表、栈、队列、哈希表、树、图、堆等等。每一种数据结构，都有自己的特点和适用场景。比如，数组适合随机访问，链表适合频繁插入删除，栈适合后进先出的场景，队列适合先进先出的场景，哈希表适合快速查找，树适合层次结构的数据，图适合网状结构的数据，堆适合优先队列。选择合适的数据结构，能大大提高程序的效率。就像选择合适的收纳工具，能大大提高衣柜的空间利用率和找衣服的效率一样。## 2.2 什么是算法？说完了数据结构，再说说算法。算法是什么？算法就是解决问题的方法和步骤。比如，你要从北京去上海，有很多种方法——可以坐高铁，可以坐飞机，可以开车，可以坐大巴。每一种方法，都有不同的路线、不同的时间、不同的费用、不同的舒适度。这些不同的方法，就是不同的"算法"。再比如，你要在一个数组中查找一个元素，有很多种方法——可以从头到尾一个一个找（顺序查找），也可以先排序再二分查找（二分查找），也可以用哈希表直接查找。这些不同的方法，就是不同的"算法"。算法有好有坏。好的算法，效率高，用的时间少，占的内存少。坏的算法，效率低，用的时间多，占的内存多。比如，在一个有100万个元素的有序数组中查找一个元素，用顺序查找，平均要找50万次，最坏情况要找100万次；用二分查找，最多只需要找20次（因为2的20次方是1048576，大于100万）。你看，差距有多大！这就像什么？就像你从北京去上海，坐高铁要5个小时，坐飞机要2个小时，开车要12个小时，坐大巴要15个小时。不同的交通方式，时间差距很大。不同的算法，效率差距也很大。所以，选择合适的算法，能大大提高程序的效率。一个好的算法，可能让你的程序运行速度提高几百倍、几千倍，甚至几万倍。## 2.3 数据结构和算法的关系数据结构和算法，是密不可分的。数据结构是"容器"，是用来存储数据的；算法是"方法"，是用来操作数据的。没有数据结构，算法就没有用武之地——你连数据都存不下来，还谈什么操作数据呢？没有算法，数据结构就是一堆死数据——你把数据存下来了，但是不知道怎么操作、怎么处理，数据就没有价值。所以，数据结构和算法，是相辅相成的，缺一不可。这就像什么？就像厨房和菜谱。厨房是"容器"，里面有锅碗瓢盆、油盐酱醋、食材调料，是用来存储和准备食材的。菜谱是"方法"，告诉你怎么做菜，第一步做什么，第二步做什么，放多少盐，放多少醋，炒多长时间。没有厨房，菜谱就是纸上谈兵——你连做菜的工具和食材都没有，还谈什么做菜呢？没有菜谱，厨房就是一堆死东西——你有锅碗瓢盆、油盐酱醋、食材调料，但是不知道怎么做菜，这些东西就没有价值。所以，厨房和菜谱，是相辅相成的，缺一不可。数据结构和算法也是一样的。你要解决一个问题，首先要选择合适的数据结构来存储数据，然后选择合适的算法来操作数据。两者结合，才能高效地解决问题。比如，你要实现一个"最近最少使用（LRU）缓存"。首先，你需要选择合适的数据结构——用哈希表来存储键值对，实现O(1)的查找；用双向链表来维护访问顺序，实现O(1)的插入和删除。然后，你需要设计合适的算法——get的时候，把访问的节点移到链表头部；put的时候，如果键已存在，更新值并移到头部，如果键不存在，插入到头部，如果缓存满了，删除链表尾部的节点。你看，数据结构和算法结合起来，才能高效地实现LRU缓存。如果只用哈希表，无法维护访问顺序；如果只用链表，查找效率太低。两者结合，才能实现O(1)时间复杂度的get和put操作。## 2.4 为什么要学数据结构与算法？搞清楚了什么是数据结构和算法，我们再来说说：为什么要学数据结构与算法？我总结了一下，主要有以下几个原因：第一，算法是程序员的"内功心法"。就像我在开头说的，算法是程序员的内功心法。没有扎实的算法基础，就算你会用再多的框架，会调再多的API，也只是一个"API调用工程师"，遇到复杂的问题，就不知道怎么解决了。有了扎实的算法基础，你才能真正理解计算机的本质，才能写出高效、优雅、健壮的代码，才能解决复杂的问题，才能成为一个真正优秀的程序员。这就像什么？就像练武。没有内功，招式再花哨，也是花架子，中看不中用。有了深厚的内功，就算是最简单的招式，也能发挥出巨大的威力。第二，算法能提高你的编程能力。学习算法，能让你写出更高效、更优雅、更健壮的代码。比如，你写了一个程序，运行很慢，你不知道怎么优化。如果你学过算法，你就能分析程序的时间复杂度和空间复杂度，找出性能瓶颈，然后用更高效的算法来优化。再比如，你写了一个程序，有很多bug，你不知道怎么改。如果你学过算法，你就能更清晰地思考问题，更严谨地设计逻辑，写出更少bug的代码。学习算法，还能让你养成良好的编程习惯——写代码之前先思考，先设计，再动手；写代码的时候注意边界条件，注意异常处理；写完代码之后分析复杂度，优化性能。这些好习惯，能让你受益终身。第三，算法是大厂面试的必考内容。现在的大厂面试，算法是必考的。不管你是校招还是社招，不管你是做前端还是后端，不管你是做业务还是做基础架构，算法都是绕不过去的坎。为什么大厂这么看重算法？因为算法能考察一个人的逻辑思维能力、问题解决能力、学习能力和编码能力。这些能力，比你会不会用某个框架、会不会调某个API，更重要，也更能反映一个人的潜力。所以，如果你想进大厂，想拿高薪，就必须好好学习算法。算法不过关，就算你项目经验再丰富，技术栈再全面，也很难通过大厂的面试。第四，算法能让你更好地理解计算机科学。数据结构与算法，是计算机科学的基础。很多计算机科学的分支，比如数据库、操作系统、计算机网络、编译原理、人工智能、机器学习等等，都是建立在数据结构与算法的基础之上的。比如，数据库的索引，用的是B+树；操作系统的进程调度，用的是各种调度算法；计算机网络的路由，用的是最短路径算法；编译原理的语法分析，用的是栈和自动机；人工智能的搜索，用的是深度优先搜索、广度优先搜索、A算法；机器学习的分类，用的是决策树、K近邻、支持向量机等等。所以，学好了数据结构与算法，你才能更好地理解这些计算机科学的分支，才能更深入地学习和研究这些领域。第五，算法能锻炼你的逻辑思维能力。学习算法，能锻炼你的逻辑思维能力、抽象思维能力、问题解决能力。算法题，往往需要你把一个复杂的问题，抽象成一个数学模型，然后设计出高效的解决方案。这个过程，能锻炼你的抽象思维能力和逻辑思维能力。而且，算法题往往有很多种解法，你需要比较不同解法的优缺点，选择最优的解法。这个过程，能锻炼你的分析能力和决策能力。这些能力，不仅仅在编程中有用，在工作和生活中也很有用。遇到复杂的问题，你能更清晰地思考，更有条理地分析，更高效地解决。总之，学习数据结构与算法，好处多多。不管你是刚入门的新手，还是已经工作多年的老手，都应该好好学习数据结构与算法。—# 三、数据结构与算法的学习路线## 3.1 学习的三个阶段搞清楚了为什么要学，我们再来说说：该怎么学？学习数据结构与算法，不是一蹴而就的，需要循序渐进，分阶段学习。我把学习过程分为三个阶段：入门阶段、进阶阶段、精通阶段。**第一个阶段：入门阶段。**这个阶段的目标是：掌握基础的数据结构和算法，理解基本概念，能写出简单的算法题。这个阶段需要学习的内容包括：- 基础数据结构：数组、链表、栈、队列、哈希表- 基础算法：排序（冒泡、选择、插入、快速、归并、堆排序）、查找（顺序查找、二分查找）- 基础概念：时间复杂度、空间复杂度、大O表示法- 简单的算法题：LeetCode简单难度的题目这个阶段的重点是：理解基本概念，打好基础。不要追求速度，要把每个数据结构和算法的原理搞清楚，最好能自己手写实现一遍。比如，数组和链表的区别是什么？栈和队列的特点是什么？快速排序的原理是什么？时间复杂度是多少？这些基础问题，一定要搞清楚。这个阶段，就像学武功的入门阶段，先练基本功——扎马步、站桩、压腿、拉伸。基本功练扎实了，后面学招式才快。**第二个阶段：进阶阶段。**这个阶段的目标是：掌握更复杂的数据结构和算法，能解决中等难度的算法题，能在实际项目中运用算法。这个阶段需要学习的内容包括：- 进阶数据结构：树（二叉树、二叉搜索树、平衡二叉树、红黑树、字典树）、图（邻接矩阵、邻接表）、堆（大顶堆、小顶堆）、并查集- 进阶算法：递归、分治、贪心、动态规划、回溯、深度优先搜索、广度优先搜索、图算法（最短路径、最小生成树、拓扑排序）- 进阶的算法题：LeetCode中等难度的题目- 算法的实际应用：在实际项目中运用算法解决问题这个阶段的重点是：掌握常见的算法思想和算法模板，能举一反三。不要死记硬背，要理解算法的本质，知道什么场景下用什么算法。比如，动态规划的本质是什么？什么样的问题适合用动态规划？动态规划的状态转移方程怎么推导？这些问题，一定要搞清楚。这个阶段，就像学武功的进阶阶段，开始学招式——拳法、腿法、刀法、剑法。每种招式都有自己的特点和适用场景，要熟练掌握，能灵活运用。**第三个阶段：精通阶段。**这个阶段的目标是：能解决困难的算法题，能设计高效的算法，能在实际项目中优化算法，能参加算法竞赛。这个阶段需要学习的内容包括：- 高级数据结构：线段树、树状数组、平衡树（Splay、Treap）、跳表、布隆过滤器、后缀数组- 高级算法：字符串算法（KMP、Manacher、AC自动机）、计算几何、数论、组合数学、概率算法、近似算法、随机化算法- 困难的算法题：LeetCode困难难度的题目、算法竞赛的题目- 算法设计与优化：能根据问题设计高效的算法，能对现有算法进行优化这个阶段的重点是：开拓视野，提升思维高度。不要局限于常见的算法，要学习更多高级的算法和数据结构，提升自己的算法设计能力和优化能力。比如，遇到一个复杂的问题，你能不能自己设计出一个高效的算法？能不能对现有的算法进行优化，把时间复杂度从O(n²)降到O(n log n)，甚至O(n)？这些能力，需要长期的积累和练习。这个阶段，就像学武功的精通阶段，开始学内功心法——九阳神功、九阴真经、易筋经。内功深厚了，飞花摘叶皆可伤人，就算是最简单的招式，也能发挥出巨大的威力。当然，不是每个人都需要达到精通阶段。对于大部分程序员来说，达到进阶阶段，能解决中等难度的算法题，能在实际项目中运用算法，就已经足够了。如果你想进大厂，想做算法工程师，想参加算法竞赛，那就需要达到精通阶段。## 3.2 学习的顺序学习数据结构与算法，顺序很重要。不要一上来就学动态规划、图算法，那样会很打击信心，也学不好。正确的学习顺序应该是：从易到难，从基础到高级，循序渐进。我推荐的学习顺序是：1. 复杂度分析：先搞清楚时间复杂度和空间复杂度，学会用大O表示法分析算法的效率。这是基础中的基础，必须先掌握。2. 基础数据结构：数组、链表、栈、队列、哈希表。这些是最基础的数据结构，必须熟练掌握。3. 基础算法：排序、查找。排序是算法的基础，必须熟练掌握各种排序算法的原理和实现。4. 递归与分治：递归是很多算法的基础，分治是一种重要的算法思想。必须理解递归的本质，掌握分治的思想。5. 树：二叉树、二叉搜索树、平衡二叉树、红黑树、字典树。树是非常重要的数据结构，很多高级算法都是基于树的。6. 搜索算法：深度优先搜索、广度优先搜索、回溯。搜索是解决很多问题的通用方法，必须熟练掌握。7. 贪心算法：贪心是一种简单但有效的算法思想，必须掌握贪心的本质和适用场景。8. 动态规划：动态规划是算法中的重点和难点，必须花大量时间学习和练习。掌握动态规划的状态定义、状态转移方程、初始化、遍历顺序。9. 图：图的存储、图的遍历、最短路径、最小生成树、拓扑排序。图是一种复杂的数据结构，图算法也比较难，需要认真学习。10. 高级数据结构和算法：堆、并查集、线段树、树状数组、字符串算法、计算几何、数论等等。这些是进阶内容，根据自己的需求选择性学习。这个顺序，是从易到难、从基础到高级的。按照这个顺序学习，能循序渐进，逐步提升，不会太打击信心。这就像什么？就像盖房子。先打地基，再建一层，再建二层，再建三层，最后封顶。不能还没打地基，就想盖三层，那样房子会塌的。学习算法也是一样的。基础还没打好，就想学动态规划、图算法，那样学不好，也会打击信心。## 3.3 学习的方法有了学习路线和学习顺序，还需要有好的学习方法。好的学习方法，能让你事半功倍；不好的学习方法，会让你事倍功半。我总结了几个好的学习方法，分享给大家：**第一，理解为主，不要死记硬背。**学习算法，最重要的是理解，而不是死记硬背。很多人学习算法，喜欢背代码、背模板。比如，背快速排序的代码，背动态规划的模板。这样做，短期可能有点用，但是长期来看，效果不好。因为你不理解算法的本质，遇到稍微变化一点的题目，就不会做了。正确的做法是：理解算法的本质，搞清楚算法的原理、思路、适用场景。比如，快速排序的本质是什么？为什么叫快速排序？它的时间复杂度为什么是O(n log n)？什么情况下会退化到O(n²)？这些问题搞清楚了，就算你忘了代码，也能自己写出来。这就像什么？就像学数学。你不能死记硬背公式，要理解公式的推导过程和适用条件。理解了，就算忘了公式，也能自己推导出来。不理解，就算背下来了，遇到稍微变化一点的题目，也不会做。**第二，多动手写，不要只看不练。**学习算法，光看是不够的，必须多动手写。很多人学习算法，喜欢看视频、看书、看题解，觉得看懂了就是会了。其实不是的。看懂了，和自己能写出来，是两回事。很多时候，你觉得看懂了，但是一写就错，不是这里漏了，就是那里错了。所以，学习算法，一定要多动手写。每个数据结构，最好自己手写实现一遍；每个算法，最好自己手写实现一遍；每道算法题，最好自己先思考，先动手写，写不出来再看题解。多动手写，才能真正掌握算法，才能把算法变成自己的东西。这就像什么？就像学游泳。你看再多的游泳教程，看再多的游泳视频，不下水练习，永远也学不会游泳。只有下水练习，喝几口水，呛几口水，才能真正学会游泳。学习算法也是一样的。看再多的视频、书、题解，不动手写，永远也学不会算法。只有多动手写，多练习，才能真正掌握算法。**第三，多总结，多归纳。**学习算法，要多总结，多归纳。算法题虽然千变万化，但是算法的思想和模板是有限的。很多题目，看起来不一样，但是本质上是同一种算法思想，用的是同一种算法模板。所以，学习算法，要善于总结和归纳。把相似的题目归为一类，总结出这类题目的通用解法和算法模板。比如，动态规划的题目，可以分为背包问题、打家劫舍问题、股票问题、子序列问题等等。每一类问题，都有自己的特点和通用解法。多总结，多归纳，才能举一反三，遇到新的题目，也能快速找到解题思路。这就像什么？就像整理衣柜。你把衣服分门别类地放好——外套、衬衫、裤子、裙子、袜子、内衣，各归各位。找的时候就很方便，一眼就能找到。如果衣服乱七八糟地堆在一起，找的时候就很麻烦。学习算法也是一样的。你把题目分门别类地归纳好，每一类都有通用解法和算法模板。遇到新的题目，先判断属于哪一类，然后用对应的通用解法，就能快速解决。**第四，循序渐进，不要急于求成。**学习算法，要循序渐进，不要急于求成。很多人学习算法，一上来就刷困难题，结果一道题都做不出来，很受打击，然后就放弃了。这样是不对的。正确的做法是：从简单题开始，先把简单题做熟，建立信心，然后再做中等题，最后再做困难题。循序渐进，逐步提升。而且，学习算法是一个长期的过程，不是一蹴而就的。不要指望学一个月、两个月就能成为算法大神。需要长期的积累和练习，才能真正掌握算法。所以，学习算法，要有耐心，要坚持。每天刷几道题，日积月累，时间长了，算法能力自然就提升了。这就像什么？就像健身。你不能指望练一个月、两个月就能练成肌肉男。需要长期的坚持，每天锻炼，日积月累，才能练出好身材。如果急于求成，一开始就举很重的哑铃，很容易受伤，然后就放弃了。学习算法也是一样的。要循序渐进，长期坚持，才能真正掌握算法。**第五，学以致用，在实际项目中运用。**学习算法，最终的目的是为了用。所以，要学以致用，在实际项目中运用算法。很多人觉得，工作中用不到算法。其实不是的。工作中很多地方都用到了算法，只是你没有意识到而已。比如，你要在一个列表中查找一个元素，用的是查找算法；你要对一个列表进行排序，用的是排序算法；你要遍历一个树形结构，用的是深度优先搜索或广度优先搜索；你要做缓存，用的是LRU算法；你要做任务调度，用的是贪心算法或优先级队列；你要做路径规划，用的是最短路径算法。所以，在实际项目中，要有意识地运用算法。遇到问题的时候，先想想能不能用算法来优化，能不能用更高效的数据结构来存储数据。这样，既能提升程序的性能，又能巩固自己的算法知识。这就像什么？就像学武功。你学了很多招式，但是不用，就等于白学。要在实战中运用，才能真正掌握这些招式，才能知道什么时候用什么招式，怎么用最有效。学习算法也是一样的。要在实际项目中运用，才能真正掌握算法，才能知道什么时候用什么算法，怎么用最有效。—# 四、核心数据结构详解## 4.1 数组：最基础的数据结构讲完了学习路线和方法，我们来详细讲讲核心的数据结构和算法。首先是数组。数组是最基础、最简单的数据结构。几乎所有的编程语言，都内置了数组类型。什么是数组？数组就是一组相同类型元素的有序集合。比如，你要存储一个班级50个学生的成绩，就可以用一个int类型的数组，长度为50。数组的每个元素，存储一个学生的成绩。数组的特点是什么？第一，数组的元素在内存中是连续存储的。这是数组最重要的特点。因为元素是连续存储的，所以可以通过下标（索引）直接访问任意元素，时间复杂度是O(1)。比如，你要访问数组的第i个元素，直接用array[i]就能访问，不需要遍历整个数组。这就像你住在一个酒店里，房间号是连续的，你要找第100号房间，直接坐电梯到10楼，找到100号房间就行了，不需要从1号房间一个一个找。第二，数组的大小是固定的。在大部分编程语言中，数组一旦创建，大小就不能改变了。如果你需要存储更多的元素，就需要创建一个更大的数组，然后把原来的元素复制过去。这就像你买了一个固定大小的衣柜，只能放100件衣服。如果你的衣服超过了100件，就需要买一个更大的衣柜，然后把原来的衣服搬过去。第三，数组的插入和删除效率低。因为数组的元素是连续存储的，如果你要在中间插入一个元素，就需要把插入位置后面的所有元素都往后移一位；如果你要删除中间的一个元素，就需要把删除位置后面的所有元素都往前移一位。这个过程的时间复杂度是O(n)。这就像你在一排座位中插入一个人。如果要在中间插入，就需要把后面的人都往后挪一个位置，才能腾出一个位置。如果要删除中间的一个人，就需要把后面的人都往前挪一个位置，才能补上空位。这个过程很麻烦，效率很低。数组的优点和缺点总结一下：- 优点：随机访问效率高，O(1)时间复杂度；内存连续，缓存友好；简单易用。- 缺点：插入和删除效率低，O(n)时间复杂度；大小固定，不能动态扩展；可能有内存浪费（如果数组很大，但是用的元素很少）。数组的适用场景：- 需要频繁随机访问元素的场景- 元素数量已知，变化不大的场景- 对内存要求较高，需要连续内存的场景数组是最基础的数据结构，很多其他的数据结构，比如栈、队列、哈希表、堆等等，都是基于数组实现的。所以，一定要熟练掌握数组。## 4.2 链表：灵活的动态数据结构接下来是链表。链表是一种常见的基础数据结构。和数组不同，链表的元素在内存中不是连续存储的，而是通过指针连接在一起的。什么是链表？链表就是一组节点的集合，每个节点包含两部分：数据域和指针域。数据域存储元素的值，指针域存储下一个节点的地址。比如，你要存储一个列表，但是不知道元素的数量，可能会频繁插入和删除，这时候用链表就比较合适。链表的特点是什么？第一，链表的元素在内存中不是连续存储的。每个节点可以存储在内存的任意位置，通过指针连接在一起。所以，链表不需要连续的内存空间，内存利用率更高。这就像你住的小区，房子不是连在一起的，而是分散在小区的各个位置，通过道路连接在一起。你要找某个人家，需要知道他家的地址，然后沿着道路走过去。第二，链表的大小是动态的。链表不需要预先分配大小，可以根据需要动态增加或删除节点。所以，链表不会有内存浪费，也不会有大小不够的问题。这就像你用绳子串珠子。你想串多少颗珠子，就串多少颗珠子。想加一颗珠子，就找个位置穿进去；想减一颗珠子，就把那颗珠子取下来。非常灵活。第三，链表的插入和删除效率高。因为链表的元素不是连续存储的，插入和删除节点，只需要修改指针的指向，不需要移动其他节点。所以，链表的插入和删除操作，时间复杂度是O(1)（前提是你已经找到了要插入或删除的位置）。这就像你在一串珠子中插入或删除一颗珠子。你只需要把绳子解开，把新珠子穿进去，或者把旧珠子取出来，然后把绳子系好就行了。不需要移动其他珠子，非常方便。第四，链表的随机访问效率低。因为链表的元素不是连续存储的，你要访问第i个元素，必须从头节点开始，一个一个地遍历，直到找到第i个元素。所以，链表的随机访问操作，时间复杂度是O(n)。这就像你在小区里找第100户人家。你不知道第100户人家在哪里，必须从第1户开始，一户一户地找，直到找到第100户。非常麻烦，效率很低。链表有很多种类型，常见的有：- 单链表：每个节点只有一个指针，指向下一个节点。只能从头向尾遍历。- 双向链表：每个节点有两个指针，一个指向下一个节点，一个指向前一个节点。可以从头向尾遍历，也可以从尾向头遍历。- 循环链表：尾节点的指针指向头节点，形成一个环。可以循环遍历。链表的优点和缺点总结一下：- 优点：插入和删除效率高，O(1)时间复杂度；大小动态，不需要预先分配；内存利用率高，不需要连续内存。- 缺点：随机访问效率低，O(n)时间复杂度；每个节点需要额外的指针空间，有一定的内存开销；缓存不友好，因为节点不连续。链表的适用场景：- 需要频繁插入和删除元素的场景- 元素数量未知，变化较大的场景- 不需要频繁随机访问元素的场景链表也是非常基础的数据结构，很多其他的数据结构，比如栈、队列、哈希表（链地址法）、图（邻接表）等等，都可以用链表实现。所以，一定要熟练掌握链表。## 4.3 栈和队列：特殊的线性数据结构接下来是栈和队列。栈和队列是两种特殊的线性数据结构。它们的底层可以用数组实现，也可以用链表实现，但是它们的操作有特殊的限制。先说说栈。什么是栈？栈是一种"后进先出"（Last In First Out，LIFO）的数据结构。就像一摞盘子，你放盘子的时候，从下往上放；你取盘子的时候，从上往下取。最后放进去的盘子，最先被取出来。栈的操作有哪些？- push（入栈）：把一个元素放到栈顶。- pop（出栈）：把栈顶的元素取出来。- peek（查看栈顶）：查看栈顶的元素，但是不取出来。- isEmpty（判断是否为空）：判断栈是否为空。栈的特点是什么？栈只能在栈顶操作，不能在栈中间或栈底操作。所以，栈的插入和删除操作，都是在栈顶进行的，时间复杂度是O(1)。栈的适用场景：- 函数调用：函数的调用栈，就是用栈实现的。调用函数的时候，把函数的上下文压入栈；函数返回的时候，把函数的上下文弹出栈。- 表达式求值：比如，中缀表达式转后缀表达式，后缀表达式求值，都是用栈实现的。- 括号匹配：判断括号是否匹配，用栈实现。遇到左括号压栈，遇到右括号出栈，最后判断栈是否为空。- 浏览器的前进后退：浏览器的前进后退功能，用两个栈实现。- 深度优先搜索（DFS）：深度优先搜索，用栈实现（或者用递归，递归本质上也是用栈）。再说说队列。什么是队列？队列是一种"先进先出"（First In First Out，FIFO）的数据结构。就像排队买东西，先来的人先买，后来的人后买。队列的操作有哪些？- enqueue（入队）：把一个元素放到队尾。- dequeue（出队）：把队首的元素取出来。- peek（查看队首）：查看队首的元素，但是不取出来。- isEmpty（判断是否为空）：判断队列是否为空。队列的特点是什么？队列只能在队尾插入，在队首删除，不能在队列中间操作。所以，队列的插入和删除操作，时间复杂度是O(1)。队列的适用场景：- 任务调度：比如，操作系统的进程调度，任务队列，都是用队列实现的。- 消息队列：比如，Kafka、RabbitMQ等消息队列，本质上就是队列。- 广度优先搜索（BFS）：广度优先搜索，用队列实现。- 缓冲区：比如，键盘输入缓冲区，打印机缓冲区，都是用队列实现的。- 限流：比如，令牌桶算法、漏桶算法，都是用队列实现的。队列还有很多变种，比如：- 双端队列（Deque）：两端都可以插入和删除的队列。- 优先队列（Priority Queue）：元素有优先级，优先级高的元素先出队。优先队列一般用堆实现。- 循环队列：用数组实现的队列，尾指针到达数组末尾后，回到数组开头，形成一个环。可以避免数组的浪费。栈和队列，虽然简单，但是非常常用。很多复杂的算法和数据结构，都是基于栈和队列的。所以，一定要熟练掌握栈和队列。## 4.4 哈希表：高效的查找数据结构接下来是哈希表。哈希表（Hash Table），也叫散列表，是一种非常高效的数据结构。它通过哈希函数，把键（key）映射到数组的下标，从而实现O(1)时间复杂度的查找、插入和删除。什么是哈希表？举个例子。你要存储一个班级学生的成绩，每个学生有一个学号（key）和一个成绩（value）。你可以用一个数组来存储，数组的下标是学号，数组的元素是成绩。这样，你要查找某个学生的成绩，直接用学号作为下标，就能O(1)时间找到。但是，学号可能很大，比如2026000001，这时候数组的大小就需要很大，会浪费很多内存。而且，学号可能不是连续的，中间有很多空位，也会浪费内存。这时候，就需要哈希函数了。哈希函数的作用，就是把任意大小的key，映射到一个固定大小的数组下标。比如，你可以用"学号 % 1000"作为哈希函数，把学号映射到0-999的下标。这样，数组的大小只需要1000，就够了。但是，哈希函数可能会产生冲突——两个不同的key，经过哈希函数计算后，得到了相同的下标。这时候，就需要解决冲突。解决冲突的方法，常见的有两种：第一，链地址法（拉链法）。每个数组的元素，是一个链表的头节点。所有哈希值相同的key，都放在同一个链表中。查找的时候，先根据哈希值找到对应的链表，然后在链表中遍历查找。这就像你有很多个篮子，每个篮子有一个编号。你要放一个东西，先根据东西的特征，算出它应该放在哪个篮子里，然后放到那个篮子里。如果篮子里已经有东西了，就和原来的东西放在一起。找的时候，先根据东西的特征，算出它在哪个篮子里，然后在那个篮子里找。第二，开放地址法。如果哈希值对应的位置已经被占用了，就按照一定的规则，找下一个空的位置。比如，线性探测（依次往后找）、二次探测（按照平方的步长找）、双重哈希（用另一个哈希函数计算步长）。这就像你去电影院看电影，你买的座位号是10号，但是10号座位已经有人坐了，你就找11号座位，如果11号也有人，就找12号，直到找到一个空座位。哈希表的特点是什么？第一，查找、插入、删除的平均时间复杂度都是O(1)。这是哈希表最大的优势，非常高效。第二，哈希表的元素是无序的。因为哈希函数把key映射到数组的下标，是没有顺序的。所以，哈希表不支持有序遍历。第三，哈希表有一定的内存浪费。因为哈希表需要预留一定的空间，避免冲突太多。一般来说，哈希表的负载因子（元素数量/数组大小）保持在0.7左右比较合适。哈希表的优点和缺点总结一下：- 优点：查找、插入、删除的平均时间复杂度都是O(1)，非常高效；实现简单，使用方便。- 缺点：元素无序，不支持有序遍历；有一定的内存浪费；哈希函数设计不好的话，冲突太多，性能会下降到O(n)；不支持范围查找。哈希表的适用场景：- 需要频繁查找、插入、删除的场景- 不需要有序遍历的场景- 不需要范围查找的场景- 统计频率、去重、缓存等场景哈希表是非常常用、非常高效的数据结构。在实际开发中，几乎每个项目都会用到哈希表。比如，Java的HashMap、Python的dict、Go的map，都是哈希表。所以，一定要熟练掌握哈希表。## 4.5 树：层次化的数据结构接下来是树。树是一种非常重要的非线性数据结构。它模拟了现实世界中的树的结构——有一个根节点，根节点下面有若干个子节点，每个子节点下面又有若干个子节点，以此类推，形成一个层次化的结构。什么是树？树是由n（n>=0）个节点组成的有限集合。当n=0时，称为空树；当n>0时，有一个特殊的节点，称为根节点，根节点没有父节点；其余节点分为m（m>=0）个互不相交的有限集合，每个集合又是一棵树，称为根节点的子树。树的相关概念：- 节点的度：一个节点的子节点的个数。- 树的度：树中所有节点的度的最大值。- 叶子节点：度为0的节点，也就是没有子节点的节点。- 分支节点：度不为0的节点。- 节点的层次：根节点是第1层，根节点的子节点是第2层，以此类推。- 树的深度（高度）：树中节点的最大层次。- 节点的祖先：从根节点到该节点的路径上的所有节点。- 节点的子孙：该节点的所有子节点，以及子节点的子节点，以此类推。树的种类有很多，常见的有：- 二叉树：每个节点最多有两个子节点，分别称为左子节点和右子节点。- 二叉搜索树（BST）：一种特殊的二叉树，左子树的所有节点的值都小于根节点的值，右子树的所有节点的值都大于根节点的值。- 平衡二叉树（AVL树）：一种特殊的二叉搜索树，左右子树的高度差不超过1，并且左右子树都是平衡二叉树。- 红黑树：一种特殊的二叉搜索树，节点有红色和黑色两种颜色，通过颜色约束来保证树的平衡。- 字典树（Trie树）：一种特殊的树，用于存储字符串，每个节点表示一个字符，从根节点到某个节点的路径，表示一个字符串。- B树和B+树：一种多路搜索树，每个节点可以有多个子节点，用于数据库和文件系统的索引。树的遍历方式有四种：- 前序遍历：先访问根节点，再遍历左子树，再遍历右子树。- 中序遍历：先遍历左子树，再访问根节点，再遍历右子树。- 后序遍历：先遍历左子树，再遍历右子树，再访问根节点。- 层序遍历：按照层次，从上到下，从左到右，依次访问每个节点。树的优点和缺点总结一下：- 优点：层次化结构，适合表示层次化的数据；查找、插入、删除的效率比较高（平衡树的时间复杂度是O(log n)）；支持有序遍历和范围查找。- 缺点：实现比较复杂；需要额外的指针空间；不平衡的树，性能会下降到O(n)。树的适用场景：- 需要表示层次化数据的场景，比如文件系统、组织机构、分类目录等。- 需要高效查找、插入、删除，并且需要有序遍历和范围查找的场景，比如数据库索引、Set、Map等。- 字典树适合字符串查找、前缀匹配、自动补全等场景。- 堆（一种特殊的树）适合优先队列、Top K问题、排序等场景。树是非常重要、非常常用的数据结构。很多高级的数据结构和算法，都是基于树的。所以，一定要熟练掌握树，特别是二叉树、二叉搜索树、平衡树、红黑树、字典树等。## 4.6 图：网状的数据结构最后是图。图是一种复杂的非线性数据结构。它模拟了现实世界中的网状结构——由若干个顶点和若干条边组成，顶点之间通过边连接。什么是图？图是由顶点（Vertex）的集合和边（Edge）的集合组成的。顶点表示对象，边表示对象之间的关系。比如，社交网络中，每个人是一个顶点，两个人是朋友，就有一条边连接他们；地图中，每个地点是一个顶点，两个地点之间有道路，就有一条边连接他们；网络中，每台计算机是一个顶点，两台计算机之间有网络连接，就有一条边连接他们。图的相关概念：- 有向图：边有方向的图。比如，A到B有边，但是B到A不一定有边。- 无向图：边没有方向的图。比如，A到B有边，B到A也有边。- 加权图：边有权重的图。比如，A到B的边的权重是5，表示A到B的距离是5。- 顶点的度：与该顶点相连的边的数量。在有向图中，分为入度（指向该顶点的边的数量）和出度（从该顶点出发的边的数量）。- 路径：从一个顶点到另一个顶点，经过的顶点序列。- 环：起点和终点相同的路径。- 连通图：任意两个顶点之间都有路径的无向图。- 强连通图：任意两个顶点之间都有双向路径的有向图。图的存储方式有两种常见的：第一，邻接矩阵。用一个二维数组来表示图，数组的下标表示顶点，数组的值表示边。比如，adj[i][j] = 1，表示顶点i和顶点j之间有边；adj[i][j] = 0，表示没有边。对于加权图，adj[i][j]表示边的权重。邻接矩阵的优点是：简单直观，查找边的时间复杂度是O(1)；缺点是：占用的空间大，空间复杂度是O(n²)，对于稀疏图（边很少的图），浪费很多空间；而且，添加和删除顶点的操作比较麻烦。第二，邻接表。用一个数组来存储所有的顶点，每个顶点对应一个链表，链表中存储与该顶点相连的其他顶点。邻接表的优点是：占用的空间小，空间复杂度是O(n + e)，对于稀疏图，节省很多空间；添加和删除顶点的操作比较方便。缺点是：查找边的时间复杂度是O(度)，不如邻接矩阵快。图的常见算法：- 图的遍历：深度优先搜索（DFS）、广度优先搜索（BFS）。- 最短路径：Dijkstra算法、Bellman-Ford算法、Floyd算法、SPFA算法。- 最小生成树：Prim算法、Kruskal算法。- 拓扑排序：Kahn算法、DFS算法。- 关键路径：用于AOE网。- 网络流：最大流、最小割、费用流。图的优点和缺点总结一下：- 优点：能表示复杂的网状关系；能解决很多复杂的问题，比如最短路径、最小生成树、网络流等。- 缺点：实现比较复杂；算法比较难，需要花较多时间学习；对于大规模的图，计算量很大。图的适用场景：- 社交网络：朋友关系、关注关系等。- 地图导航：最短路径、路径规划等。- 网络拓扑：计算机网络、通信网络等。- 推荐系统：协同过滤、关联推荐等。- 任务调度：拓扑排序、关键路径等。图是一种复杂但非常重要的数据结构。虽然在日常开发中，可能不常用到图，但是在很多特定的领域，比如地图、社交网络、推荐系统等，图是非常核心的数据结构。所以，了解图的基本概念和常见算法，是很有必要的。—# 五、核心算法详解## 5.1 排序算法：算法的基础讲完了核心数据结构，我们来详细讲讲核心算法。首先是排序算法。排序是最基础、最常用的算法。很多其他的算法，都是建立在排序的基础之上的。比如，二分查找，就需要先排序；很多贪心算法，也需要先排序。排序算法有很多种，常见的有：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序、希尔排序、计数排序、桶排序、基数排序等等。我们可以从几个维度来比较不同的排序算法：- 时间复杂度：最好、最坏、平均时间复杂度。- 空间复杂度：需要的额外空间。- 稳定性：相等的元素，排序后相对顺序是否不变。如果不变，就是稳定的；如果可能改变，就是不稳定的。- 适用场景：适合什么规模的数据，适合什么特点的数据。我们来详细讲讲几种最常用的排序算法。**冒泡排序（Bubble Sort）**冒泡排序是最简单的排序算法。它的原理是：重复地遍历要排序的列表，依次比较相邻的两个元素，如果它们的顺序错误，就交换它们。遍历列表的工作是重复进行的，直到没有再需要交换的元素，也就是说列表已经排序完成了。冒泡排序的名字由来，是因为越小的元素，会经由交换，慢慢"浮"到列表的顶端，就像水中的气泡一样。冒泡排序的时间复杂度：最好是O(n)（已经有序的情况），最坏是O(n²)，平均是O(n²)。空间复杂度是O(1)。是稳定的排序算法。冒泡排序的优点是：简单，容易理解，实现容易；是稳定的排序算法。缺点是：效率低，时间复杂度高，不适合大规模的数据。冒泡排序的适用场景：数据规模很小，或者数据基本有序的情况。**选择排序（Selection Sort）**选择排序的原理是：首先在未排序的序列中找到最小的元素，存放到排序序列的起始位置；然后，再从剩余未排序的元素中继续寻找最小的元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的时间复杂度：最好、最坏、平均都是O(n²)。空间复杂度是O(1)。是不稳定的排序算法。选择排序的优点是：简单，容易理解，实现容易；交换次数少，最多n-1次交换。缺点是：效率低，时间复杂度高，不适合大规模的数据；不稳定。选择排序的适用场景：数据规模很小，或者交换操作成本很高的情况。**插入排序（Insertion Sort）**插入排序的原理是：通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序的工作方式，就像我们打扑克牌的时候，整理手中的牌一样。每拿到一张新牌，就把它插入到手中已经排好序的牌中的合适位置。插入排序的时间复杂度：最好是O(n)（已经有序的情况），最坏是O(n²)，平均是O(n²)。空间复杂度是O(1)。是稳定的排序算法。插入排序的优点是：简单，容易理解，实现容易；是稳定的排序算法；对于基本有序的数据，效率很高；在数据规模很小的时候，效率很高。缺点是：效率低，时间复杂度高，不适合大规模的数据。插入排序的适用场景：数据规模很小，或者数据基本有序的情况。很多高级的排序算法，比如快速排序、归并排序，在数据规模很小的时候，会切换到插入排序，因为小数据量的时候，插入排序的常数因子更小，效率更高。**快速排序（Quick Sort）**快速排序是一种非常高效的排序算法，也是实际开发中最常用的排序算法之一。快速排序的原理是：采用分治的思想，选择一个基准元素（pivot），把数组分成两部分——小于基准的部分和大于基准的部分；然后，对这两部分分别递归地进行快速排序；最后，把排序好的两部分和基准拼接起来，就得到了排序好的数组。快速排序的时间复杂度：最好是O(n log n)，最坏是O(n²)（每次选择的基准都是最大或最小的元素），平均是O(n log n)。空间复杂度是O(log n)（递归栈的空间）。是不稳定的排序算法。快速排序的优点是：效率高，平均时间复杂度是O(n log n)；常数因子小，实际运行速度快；原地排序，不需要额外的空间。缺点是：最坏情况时间复杂度是O(n²)；不稳定。快速排序的适用场景：大部分场景都适用，特别是大规模的数据。很多编程语言的内置排序函数，比如C的qsort、Java的Arrays.sort（基本类型），都是用快速排序实现的。**归并排序（Merge Sort）**归并排序也是一种高效的排序算法，采用分治的思想。归并排序的原理是：把数组分成两半，分别对这两半进行归并排序；然后，把排序好的两半合并（merge）起来，就得到了排序好的数组。归并排序的核心是合并操作——把两个有序的数组合并成一个有序的数组。合并的方法是：用两个指针，分别指向两个数组的起始位置，比较两个指针指向的元素，把较小的元素放到结果数组中，然后把对应的指针往后移一位。重复这个过程，直到其中一个数组的元素都放到结果数组中，然后把另一个数组中剩余的元素放到结果数组中。归并排序的时间复杂度：最好、最坏、平均都是O(n log n)。空间复杂度是O(n)（需要额外的数组来存储合并的结果）。是稳定的排序算法。归并排序的优点是：效率高，时间复杂度稳定，都是O(n log n)；是稳定的排序算法；适合链表排序，因为链表的合并不需要额外的空间。缺点是：需要额外的空间，空间复杂度是O(n)；常数因子比快速排序大，原地排序的时候效率不如快速排序。归并排序的适用场景：需要稳定排序的场景；链表排序；外部排序（数据量太大，内存放不下，需要分块排序后合并）。**堆排序（Heap Sort）**堆排序是利用堆这种数据结构来排序的算法。堆是一种特殊的完全二叉树，分为大顶堆和小顶堆。大顶堆的每个节点的值，都大于或等于它的子节点的值；小顶堆的每个节点的值，都小于或等于它的子节点的值。堆排序的原理是：首先，把数组构建成一个大顶堆；然后，把堆顶的元素（最大的元素）和堆的最后一个元素交换，这样最大的元素就放到了数组的末尾；然后，把剩余的元素重新调整成大顶堆，再把堆顶的元素和堆的最后一个元素交换。重复这个过程，直到堆的大小为1，数组就排序好了。堆排序的时间复杂度：最好、最坏、平均都是O(n log n)。空间复杂度是O(1)。是不稳定的排序算法。堆排序的优点是：效率高，时间复杂度稳定，都是O(n log n)；原地排序，不需要额外的空间。缺点是：常数因子比快速排序大，实际运行速度不如快速排序；不稳定。堆排序的适用场景：需要原地排序，并且需要稳定的O(n log n)时间复杂度的场景；优先队列、Top K问题等。排序算法的对比表：| 排序算法 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 ||———|————–|————–|————–|———-|——–|| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 || 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 || 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 || 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 || 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 || 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |排序算法是算法的基础，一定要熟练掌握。特别是快速排序、归并排序、堆排序这三种O(n log n)的排序算法，一定要理解原理，能手写实现。## 5.2 查找算法：高效定位元素接下来是查找算法。查找，就是在一个数据集合中，找到满足条件的元素。查找是非常常用的操作，很多程序都需要频繁地查找元素。查找算法有很多种，常见的有：顺序查找、二分查找、哈希查找、树表查找等等。我们来详细讲讲几种最常用的查找算法。**顺序查找（Sequential Search）**顺序查找，也叫线性查找，是最简单的查找算法。它的原理是：从数据集合的第一个元素开始，依次比较每个元素和目标值，如果相等，就查找成功；如果遍历完整个集合都没有找到，就查找失败。顺序查找的时间复杂度：最好是O(1)（第一个元素就是目标值），最坏是O(n)（最后一个元素是目标值，或者没有目标值），平均是O(n)。空间复杂度是O(1)。顺序查找的优点是：简单，容易理解，实现容易；对数据集合没有要求，不需要有序，不需要特殊的数据结构。缺点是：效率低，时间复杂度高，不适合大规模的数据。顺序查找的适用场景：数据规模很小，或者数据集合无序的情况。**二分查找（Binary Search）**二分查找，也叫折半查找，是一种高效的查找算法。它的前提条件是：数据集合必须是有序的。二分查找的原理是：每次都取中间的元素和目标值比较，如果相等，就查找成功；如果目标值比中间元素小，就只在左半部分查找；如果目标值比中间元素大，就只在右半部分查找。这样，每次比较都能排除一半的元素，大大提高了查找效率。二分查找的时间复杂度：最好是O(1)（中间元素就是目标值），最坏是O(log n)，平均是O(log n)。空间复杂度是O(1)（迭代实现）或者O(log n)（递归实现）。二分查找的优点是：效率高，时间复杂度是O(log n)；实现简单。缺点是：要求数据集合必须是有序的；要求数据集合支持随机访问（比如数组），链表不适合二分查找。二分查找的适用场景：数据集合有序，并且支持随机访问的情况。比如，在有序数组中查找元素。二分查找虽然简单，但是有很多变种和应用场景。比如：- 查找第一个等于目标值的元素- 查找最后一个等于目标值的元素- 查找第一个大于等于目标值的元素- 查找最后一个小于等于目标值的元素- 查找旋转数组的最小值- 查找峰值元素- 求平方根这些变种，都是面试中常考的题目，一定要熟练掌握。**哈希查找（Hash Search）**哈希查找，就是利用哈希表来查找元素。我们在前面讲哈希表的时候已经讲过了，哈希表通过哈希函数，把键映射到数组的下标，从而实现O(1)时间复杂度的查找。哈希查找的时间复杂度：平均是O(1)，最坏是O(n)（哈希冲突很多的时候）。空间复杂度是O(n)。哈希查找的优点是：效率高，平均时间复杂度是O(1)；插入和删除的效率也很高。缺点是：需要额外的空间；元素无序，不支持有序遍历和范围查找；哈希函数设计不好的话，冲突太多，性能会下降。哈希查找的适用场景：需要频繁查找、插入、删除，并且不需要有序遍历和范围查找的场景。在实际开发中，哈希查找是最常用的查找方式之一。树表查找树表查找，就是利用树这种数据结构来查找元素。比如，二叉搜索树、平衡二叉树、红黑树、B树、B+树等等。以二叉搜索树为例，它的查找原理是：从根节点开始，如果目标值等于根节点的值，就查找成功；如果目标值比根节点的值小，就去左子树查找；如果目标值比根节点的值大，就去右子树查找。二叉搜索树的查找时间复杂度：最好是O(log n)（树是平衡的），最坏是O(n)（树退化成链表）。为了避免树退化成链表，就有了平衡二叉树、红黑树等平衡树。平衡树的查找时间复杂度稳定在O(log n)。树表查找的优点是：效率高，时间复杂度是O(log n)；支持有序遍历和范围查找；插入和删除的效率也很高。缺点是：实现比较复杂；需要额外的指针空间。树表查找的适用场景：需要高效查找、插入、删除，并且需要有序遍历和范围查找的场景。比如，数据库的索引、Set、Map等。查找算法的对比表：| 查找算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 是否要求有序 | 适用场景 ||———|————–|————–|———-|————|———|| 顺序查找 | O(n) | O(n) | O(1) | 否 | 小规模、无序数据 || 二分查找 | O(log n) | O(log n) | O(1) | 是 | 有序、支持随机访问的数据 || 哈希查找 | O(1) | O(n) | O(n) | 否 | 频繁查找、插入、删除，不需要有序遍历 || 树表查找 | O(log n) | O(log n) | O(n) | 是（中序遍历有序） | 频繁查找、插入、删除，需要有序遍历和范围查找 |查找算法是非常常用的算法，一定要熟练掌握。特别是二分查找和哈希查找，是面试中常考的内容，一定要深入理解，熟练运用。## 5.3 递归与分治：把大问题拆成小问题接下来是递归与分治。递归是一种非常重要的编程技巧，也是很多算法的基础。分治是一种重要的算法思想，很多高效的算法，都是基于分治思想的。先说说递归。什么是递归？递归就是函数自己调用自己。递归的两个关键要素：第一，递归出口（终止条件）：递归必须有一个终止条件，当满足终止条件的时候，递归就停止了。如果没有终止条件，递归就会无限进行下去，最后栈溢出。第二，递归表达式：函数自己调用自己，但是问题的规模要比原来小。这样，问题的规模会越来越小，最终到达递归出口。举个经典的递归例子：计算n的阶乘。n的阶乘，定义是：n! = n * (n-1) * (n-2) * … * 1。用递归的方式来计算：- 递归出口：当n=1的时候，1! = 1。- 递归表达式：n! = n * (n-1)!。这样，计算n的阶乘，就变成了计算(n-1)的阶乘，然后乘以n。而计算(n-1)的阶乘，又变成了计算(n-2)的阶乘，然后乘以(n-1)。以此类推，直到n=1，到达递归出口，然后再逐层返回，最终得到n的阶乘。递归的优点是：代码简洁，逻辑清晰，容易理解；适合解决具有自相似结构的问题，比如树的遍历、图的深度优先搜索、分治算法等。递归的缺点是：效率可能不如迭代，因为递归需要函数调用的开销；可能会有重复计算，比如斐波那契数列的递归实现，会有大量的重复计算；递归深度太大的话，会栈溢出。所以，使用递归的时候，要注意：一定要有递归出口；尽量避免重复计算（可以用记忆化搜索来优化）；递归深度不要太大（可以用迭代来替代，或者用尾递归优化）。再说说分治。什么是分治？分治就是"分而治之"，把一个大问题，拆分成若干个规模较小的、与原问题相似的子问题，递归地解决这些子问题，然后把子问题的解合并起来，得到原问题的解。分治算法的三个步骤：第一，分解（Divide）：把原问题分解成若干个规模较小的、相互独立的、与原问题形式相同的子问题。第二，解决（Conquer）：递归地解决各个子问题。如果子问题的规模足够小，就直接解决。第三，合并（Combine）：把子问题的解合并起来，得到原问题的解。举个经典的分治例子：归并排序。归并排序就是典型的分治算法：- 分解：把数组分成两半。- 解决：递归地对这两半分别进行归并排序。- 合并：把排序好的两半合并起来，得到排序好的数组。再举一个分治的例子：快速排序。快速排序也是分治算法：- 分解：选择一个基准元素，把数组分成两部分——小于基准的部分和大于基准的部分。- 解决：递归地对这两部分分别进行快速排序。- 合并：因为是原地排序，所以不需要显式的合并，排序好的两部分自然就在数组中了。分治算法的适用场景：- 问题可以分解成若干个规模较小的、与原问题相似的子问题。- 子问题之间是相互独立的，没有重叠。- 子问题的解可以合并成原问题的解。常见的分治算法有：归并排序、快速排序、二分查找、大整数乘法、矩阵乘法（Strassen算法）、最近点对问题、汉诺塔问题等等。递归和分治，是非常重要的编程技巧和算法思想。很多高级的算法，都是基于递归和分治的。所以，一定要深入理解递归和分治的本质，熟练运用递归和分治来解决问题。## 5.4 贪心算法：每一步都选择最优接下来是贪心算法。贪心算法是一种简单但有效的算法思想。它的核心思想是：在每一步都选择当前看起来最优的选择，也就是局部最优，希望通过每一步的局部最优，最终得到全局最优。贪心算法的特点是：第一，简单。贪心算法的思路很简单，就是每一步都选最好的，不需要考虑全局，不需要回溯，不需要动态规划那样的状态转移。第二，高效。贪心算法的时间复杂度一般都比较低，因为它只需要做局部的最优选择，不需要遍历所有的可能性。第三，不一定能得到全局最优解。因为贪心算法只考虑局部最优，不考虑全局，所以有时候局部最优的选择，反而会导致全局不是最优的。所以，贪心算法不是对所有问题都适用的。那么，什么样的问题适合用贪心算法呢？一般来说，适合用贪心算法的问题，需要满足两个条件：第一，最优子结构：问题的最优解，包含子问题的最优解。也就是说，问题可以分解成子问题，问题的最优解可以由子问题的最优解构造出来。第二，贪心选择性质：问题的全局最优解，可以通过一系列的局部最优选择来得到。也就是说，每一步做局部最优的选择，最终能得到全局最优解。这两个条件中，第二个条件是关键，也是贪心算法和动态规划的区别所在。动态规划考虑了所有的可能性，能保证得到全局最优解；而贪心算法只考虑局部最优，只有满足贪心选择性质的时候，才能得到全局最优解。举个经典的贪心例子：活动选择问题。有n个活动，每个活动都有一个开始时间和结束时间。你要选择尽可能多的活动，使得选中的活动之间不冲突（一个活动结束后，另一个才能开始）。这个问题，用贪心算法怎么解决？贪心策略是：每次都选择结束时间最早的活动。因为结束时间越早，剩下的时间就越多，就能安排更多的活动。具体步骤是：1. 把所有活动按照结束时间从小到大排序。2. 选择第一个活动（结束时间最早的）。3. 然后，依次遍历剩下的活动，如果当前活动的开始时间大于等于上一个选中活动的结束时间，就选中这个活动。4. 最后，选中的活动就是最多的不冲突活动。这个贪心策略，是能得到全局最优解的。因为每次选择结束时间最早的活动，能给剩下的活动留下最多的时间，从而能安排最多的活动。再举一个经典的贪心例子：零钱找零问题。你要找给顾客n元钱，有面值为1元、5元、10元、20元、50元、100元的纸币，每种纸币的数量足够多。请问，最少需要多少张纸币？这个问题，用贪心算法怎么解决？贪心策略是：每次都选择面值最大的纸币。因为面值越大，需要的纸币数量就越少。具体步骤是：1. 先选尽可能多的100元纸币。2. 剩下的钱，再选尽可能多的50元纸币。3. 剩下的钱，再选尽可能多的20元纸币。4. 以此类推，直到钱找完。对于人民币的面值来说，这个贪心策略是能得到全局最优解的。因为人民币的面值设计，满足贪心选择性质。但是，并不是所有的面值设计，都满足贪心选择性质。比如，如果面值是1元、3元、4元，要找6元钱。用贪心算法，先选4元，再选1元、1元，一共3张。但是最优解是选两个3元，一共2张。所以，这时候贪心算法就得不到全局最优解了。所以，使用贪心算法的时候，一定要先证明问题满足贪心选择性质，否则可能得不到全局最优解。常见的贪心算法应用场景：- 活动选择问题- 区间调度问题- 零钱找零问题- 哈夫曼编码- 最小生成树（Prim算法、Kruskal算法）- 最短路径（Dijkstra算法）- 任务调度- 负载均衡贪心算法是一种简单但有效的算法思想。虽然不是对所有问题都适用，但是对于满足贪心选择性质的问题，贪心算法是最高效、最简单的解法。所以，一定要理解贪心算法的本质，知道什么问题适合用贪心算法，什么问题不适合。## 5.5 动态规划：算法中的"大boss"接下来是动态规划。动态规划（Dynamic Programming，简称DP），是算法中的重点和难点，也是面试中最常考的算法之一。很多人觉得动态规划很难，其实只要掌握了方法，动态规划也没有那么难。什么是动态规划？动态规划是一种通过把原问题分解为相对简单的子问题的方式，来求解复杂问题的方法。动态规划和分治有点像，都是把大问题拆成小问题。但是，它们有一个关键的区别：分治的子问题是相互独立的，没有重叠；而动态规划的子问题是有重叠的，也就是说，不同的子问题，可能有公共的子子问题。如果用分治的方法来解决有重叠子问题的问题，就会重复计算很多子问题，效率很低。而动态规划，会把已经计算过的子问题的解保存下来，下次需要的时候直接用，不需要重复计算，从而大大提高了效率。动态规划的核心思想，可以概括为一句话："记住你已经做过的事情。"动态规划问题，一般有三个要素：第一，状态定义：用一个状态来表示问题的某个阶段。比如，dp[i]表示前i个元素的最优解，dp[i][j]表示前i个元素中选j个的最优解。第二，状态转移方程：状态之间的转移关系。也就是，如何从子问题的解，推导出原问题的解。比如，dp[i] = max(dp[i-1], dp[i-2] + nums[i])。第三，初始化和遍历顺序：状态的初始值，以及状态的遍历顺序。初始化是为了让状态转移能进行下去；遍历顺序是为了保证在计算当前状态的时候，需要的子问题的解已经计算好了。动态规划的解题步骤，可以概括为四步：第一步，确定状态：明确问题的状态是什么，状态的含义是什么。第二步，推导状态转移方程：根据问题的逻辑，推导出状态之间的转移关系。第三步，确定初始化和遍历顺序：确定状态的初始值，以及状态的遍历顺序。第四步，返回结果：根据状态的定义，返回最终的结果。举个经典的动态规划例子：斐波那契数列。斐波那契数列的定义是：F(0) = 0，F(1) = 1，F(n) = F(n-1) + F(n-2)（n >= 2）。如果用递归的方法来计算F(n)，会有大量的重复计算，时间复杂度是O(2^n)，效率很低。用动态规划的方法来计算：- 状态定义：dp[i]表示斐波那契数列的第i个数。- 状态转移方程：dp[i] = dp[i-1] + dp[i-2]。- 初始化：dp[0] = 0，dp[1] = 1。- 遍历顺序：从2到n，从小到大遍历。- 返回结果：dp[n]。这样，时间复杂度就降到了O(n)，空间复杂度是O(n)。还可以进一步优化空间，因为dp[i]只依赖于dp[i-1]和dp[i-2]，所以不需要保存整个数组，只需要保存前两个值就行了，空间复杂度可以降到O(1)。再举一个经典的动态规划例子：爬楼梯问题。你要爬一个n阶的楼梯，每次可以爬1阶或者2阶，请问有多少种不同的方法可以爬到楼顶？用动态规划的方法来解决：- 状态定义：dp[i]表示爬到第i阶楼梯的方法数。- 状态转移方程：要爬到第i阶楼梯，要么是从第i-1阶爬1阶上来的，要么是从第i-2阶爬2阶上来的。所以，dp[i] = dp[i-1] + dp[i-2]。- 初始化：dp[1] = 1（爬1阶只有1种方法），dp[2] = 2（爬2阶有2种方法：1+1或者2）。- 遍历顺序：从3到n，从小到大遍历。- 返回结果：dp[n]。你看，这个问题的状态转移方程，和斐波那契数列是一样的。所以，很多动态规划问题，本质上都是相似的，掌握了方法，就能举一反三。动态规划的常见类型：- 线性DP：状态是线性的，比如斐波那契数列、爬楼梯、最大子数组和、打家劫舍等。- 背包问题：0-1背包、完全背包、多重背包、分组背包等。- 区间DP：状态是一个区间，比如最长回文子序列、矩阵链乘法、石子合并等。- 树形DP：状态是树的节点，比如树的最大独立集、树的直径、树形背包等。- 状态压缩DP：用二进制来表示状态，比如旅行商问题、状态压缩DP等。- 数位DP：统计数字的各位数字满足某些条件的数的个数。动态规划是算法中的重点和难点，需要花大量的时间学习和练习。但是，只要掌握了方法，多做题，多总结，就能攻克动态规划。## 5.6 搜索算法：暴力出奇迹最后是搜索算法。搜索算法是一种通用的算法，用来在一个状态空间中，找到满足条件的解。很多问题，没有高效的算法，或者问题规模很小，就可以用搜索算法来暴力求解。搜索算法主要有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。先说说深度优先搜索（DFS）。深度优先搜索的原理是：从起始状态出发，沿着一条路径一直往下走，直到走到尽头，或者找到解；如果走到尽头还没找到解，就回溯到上一个节点，换一条路径继续走。直到遍历完所有的路径，或者找到解。深度优先搜索，就像你走迷宫。你从入口进去，遇到岔路口，就选一条路一直走，走到死胡同，就退回到上一个岔路口，换一条路继续走。直到找到出口，或者遍历完所有的路。深度优先搜索的实现方式，一般是递归，或者用栈。深度优先搜索的优点是：实现简单，代码简洁；空间复杂度低，只需要保存当前路径上的节点。缺点是：可能会走很多冤枉路，效率不高；如果状态空间很大，可能会超时；不一定能找到最优解（如果是求最短路径的话，DFS找到的不一定是最短的）。深度优先搜索的适用场景：- 状态空间不是很大的问题。- 需要遍历所有可能的解的问题。- 求所有解的问题。- 树的遍历、图的遍历。- 排列组合、子集、全排列等问题。- 回溯问题（N皇后、数独、解数独等）。再说说广度优先搜索（BFS）。广度优先搜索的原理是：从起始状态出发，先访问所有距离为1的状态，再访问所有距离为2的状态，再访问所有距离为3的状态，以此类推。直到找到解，或者遍历完所有的状态。广度优先搜索，就像你往水里扔一块石头，水波一圈一圈地往外扩散。先扩散到距离近的地方，再扩散到距离远的地方。广度优先搜索的实现方式，一般是用队列。广度优先搜索的优点是：能找到最短路径（如果每条边的权重都相同的话）；不会走冤枉路，效率比DFS高（在求最短路径的场景下）。缺点是：空间复杂度高，需要保存所有访问过的节点；实现比DFS稍微复杂一点。广度优先搜索的适用场景：- 求最短路径的问题（每条边的权重都相同）。- 求最少步数的问题。- 树的层序遍历、图的层序遍历。- 迷宫问题、最短路径问题。- 单词接龙、打开转盘锁等问题。除了DFS和BFS，还有一些高级的搜索算法，比如：- 双向BFS：从起点和终点同时开始BFS，相遇的时候就找到了最短路径。比单向BFS效率更高。- A算法：一种启发式搜索算法，在BFS的基础上，加入了启发函数，优先搜索更有可能找到解的路径。比BFS效率更高。- 迭代加深搜索：结合了DFS和BFS的优点，每次限制DFS的深度，逐步加深深度。空间复杂度低，又能找到最短路径。- 剪枝：在搜索的过程中，提前排除不可能的路径，减少搜索的空间。比如，可行性剪枝、最优性剪枝等。搜索算法是一种通用的算法，虽然有时候效率不高，但是很多问题都能用搜索算法来解决。特别是在面试中，很多问题如果一时想不到高效的算法，可以先用搜索算法暴力求解，然后再优化。所以，一定要熟练掌握DFS和BFS。—# 六、算法学习的资源与工具## 6.1 在线刷题平台讲完了核心的数据结构和算法，我们来聊聊算法学习的资源与工具。首先是在线刷题平台。学习算法，最重要的就是多刷题。在线刷题平台，提供了大量的算法题，并且可以在线提交代码，在线判题，非常方便。常见的在线刷题平台有：LeetCode（力扣）LeetCode是目前最流行的算法刷题平台，也是国内大厂面试最常用的平台。LeetCode的特点：- 题目数量多：有2000多道算法题，并且还在不断增加。- 题目质量高：题目都是精选的，很多都是大厂面试的真题。- 分类清晰：题目按照数据结构、算法、难度等分类，方便针对性练习。- 讨论区活跃：每道题都有讨论区，有很多大神分享解题思路和代码。- 模拟面试：有模拟面试功能，可以模拟真实的面试场景。- 周赛：每周都有周赛，可以和其他选手一起比赛，提升自己的算法水平。LeetCode有中文站（leetcode.cn）和英文站（leetcode.com），国内用户建议用中文站，访问速度快，界面是中文的。牛客网牛客网是国内的一个在线编程学习平台，除了算法题，还有很多其他的内容，比如笔试真题、面试经验、课程等。牛客网的特点：- 题目数量多：有大量的算法题，还有很多大厂的笔试真题。- 笔试真题：收录了很多大厂的笔试真题，可以在线模拟笔试。- 面试经验：有很多面试经验分享，可以了解大厂的面试流程和面试题。- 课程：有很多算法、编程的课程，适合系统学习。- 讨论区活跃：有很多用户分享解题思路和面试经验。牛客网适合准备校招的同学，因为有很多大厂的笔试真题和面试经验。CodeforcesCodeforces是一个俄罗斯的在线竞赛平台，以算法竞赛为主。Codeforces的特点：- 题目质量高：题目都是算法竞赛的题目，质量很高，有一定的难度。- 比赛频繁：每周都有比赛，比赛类型多样，有Div1、Div2、Div3、Educational等。- rating系统：有rating系统，可以和全世界的选手一起排名。- 讨论区活跃：每道题都有题解和讨论，有很多大神分享解题思路。- 题目难度跨度大：从简单题到很难的题都有，适合各个水平的选手。Codeforces适合有一定算法基础，想提升算法水平，或者想参加算法竞赛的同学。其他平台除了上面三个平台，还有一些其他的在线刷题平台，比如：- 洛谷：国内的算法竞赛平台，适合OI选手。- POJ：北京大学的在线评测系统，经典题目很多。- HDU：杭州电子科技大学的在线评测系统，题目很多。- AtCoder：日本的算法竞赛平台，比赛质量很高。- HackerRank：国外的在线编程平台，题目很多，分类清晰。- TopCoder：老牌的算法竞赛平台，比赛质量很高。## 6.2 经典书籍除了在线刷题平台，经典书籍也是学习算法的重要资源。常见的算法经典书籍有：《算法（第4版）》作者是Robert Sedgewick和Kevin Wayne。这本书是算法领域的经典教材，内容全面，讲解详细，配有大量的插图和示例代码（Java语言）。适合系统学习算法的同学。《算法导论（原书第3版）》作者是Thomas H. Cormen等。这本书是算法领域的"圣经"，内容非常全面，理论性很强，数学推导很详细。适合有一定基础，想深入学习算法理论的同学。但是，这本书比较难，不适合初学者。《数据结构与算法分析》有C语言版、Java语言版、C++语言版等多个版本，作者是Mark Allen Weiss。这本书讲解了数据结构和算法分析的基础知识，内容适中，难度适中，适合初学者学习数据结构和算法。《剑指Offer》作者是何海涛。这本书收录了很多典型的编程面试题，每道题都有详细的解题思路和代码。适合准备面试的同学，很多大厂的面试题都出自这本书。《编程之美》作者是《编程之美》小组。这本书收集了很多有趣的编程题，题目都来自微软的面试，解题思路很巧妙，能锻炼思维能力。适合想提升思维能力，或者准备微软面试的同学。《算法竞赛入门经典》作者是刘汝佳。这本书是算法竞赛的入门教材，内容全面，讲解详细，适合想参加算法竞赛的同学。《挑战程序设计竞赛》作者是秋叶拓哉等。这本书是算法竞赛的经典教材，内容全面，难度适中，适合有一定基础，想提升算法竞赛水平的同学。## 6.3 视频课程除了书籍，视频课程也是学习算法的重要资源。视频课程的好处是，有老师讲解，比自己看书更容易理解。常见的算法视频课程有：- 慕课网：有很多算法、数据结构的课程，质量不错。- 极客时间：有很多算法、数据结构的专栏，比如《数据结构与算法之美》，讲得很好。- B站：有很多免费的算法、数据结构的视频，比如天勤公开课、王道考研等，质量都不错。- Coursera：有很多国外大学的算法课程，比如普林斯顿大学的《算法》课程，质量很高。- edX：和Coursera类似，有很多国外大学的算法课程。## 6.4 学习工具除了学习资源，还有一些工具，能帮助你更好地学习算法。常见的算法学习工具有：- VisuAlgo：一个算法可视化的网站，能把各种算法的执行过程可视化，帮助理解算法的原理。- Algorithm Visualizer：另一个算法可视化的网站，支持自定义代码，可视化执行过程。- LeetCode插件：比如VS Code的LeetCode插件，可以在VS Code中直接刷题，非常方便。- 思维导图工具：比如XMind、MindMaster等，可以用来整理算法的知识体系，建立知识框架。- 笔记工具：比如Notion、Obsidian、印象笔记等，可以用来记录解题思路、错题、总结等。—# 七、算法面试的技巧与注意事项## 7.1 面试前的准备讲完了学习资源，我们来聊聊算法面试的技巧与注意事项。首先是面试前的准备。算法面试，准备是非常重要的。只要准备充分，算法面试其实并不难。面试前的准备，主要包括以下几个方面：第一，刷够题目。算法面试，最基础的就是刷题。题目刷够了，面试的时候遇到类似的题目，就能很快做出来。那么，刷多少题才算够呢？一般来说，刷300-500道题，就足够应对大部分的算法面试了。当然，不是刷得越多越好，关键是要刷精，每道题都要理解，都要掌握，而不是囫囵吞枣，刷完就忘。刷题的时候，要注意分类刷，按照数据结构和算法的类型来刷，比如数组、链表、栈、队列、哈希表、树、图、排序、查找、递归、分治、贪心、动态规划、搜索等等。每个类型，都要刷一定数量的题目，掌握这个类型的常见解法和模板。第二，总结归纳。刷题的时候，要多总结，多归纳。把相似的题目归为一类，总结出这类题目的通用解法和算法模板。比如，动态规划的题目，可以分为背包问题、打家劫舍问题、股票问题、子序列问题等等。每一类问题，都有自己的特点和通用解法。总结出来，遇到新的题目，就能快速判断属于哪一类，然后用对应的通用解法。第三，模拟面试。面试前，最好多做几次模拟面试，熟悉面试的流程和节奏。可以找朋友互相模拟面试，一个人当面试官，一个人当候选人，然后交换。也可以用LeetCode的模拟面试功能，或者参加一些模拟面试的活动。模拟面试的时候，要注意：要像真实面试一样，有时间限制，要边写代码边讲解思路，要注意沟通。第四，复习错题。面试前，要把之前做错的题目，或者不熟悉的题目，再复习一遍。确保这些题目，面试的时候再遇到，能做出来。很多人刷题，刷完就忘，之前做错的题目，过一段时间再做，还是会错。所以，一定要定期复习错题，确保真正掌握了。## 7.2 面试中的技巧面试中的技巧也很重要。有时候，题目你会做，但是因为面试技巧不好，也可能面试不通过。面试中的技巧，主要包括以下几个方面：第一，先沟通，再动手。拿到题目之后，不要急着写代码，先和面试官沟通，确认题目的要求、边界条件、输入输出格式等等。比如，题目说"给定一个数组"，你要问清楚：数组的长度范围是多少？数组的元素是整数还是浮点数？有没有重复元素？有没有负数？数组是不是有序的？等等。沟通清楚了，再动手写代码，避免因为理解错了题目，而写了错误的代码。第二，先讲思路，再写代码。写代码之前，先把你的解题思路讲给面试官听，让面试官知道你的想法。讲思路的时候，要注意：先讲暴力解法，再讲优化解法；讲清楚时间复杂度和空间复杂度；讲清楚为什么这么做，逻辑是什么。如果面试官觉得你的思路有问题，或者有更好的解法，会提示你，你可以及时调整。如果面试官觉得你的思路没问题，你就可以开始写代码了。第三，写代码的时候，要注意规范。写代码的时候，要注意代码规范：变量名要有意义，函数名要有意义，要有注释，要有缩进，代码结构要清晰。不要写得太潦草，不要用单字母的变量名（除了循环变量i、j、k），不要写没有注释的复杂逻辑。面试官看你的代码，首先看的是代码规范。如果代码写得很规范，面试官会觉得你是一个专业的程序员，印象分就会高很多。第四，写完代码之后，要测试。写完代码之后，不要马上说"写完了"，要自己先测试一下。可以用几个测试用例，手动运行一下你的代码，看看有没有问题。比如，正常的测试用例、边界测试用例、特殊测试用例等等。如果发现问题，及时修改。如果没有问题，再告诉面试官"写完了"，并且把测试的过程和结果讲给面试官听。第五，遇到不会的题目，不要慌。面试的时候，可能会遇到你不会的题目。这时候，不要慌，不要放弃。可以先讲一下你的思路，哪怕是暴力解法，也可以讲。然后，看看能不能优化。如果实在不会，可以请面试官给一点提示。很多时候，面试官看的不是你能不能做出来，而是你的思考过程，你解决问题的能力。只要你思路清晰，逻辑严谨，哪怕最后没有做出来，也可能通过面试。## 7.3 面试后的复盘面试结束之后，要及时复盘。复盘的内容包括：- 面试考了哪些题目？这些题目你会不会做？- 哪些题目你做出来了？哪些题目你没做出来？- 没做出来的题目，是因为什么？是知识点没掌握？还是思路不对？还是紧张了？- 面试中有哪些做得好的地方？有哪些做得不好的地方？- 下次面试，需要改进哪些地方？通过复盘，你能发现自己的不足，然后针对性地改进。这样，每次面试之后，你都能有所提升。而且，面试的题目，很多都是重复的。这次面试遇到的题目，下次面试可能还会遇到。所以，面试之后，一定要把面试的题目搞懂，确保下次再遇到，能做出来。—# 八、写在最后：算法是程序员的基本功写到这里，这篇文章也接近尾声了。让我来总结一下。数据结构与算法，是程序员的"内功心法"，是程序员的基本功。不管你是做前端、后端、移动端、还是数据科学，不管你是刚入门的新手，还是已经工作多年的老手，都应该好好学习数据结构与算法。学习数据结构与算法，要循序渐进，分阶段学习——入门阶段、进阶阶段、精通阶段。要按照正确的顺序学习，从易到难，从基础到高级。要有好的学习方法——理解为主，不要死记硬背；多动手写，不要只看不练；多总结，多归纳；循序渐进，不要急于求成；学以致用，在实际项目中运用。核心的数据结构包括：数组、链表、栈、队列、哈希表、树、图等等。核心的算法包括：排序、查找、递归与分治、贪心、动态规划、搜索等等。这些都是必须掌握的内容。学习算法，有很多好的资源和工具——在线刷题平台（LeetCode、牛客网、Codeforces等）、经典书籍（《算法》、《算法导论》、《剑指Offer》等）、视频课程、学习工具等等。算法面试，有很多技巧——面试前要充分准备（刷够题目、总结归纳、模拟面试、复习错题）；面试中要注意技巧（先沟通再动手、先讲思路再写代码、写代码注意规范、写完代码要测试、遇到不会的不要慌）；面试后要及时复盘。最后，我想和大家说：算法学习，是一个长期的过程，不是一蹴而就的。不要指望学一个月、两个月就能成为算法大神。需要长期的积累和练习，每天刷几道题，日积月累，时间长了，算法能力自然就提升了。也不要觉得算法很难，学不会。其实，算法没有那么难，只要你掌握了正确的方法，多练习，多总结，就能学好。很多人觉得算法难，是因为没有掌握方法，或者练习不够。算法是程序员的基本功，是面试的敲门砖，是提升编程能力的必经之路。希望大家都能重视算法，好好学习算法，把算法基础打扎实，成为一个优秀的程序员。希望这篇文章，能帮你更好地学习数据结构与算法，帮你在算法的道路上走得更远、更稳。谢谢大家！—（全文完）