1. 什么是大O符号与时间复杂度？
大O符号主要用来描述算法的复杂度，表示当输入规模越来越大时，算法的时间或者空间消耗是怎么增长的。我们通常更关注增长趋势，而不是具体运行了多少毫秒。
- 遍历一个长度为
n的数组，需要把每个元素看一遍，时间复杂度是 O(n)； - 每次都把问题规模缩小一半，比如二分查找，那么复杂度就是 O(log n)。
一般来说，O(1)、O(log n)、O(n) 比 O(n log n)、O(n²) 更高效。
2. 线性存储和链式存储有什么区别？
线性存储一般把逻辑上相邻的数据放在连续的内存空间中，典型的就是数组。它最大的优点是可以通过下标直接访问元素，随机访问效率很高，但如果中间插入或者删除元素，后面的元素可能都需要移动。
链式存储不要求节点在内存中连续存放，而是通过指针把一个个节点连接起来。它插入和删除节点比较方便，但如果想访问第 i 个元素，通常需要从头节点一个一个往后找，所以随机访问效率比较低。
[!TIP] 可以简单理解成：数组适合查找，链表更适合频繁插入和删除。
3. 栈和队列有什么区别？
栈和队列都是线性数据结构，但它们处理数据的顺序不同。
- 栈是后进先出（LIFO），也就是最后进入的数据最先出来，比如叠盘子，最后放上去的盘子最先拿走。栈主要有入栈和出栈操作。
- 队列是先进先出（FIFO），就像现实中的排队，先进入队列的人先出去。队列主要有入队和出队操作。
实际应用中：
- 栈经常用于函数调用、括号匹配、DFS 等；
- 队列经常用于任务调度、消息处理、BFS 等。
4. 什么是堆？什么是大顶堆和小顶堆？
堆是一种特殊的完全二叉树，它需要满足一定的堆序关系。
- 大顶堆：每个节点都不小于自己的子节点，所以堆顶一定是整个堆中的最大值；
- 小顶堆：每个节点都不大于自己的子节点，堆顶是最小值。
堆通常使用数组来实现，因为完全二叉树非常适合用数组表示。对于下标为 i 的节点，它的左右孩子可以通过下标计算出来：
- 左孩子：
2 * i + 1 - 右孩子：
2 * i + 2
堆的一个重要应用就是优先队列。比如每次都要快速取出当前最大的任务，就可以使用大顶堆；如果要维护最小的几个元素，就可以使用小顶堆。
5. 什么是哈希表？如何解决哈希冲突？
哈希表是一种通过哈希函数建立"数据 → 存储位置"映射的数据结构。理想情况下，我们可以根据一个数据直接计算出它应该存放的位置，因此查找、插入和删除的平均时间复杂度都可以达到 O(1)。
问题在于，不同的数据经过哈希函数之后可能得到相同的位置，这就是哈希冲突。
常见的解决方法有两种：
- 链地址法：一个位置对应一个链表或者其他结构，发生冲突的数据放到同一个链表中；
- 开放地址法：发生冲突后继续寻找其他空的位置，比如线性探测。
[!TIP] 哈希表的核心其实就是：通过哈希函数快速定位，通过冲突解决机制处理不同数据映射到同一个位置的问题。
6. 如何判断链表是否存在环？
最经典的方法是快慢指针。
设置两个指针，慢指针每次走一步，快指针每次走两步：
- 如果链表没有环，快指针最终会走到
None； - 如果链表存在环，快指针进入环以后会不断追赶慢指针，最终两者一定会相遇。
它的时间复杂度是 O(n)，额外空间复杂度是 O(1)。
[!TIP] 这个算法的核心思想其实就是：两个速度不同的人在一个环形跑道上跑步，快的人最终一定会追上慢的人。
7. 二分查找和线性查找有什么区别？
线性查找就是从头到尾逐个比较，如果数据有 n 个，最坏情况下需要比较 n 次，所以时间复杂度是 O(n)。
二分查找利用数据已经有序这一条件，每次取中间元素进行比较：
- 目标比中间值小，就去左边继续找；
- 目标比中间值大，就去右边找。
这样每次都能排除一半的数据，因此时间复杂度是 O(log n)。
[!TIP] 二分查找快的关键不是"查找方式更高级"，而是利用有序性，每次排除一半的搜索空间。
8. 常见排序算法有哪些？有什么区别？
常见排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。
从时间复杂度来看：
- 冒泡、选择、插入排序：通常是 O(n²)；
- 快速排序：平均 O(n log n)，最坏 O(n²)；
- 归并排序：O(n log n)；
- 堆排序：O(n log n)。
另外还有一个面试中经常问的概念叫稳定性：如果两个元素的值相同，排序后它们原来的相对顺序仍然保持不变，就叫稳定排序。比如归并排序是稳定的，而快速排序通常是不稳定的。
[!TIP] 比较排序算法时，不仅要看时间复杂度，还要看空间复杂度、稳定性以及适用场景。
9. DFS 和 BFS 有什么区别？
- DFS（深度优先搜索）：沿着一条路径不断向下搜索，直到走不下去之后再回退。它通常通过递归或者栈实现。
- BFS（广度优先搜索）：不会一直往一个方向走，而是先把当前节点的所有邻居访问完，再继续访问下一层，所以通常使用队列实现。
比如在一棵树中：
- DFS：先走左边，一直走到底，再回来；
- BFS：先访问第一层，再访问第二层，再访问第三层。
[!TIP] 如果要求无权图中某个节点到其他节点的最短距离，BFS 通常比较合适，因为它是按照距离一层一层搜索的。
10. 堆和栈有什么区别？
注意：这里说的是内存中的堆和栈，和前面讲的数据结构中的"堆"不是一个概念。
- 栈主要用来保存函数调用过程中产生的数据，比如局部变量、函数参数等。它由系统自动管理，分配和释放速度比较快，但是空间相对有限。
- 堆主要用于程序运行过程中动态申请的内存，比如使用
new或者malloc分配的空间。它的空间通常更大，但是需要程序进行管理。
[!TIP] 可以简单理解为：栈主要服务于函数调用，堆主要服务于动态内存分配。
11. 什么是图？图有哪些表示和遍历方式？
图是一种用来表示对象之间关系的数据结构，由顶点和边组成。
比如社交网络中，人可以看成顶点，两个人之间的好友关系可以看成边。根据边有没有方向，还可以分成有向图和无向图。
- 常见的存储方式：邻接矩阵、邻接表；
- 常见的遍历方法：DFS、BFS。
图的应用非常广，比如网络拓扑、社交网络、地图导航、任务依赖等。
留言板