基础结构

数组和链表区别是什么？

一句话理解

数组像“一排连续座位”，可以直接按座位号找到人；链表像“一群人每个人手里拿着下一个人的地址”，想找第几个通常要从第一个一路问过去。

核心区别

数组的元素在内存里是连续存放的。

比如：

arr[0] arr[1] arr[2] arr[3]

它们挨在一起，所以如果知道 arr[0] 的地址，就可以直接算出 arr[3] 的地址：

arr[3] 地址 = 数组起始地址 + 3 * 每个元素大小

所以数组支持快速随机访问，访问 arr[i] 的时间复杂度是 O(1)。

链表的元素不是连续存放的。链表由一个个节点组成，每个节点里通常有两部分：

数据 data + 指向下一个节点的指针 next

所以链表想访问第 5 个元素，通常不能直接跳过去，而是：

head -> 第1个 -> 第2个 -> 第3个 -> 第4个 -> 第5个

因此链表访问第 i 个元素通常是 O(n)。

查询区别

数组查询快。

因为数组可以通过下标直接定位：

#include <iostream> // 引入输入输出库，用来打印结果
using namespace std; // 使用标准命名空间，避免每次写 std::

int main() // 程序入口函数
{ // main 函数开始
    int arr[4] = {10, 20, 30, 40}; // 定义一个长度为 4 的数组，元素在内存中连续存放
    cout << arr[2] << endl; // 直接通过下标访问第三个元素，时间复杂度是 O(1)
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

链表查询慢。

因为链表没有下标定位能力，想找某个位置通常要从头节点开始走：

#include <iostream> // 引入输入输出库，用来打印结果
using namespace std; // 使用标准命名空间，避免每次写 std::

struct Node // 定义链表节点结构体
{ // Node 结构体开始
    int value; // 节点中保存的数据
    Node* next; // 指向下一个节点的指针
}; // Node 结构体结束

int main() // 程序入口函数
{ // main 函数开始
    Node a{10, nullptr}; // 创建第一个节点，值是 10，暂时没有下一个节点
    Node b{20, nullptr}; // 创建第二个节点，值是 20，暂时没有下一个节点
    Node c{30, nullptr}; // 创建第三个节点，值是 30，暂时没有下一个节点
    a.next = &b; // 让第一个节点指向第二个节点
    b.next = &c; // 让第二个节点指向第三个节点
    Node* current = &a; // 从头节点开始遍历链表
    while (current != nullptr) // 只要当前节点不是空，就继续遍历
    { // while 循环开始
        cout << current->value << endl; // 打印当前节点保存的数据
        current = current->next; // 移动到下一个节点
    } // while 循环结束
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

插入和删除区别

数组中间插入、删除比较慢。

比如数组是：

10 20 30 40 50

你想在 20 后面插入 25，后面的 30 40 50 都要往后挪。

所以数组中间插入通常是 O(n)。

链表插入、删除本身很快。

如果你已经拿到了要插入位置的节点，只需要改指针：

A -> B -> C

插入 X 后：

A -> B -> X -> C

链表插入节点的关键不是搬数据，而是改指针。

#include <iostream> // 引入输入输出库，用来打印结果
using namespace std; // 使用标准命名空间，避免每次写 std::

struct Node // 定义链表节点结构体
{ // Node 结构体开始
    int value; // 节点保存的数据
    Node* next; // 指向下一个节点的指针
}; // Node 结构体结束

int main() // 程序入口函数
{ // main 函数开始
    Node a{10, nullptr}; // 创建节点 a，值是 10
    Node b{20, nullptr}; // 创建节点 b，值是 20
    Node x{15, nullptr}; // 创建要插入的新节点 x，值是 15
    a.next = &b; // 原本 a 指向 b
    x.next = a.next; // 让 x 先指向原本 a 后面的节点，也就是 b
    a.next = &x; // 再让 a 指向 x，完成插入
    cout << a.value << " -> " << a.next->value << " -> " << a.next->next->value << endl; // 打印插入后的链表顺序
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

性能对比

对比点	数组	链表
内存布局	连续	不连续
随机访问	快，O(1)	慢，O(n)
中间插入	慢，要移动元素	找到位置后快
中间删除	慢，要移动元素	找到位置后快
内存开销	小，只存数据	大，要额外存指针
CPU 缓存	友好	不太友好
适合场景	查询多、遍历多、数据紧凑	插入删除频繁、节点数量变化大

为什么数组缓存更友好

CPU 读取内存时，通常不是只拿一个整数，而是会顺手把附近的一段内存也加载进缓存。

数组是连续的，所以访问 `arr[0]` 后，`arr[1]`、`arr[2]` 很可能也已经在缓存里了。

链表节点可能散落在内存各处，访问下一个节点时可能又要跳到另一个地址，CPU 缓存命中率更差。

这也是为什么在游戏开发里，很多时候即使链表插入删除理论上快，实际性能也不一定比数组好。

什么时候用数组

数据数量相对稳定。

经常通过下标访问。

经常完整遍历。

追求缓存友好和高性能。

例如：角色列表、子弹数组、组件数组、地图格子、排行榜数据。

什么时候用链表

频繁在中间插入和删除。

不太需要随机访问。

已经能快速拿到要插入/删除的位置。

例如：某些 LRU 缓存、任务队列节点、需要频繁摘除节点的数据结构。

不过在游戏客户端里，链表用得通常没有数组、`vector`、`List<T>` 那么多，因为链表对 CPU 缓存不友好。

面试高分回答

NOTE

数组和链表最大的区别是内存布局。数组使用连续内存，所以可以通过下标直接计算地址，随机访问是 O(1)，而且缓存友好，遍历性能通常很好。但数组在中间插入或删除元素时，需要移动后面的元素，所以是 O(n)。

链表由节点组成，每个节点保存数据和指向下一个节点的指针，节点在内存中不要求连续。链表随机访问慢，因为要从头节点一步步遍历，通常是 O(n)；但如果已经拿到了目标位置，插入和删除只需要修改指针，操作本身可以是 O(1)。缺点是额外指针开销更大，并且缓存命中率差。游戏开发里如果追求遍历性能和数据局部性，数组或连续容器通常更常用。

栈和队列适合什么场景？

一句话理解

栈适合处理“最近发生的事情”，队列适合处理“最早来的事情”。

栈的特点是：后进先出，英文叫 LIFO，也就是 Last In First Out。

你可以把它想成叠盘子：

最后放上去的盘子，最先被拿走。

栈常见操作：

操作	含义
push	入栈，把东西放到栈顶
pop	出栈，把栈顶的东西拿走
top	查看栈顶元素
empty	判断栈是否为空

栈适合什么场景

栈适合“回退型问题”。

比如：

撤销操作：你刚刚画了一笔，按 `Ctrl + Z`，应该撤销最近那一笔。

函数调用：函数 A 调用函数 B，函数 B 调用函数 C，返回时一定是 C 先返回，再 B 返回，再 A 返回。

递归：递归本质上依赖调用栈。

括号匹配：遇到左括号入栈，遇到右括号就和栈顶匹配。

深度优先搜索 DFS：先沿着一条路走到底，走不通再回退。

UI 页面返回：打开页面 A，再打开页面 B，再打开页面 C，返回时应该先回到 B。

游戏状态回退：例如编辑器里的撤销、技能释放步骤回滚、行为树路径回退。

栈代码示例：撤销操作

#include <iostream> // 引入输入输出库，用来打印信息
#include <stack> // 引入 stack 容器，用来模拟撤销栈
#include <string> // 引入 string 类型，用来保存操作名称
using namespace std; // 使用标准命名空间，避免每次写 std::

int main() // 程序入口函数
{ // main 函数开始
    stack<string> undoStack; // 创建一个字符串栈，用来保存玩家最近做过的操作
    undoStack.push("移动角色"); // 把“移动角色”这个操作压入栈中
    undoStack.push("释放技能"); // 把“释放技能”这个操作压入栈中
    undoStack.push("打开背包"); // 把“打开背包”这个操作压入栈中
    cout << "撤销操作：" << undoStack.top() << endl; // 查看栈顶操作，也就是最近发生的“打开背包”
    undoStack.pop(); // 弹出栈顶操作，表示撤销“打开背包”
    cout << "下一个可撤销操作：" << undoStack.top() << endl; // 现在栈顶变成“释放技能”
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

队列是什么

队列的特点是：先进先出，英文叫 FIFO，也就是 First In First Out。

你可以把它想成排队：

先来的人，先被服务。

队列常见操作：

操作	含义
push / enqueue	入队，排到队尾
pop / dequeue	出队，从队头取出
front	查看队头元素
empty	判断队列是否为空

队列适合什么场景

队列适合“排队型问题”。

比如：

任务队列：谁先提交任务，谁先执行。

消息系统：谁先发消息，谁先处理。

网络包处理：先收到的数据包通常先处理。

生产者消费者模型：生产者把任务放进队列，消费者从队列取任务。

广度优先搜索 BFS：一层一层向外扩展。

资源加载请求：多个资源请求排队等待加载。

游戏事件队列：例如伤害事件、音效事件、UI 通知事件按顺序处理。

AI 请求队列：很多怪物同时请求寻路时，可以排队分批处理。

队列代码示例：任务排队处理

#include <iostream> // 引入输入输出库，用来打印任务信息
#include <queue> // 引入 queue 容器，用来保存等待处理的任务
#include <string> // 引入 string 类型，用来保存任务名称
using namespace std; // 使用标准命名空间，避免每次写 std::

int main() // 程序入口函数
{ // main 函数开始
    queue<string> taskQueue; // 创建一个任务队列，用来保存等待执行的任务
    taskQueue.push("加载角色模型"); // 第一个任务入队，排在最前面
    taskQueue.push("加载角色贴图"); // 第二个任务入队，排在第一个任务后面
    taskQueue.push("播放入场动画"); // 第三个任务入队，排在最后面
    while (!taskQueue.empty()) // 只要队列不为空，就继续处理任务
    { // while 循环开始
        cout << "处理任务：" << taskQueue.front() << endl; // 读取队头任务，也就是最早进入队列的任务
        taskQueue.pop(); // 移除队头任务，表示这个任务已经处理完了
    } // while 循环结束
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

怎么选择

如果你关心的是“最近加入的东西先处理”，用栈。

比如：撤销、回退、递归、DFS、函数调用、页面返回。

如果你关心的是“最早加入的东西先处理”，用队列。

比如：任务排队、消息分发、BFS、网络包处理、资源加载请求。

如果你关心的是“优先级高的先处理”，那就不是普通队列了，应该考虑 `priority_queue`，也就是优先队列。例如 A* 寻路、任务调度、技能优先级处理。

面试高分回答

NOTE

栈和队列都是线性数据结构，但处理顺序不同。栈是后进先出，适合处理回退类场景，比如函数调用栈、递归、撤销操作、括号匹配和 DFS。队列是先进先出，适合处理排队类场景，比如任务队列、消息队列、生产者消费者、网络包处理和 BFS。简单记忆就是：需要“回到最近一步”用栈，需要“按先来后到处理”用队列。

哈希表如何解决冲突？

一句话理解

哈希冲突就是：两个不同的 key 算出来的位置一样了。解决办法通常有三类：链地址法、开放寻址法、扩容再哈希。

先理解什么是冲突

哈希表的核心流程大概是：

key -> hash(key) -> 数组下标 -> 存到对应位置

比如哈希表有 8 个桶：

index = hash(key) % 8

如果：

18 % 8 = 2
26 % 8 = 2

那么 18 和 26 都想放到 bucket[2]，这就叫哈希冲突。

冲突不是异常，而是哈希表必须面对的正常情况。因为桶的数量是有限的，但可能存入的 key 是很多的。

方法一：链地址法

链地址法也叫 Separate Chaining。

它的做法是：每个桶后面挂一条链表，冲突的元素都放到同一个桶对应的链表里。

比如：

bucket[2] -> 18 -> 26 -> 34

查找 26 的时候：

先算出 26 应该在 bucket[2]
然后从 bucket[2] 的链表里一个个找

优点是实现比较直观，插入删除也比较容易。

缺点是如果冲突很多，某个桶后面的链表会很长，查找就会从接近 O(1) 退化到 O(n)。

链地址法代码示例

下面是一个非常简化版的哈希表，只演示“冲突后挂链表”的思想。

#include <iostream> // 引入输入输出库，用来打印结果
#include <vector> // 引入 vector 容器，用来表示哈希表的桶数组
#include <list> // 引入 list 容器，用来表示每个桶后面的链表
using namespace std; // 使用标准命名空间，避免每次写 std::

class HashTable // 定义一个简单的哈希表类
{ // HashTable 类开始
private: // private 表示下面成员只能在类内部访问
    vector<list<int>> buckets; // buckets 是桶数组，每个桶里面挂一条 int 链表
    int bucketCount; // bucketCount 表示桶的数量

    int Hash(int key) // 定义哈希函数，用 key 计算桶下标
    { // Hash 函数开始
        return key % bucketCount; // 用取模得到桶下标，例如 26 % 8 = 2
    } // Hash 函数结束

public: // public 表示下面成员可以被外部调用
    HashTable(int size) // 定义构造函数，用来初始化哈希表大小
    { // 构造函数开始
        bucketCount = size; // 保存桶数量
        buckets.resize(bucketCount); // 创建指定数量的桶
    } // 构造函数结束

    void Insert(int key) // 定义插入函数，把 key 放入哈希表
    { // Insert 函数开始
        int index = Hash(key); // 计算这个 key 应该放到哪个桶里
        buckets[index].push_back(key); // 把 key 插入到对应桶的链表末尾
    } // Insert 函数结束

    bool Find(int key) // 定义查找函数，判断 key 是否存在
    { // Find 函数开始
        int index = Hash(key); // 先算出 key 应该在哪个桶里
        for (int value : buckets[index]) // 遍历这个桶后面的链表
        { // for 循环开始
            if (value == key) // 如果当前节点的值等于要找的 key
            { // if 语句开始
                return true; // 找到了就返回 true
            } // if 语句结束
        } // for 循环结束
        return false; // 整条链表都没找到，就返回 false
    } // Find 函数结束
}; // HashTable 类结束

int main() // 程序入口函数
{ // main 函数开始
    HashTable table(8); // 创建一个有 8 个桶的哈希表
    table.Insert(18); // 插入 18，它会落到 bucket[2]
    table.Insert(26); // 插入 26，它也会落到 bucket[2]，所以发生冲突
    cout << table.Find(26) << endl; // 查找 26，找到会输出 1
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

方法二：开放寻址法

开放寻址法也叫 Open Addressing。

它的做法是：如果目标位置被占用了，就继续在数组里找下一个空位置。

比如 26 本来要放在 bucket[2]，但是 bucket[2] 已经有 18 了，那么就尝试：

bucket[3]
bucket[4]
bucket[5]
...

常见探测方式有：

方式	思想
线性探测	冲突后依次看下一个位置
二次探测	冲突后按平方距离跳着找
双重哈希	冲突后用第二个哈希函数决定跳多远

开放寻址法的优点是数据都在数组里，内存更连续，缓存友好。

缺点是删除比较麻烦，通常不能直接清空位置，否则可能破坏后续查找链路；而且表太满时，探测次数会明显增加。

方法三：扩容再哈希

哈希表不能无限往同一个小数组里塞元素。

当元素数量越来越多，负载因子变大，冲突就会越来越多。

负载因子可以简单理解为：

load factor = 元素数量 / 桶数量

比如：

8 个桶里放了 7 个元素，负载因子就是 7 / 8 = 0.875

这时候哈希表会变得比较拥挤，查询和插入都可能变慢。

所以很多哈希表会在负载因子超过某个阈值时扩容，比如从 8 个桶扩到 16 个桶，然后把旧元素重新计算下标，放进新表里。

这个过程叫 rehash，也就是重新哈希。

为什么扩容后要重新哈希

因为桶数量变了，取模结果也会变。

原来：

18 % 8 = 2
26 % 8 = 2

扩容到 16 个桶后：

18 % 16 = 2
26 % 16 = 10

它们可能就不会冲突了。

所以扩容不仅是“数组变大”，还要“所有元素重新找位置”。

面试中常见追问

哈希冲突能不能完全避免？

一般不能。只要 key 的数量可能大于桶数量，或者 hash 结果被映射到有限桶里，就可能冲突。好的哈希函数只能降低冲突概率，不能保证绝对没有冲突。

哈希表最坏复杂度是多少？

理想情况下插入、删除、查找接近 `O(1)`。但如果冲突严重，比如链地址法所有元素都挂到同一个桶里，最坏会退化到 `O(n)`。

为什么哈希表要关注负载因子？

因为负载因子越高，桶越拥挤，冲突越容易发生。负载因子过高时，哈希表通常会扩容，牺牲一次较大的 rehash 成本，换取后续操作继续接近 `O(1)`。

链地址法和开放寻址法怎么选？

链地址法实现简单，删除方便，对负载因子容忍度相对高。开放寻址法数据更连续，缓存友好，但删除和探测策略更复杂，表太满时性能下降明显。

面试高分回答

TIP

哈希表冲突指的是不同 key 经过哈希函数计算后映射到了同一个桶。常见解决方式有链地址法和开放寻址法。链地址法是在每个桶后面挂链表或其他结构，冲突元素都放在同一个桶的链上；开放寻址法是在数组内部继续探测下一个可用位置，比如线性探测、二次探测或双重哈希。另外，当负载因子过高时，哈希表通常会扩容并 rehash，把旧元素重新分布到更大的桶数组中，减少冲突。理想情况下哈希表查找接近 O(1)，但冲突严重时可能退化到 O(n)。

二叉树、二叉搜索树、平衡树区别是什么？

一句话理解

二叉树只规定“每个节点最多两个孩子”；二叉搜索树在二叉树基础上规定“左小右大”；平衡树在二叉搜索树基础上再规定“不能长得太歪”。

二叉树是什么

二叉树，英文叫 Binary Tree。

它的规则非常简单：

每个节点最多有两个子节点。

这两个子节点通常叫：

left：左孩子。

right：右孩子。

但是普通二叉树不要求左边比右边小，也不要求有序。

例如下面这样也是二叉树：

        A
       / \
      B   C
     / \
    D   E

它只是满足“每个节点最多两个孩子”。

所以普通二叉树更像是一种“树的形状规则”，不一定适合快速查找。

二叉搜索树是什么

二叉搜索树，英文叫 Binary Search Tree，简称 BST。

它首先是一棵二叉树，然后额外满足搜索规则：

左子树所有节点的值都小于当前节点。

右子树所有节点的值都大于当前节点。

左右子树本身也必须是二叉搜索树。

例如：

        8
       / \
      4   12
     / \
    2   6

这个树中：

`4` 在 `8` 左边，因为 `4 < 8`。

`12` 在 `8` 右边，因为 `12 > 8`。

`2` 在 `4` 左边，因为 `2 < 4`。

`6` 在 `4` 右边，因为 `6 > 4`。

所以它是二叉搜索树。

BST 为什么查找快

假设你要找 `6`：

先看根节点 `8`。

`6 < 8`，所以去左边找。

来到 `4`。

`6 > 4`，所以去右边找。

找到 `6`。

它每次比较都能排除一半左右的方向，所以如果树比较均匀，查找效率接近 `O(log n)`。

但是注意：这是树比较均匀的情况。

BST 的问题：可能退化成链表

如果插入顺序是：

1, 2, 3, 4, 5

普通 BST 可能长成这样：

1
 \
  2
   \
    3
     \
      4
       \
        5

这棵树虽然还是二叉搜索树，但它已经歪成链表了。

查找 5 时要一路往右找：

1 -> 2 -> 3 -> 4 -> 5

这时查找复杂度从 O(log n) 退化成 O(n)。

所以普通 BST 的问题是：平均可能很快，但最坏可能很慢。

平衡树是什么

平衡树通常指“自平衡二叉搜索树”。

它首先也是二叉搜索树，也满足“左小右大”。

但它还会尽量控制树的高度，不让树歪得太厉害。

常见平衡树包括：

`AVL Tree`：平衡要求更严格，查找很稳定。

`Red-Black Tree`：红黑树，平衡要求相对宽松，但插入删除综合性能好。

`Treap`：结合随机优先级和 BST 的结构。

C++ 里的 `std::map`、`std::set` 通常就是基于红黑树这类平衡搜索树实现的。

平衡树为什么快

树的查找速度主要取决于高度。

如果树高度很低：

查找路径短

如果树高度很高：

查找路径长

平衡树会通过旋转等操作，让树的高度保持在接近 log n 的级别。

所以平衡树的查找、插入、删除通常都是稳定的 O(log n)。

三者对比

类型	核心规则	是否有序	是否自动保持平衡	查找效率
二叉树	每个节点最多两个孩子	不一定	不保证	通常可能要遍历
二叉搜索树	左小右大	是	不保证	平均 O(log n)，最坏 O(n)
平衡树	左小右大 + 控制高度	是	是	通常稳定 O(log n)

BST 简单代码示例

下面代码演示的是普通二叉搜索树插入和查找，不包含平衡逻辑。

#include <iostream> // 引入输入输出库，用来打印结果
using namespace std; // 使用标准命名空间，避免每次写 std::

struct Node // 定义二叉搜索树节点结构体
{ // Node 结构体开始
    int value; // 保存当前节点的值
    Node* left; // 指向左孩子，左孩子的值应该更小
    Node* right; // 指向右孩子，右孩子的值应该更大
}; // Node 结构体结束

Node* CreateNode(int value) // 定义创建节点的函数
{ // CreateNode 函数开始
    Node* node = new Node(); // 在堆上创建一个新的节点
    node->value = value; // 把传入的值保存到节点里
    node->left = nullptr; // 新节点一开始没有左孩子
    node->right = nullptr; // 新节点一开始没有右孩子
    return node; // 返回新节点的地址
} // CreateNode 函数结束

Node* Insert(Node* root, int value) // 定义插入函数，把 value 插入到 BST 中
{ // Insert 函数开始
    if (root == nullptr) // 如果当前树是空的
    { // if 语句开始
        return CreateNode(value); // 创建新节点并作为当前子树的根节点返回
    } // if 语句结束
    if (value < root->value) // 如果要插入的值小于当前节点
    { // if 语句开始
        root->left = Insert(root->left, value); // 递归插入到左子树
    } // if 语句结束
    else if (value > root->value) // 如果要插入的值大于当前节点
    { // else if 语句开始
        root->right = Insert(root->right, value); // 递归插入到右子树
    } // else if 语句结束
    return root; // 返回当前子树的根节点
} // Insert 函数结束

bool Find(Node* root, int value) // 定义查找函数，判断 value 是否存在
{ // Find 函数开始
    if (root == nullptr) // 如果走到空节点
    { // if 语句开始
        return false; // 表示没有找到目标值
    } // if 语句结束
    if (value == root->value) // 如果目标值等于当前节点的值
    { // if 语句开始
        return true; // 表示找到了目标值
    } // if 语句结束
    if (value < root->value) // 如果目标值小于当前节点
    { // if 语句开始
        return Find(root->left, value); // 去左子树继续查找
    } // if 语句结束
    return Find(root->right, value); // 否则去右子树继续查找
} // Find 函数结束

int main() // 程序入口函数
{ // main 函数开始
    Node* root = nullptr; // 创建一棵空树
    root = Insert(root, 8); // 插入 8，作为根节点
    root = Insert(root, 4); // 插入 4，因为 4 小于 8，所以放到左边
    root = Insert(root, 12); // 插入 12，因为 12 大于 8，所以放到右边
    root = Insert(root, 6); // 插入 6，它会在 8 的左边、4 的右边
    cout << Find(root, 6) << endl; // 查找 6，找到会输出 1
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

面试高分回答

NOTE

二叉树是一种基础树结构，每个节点最多有两个孩子，但不要求节点之间有大小顺序。二叉搜索树是在二叉树基础上增加了有序性，满足左子树小于根节点、右子树大于根节点，因此查找时可以根据大小决定往左还是往右，平均复杂度接近 O(log n)。但普通 BST 如果插入顺序不好，可能退化成链表，最坏查找变成 O(n)。平衡树通常指自平衡二叉搜索树，比如 AVL 树和红黑树，它们通过旋转等操作控制树的高度，使查找、插入、删除都能稳定保持在 O(log n)。记忆方式是：二叉树管形状，BST 管顺序，平衡树管高度。

堆是什么？小根堆和大根堆区别是什么？

一句话理解

堆是一种“能快速拿到最大值或最小值”的树形数据结构。小根堆的堆顶是最小值，大根堆的堆顶是最大值。

先注意一个容易混淆的点

这里说的“堆”，是数据结构里的 Heap。

它不是内存管理里的“堆内存”。

面试里如果问：

栈和堆区别是什么？

那里的“堆”通常指内存区域。

如果问：

小根堆、大根堆、堆排序、优先队列

那里的“堆”通常指数据结构。

堆满足两个条件

第一个条件：它通常是一棵完全二叉树。

完全二叉树的意思是：从上到下、从左到右依次填满，中间不能乱空。

第二个条件：父节点和子节点之间满足大小规则。

小根堆：父节点小于等于子节点，所以根节点最小。

大根堆：父节点大于等于子节点，所以根节点最大。

小根堆是什么

小根堆也叫 Min Heap。

规则是：

父节点 <= 子节点

例如：

        1
       / \
      3   5
     / \ / \
    7  9 10 12

根节点是 1，它是整棵堆里最小的元素。

所以小根堆适合快速取最小值。

常见场景：

A* 寻路中取 `f` 值最小的节点。

Dijkstra 最短路中取当前距离最小的点。

定时器系统中取最近要触发的任务。

服务器任务调度中取最早到期的任务。

大根堆是什么

大根堆也叫 Max Heap。

规则是：

父节点 >= 子节点

例如：

        99
       /  \
      80   70
     / \   / \
    30 50 40 10

根节点是 99，它是整棵堆里最大的元素。

所以大根堆适合快速取最大值。

常见场景：

排行榜快速取最高分。

战斗系统里取最高优先级目标。

任务系统里取最高优先级任务。

数据流中维护当前最大值。

堆不是完全有序

这是零基础很容易误解的点。

堆只保证父子之间的大小关系，不保证整棵树从左到右有序。

比如小根堆只保证：

父节点 <= 子节点

但不保证左孩子一定小于右孩子。

所以堆不是排序数组。

堆只能保证：

小根堆的堆顶一定最小。

大根堆的堆顶一定最大。

如果你想找任意一个元素，堆不一定快，可能还是要 O(n) 遍历。

堆为什么常用数组实现

堆看起来是树，但通常不用指针节点实现，而是用数组实现。

因为堆是完全二叉树，没有中间空洞，所以数组非常适合存。

假设某个节点下标是 `i`：

左孩子下标是 `2 * i + 1`。

右孩子下标是 `2 * i + 2`。

父节点下标是 `(i - 1) / 2`。

比如数组：

[1, 3, 5, 7, 9, 10, 12]

可以表示成：

        1
       / \
      3   5
     / \ / \
    7  9 10 12

数组实现的好处是内存连续，缓存友好，也不用为每个节点额外存指针。

常见操作复杂度

操作	含义	复杂度
top	看堆顶最大/最小值	O(1)
push	插入一个元素	O(log n)
pop	删除堆顶元素	O(log n)
build heap	把数组建成堆	O(n)
查找任意元素	找某个指定值	O(n)

为什么插入和删除是 O(log n)？

因为堆的高度大约是 log n。

插入时，新元素先放到数组末尾，然后一路和父节点比较，必要时往上换位置，这叫“上浮”。

删除堆顶时，通常把最后一个元素拿到堆顶，然后一路和孩子比较，必要时往下换位置，这叫“下沉”。

C++ 代码示例：大根堆和小根堆

C++ 的 priority_queue 默认是大根堆。

#include <iostream> // 引入输入输出库，用来打印结果
#include <queue> // 引入 priority_queue，用来使用堆结构
#include <vector> // 引入 vector，因为小根堆写法里需要指定底层容器
#include <functional> // 引入 greater，用来把 priority_queue 改成小根堆
using namespace std; // 使用标准命名空间，避免每次写 std::

int main() // 程序入口函数
{ // main 函数开始
    priority_queue<int> maxHeap; // 创建大根堆，默认堆顶是最大值
    maxHeap.push(30); // 插入数字 30
    maxHeap.push(10); // 插入数字 10
    maxHeap.push(50); // 插入数字 50
    cout << maxHeap.top() << endl; // 输出堆顶元素，大根堆会输出最大值 50

    priority_queue<int, vector<int>, greater<int>> minHeap; // 创建小根堆，堆顶是最小值
    minHeap.push(30); // 插入数字 30
    minHeap.push(10); // 插入数字 10
    minHeap.push(50); // 插入数字 50
    cout << minHeap.top() << endl; // 输出堆顶元素，小根堆会输出最小值 10

    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

面试高分回答

WARNING

堆是一种通常用数组实现的完全二叉树结构，它不要求所有元素完全有序，只要求父节点和子节点满足某种大小关系。小根堆要求父节点小于等于子节点，所以堆顶是最小值；大根堆要求父节点大于等于子节点，所以堆顶是最大值。堆常用于优先队列，能在 O(1) 时间查看最大或最小元素，并在 O(log n) 时间完成插入和删除堆顶。需要注意的是，堆只能快速访问堆顶，查找任意元素并不快，通常还是 O(n)。

图如何存储？邻接矩阵和邻接表区别是什么？

一句话理解

图就是“点和点之间有连接关系”。邻接矩阵像一张“关系表”，邻接表像每个点自己的“好友列表”。

图是什么

图，英文叫 Graph。

它由两部分组成：

Vertex：顶点，也叫节点。

Edge：边，表示两个点之间有关系。

比如游戏里：

地图路点可以是顶点。

两个路点之间能走，就有一条边。

怪物寻路、导航网格、技能目标关系、任务依赖关系，都可以抽象成图。

图常见有哪些类型

无向图：A 能到 B，B 也能到 A。

A -- B

有向图：A 能到 B，但 B 不一定能到 A。

A -> B

无权图：只关心有没有连接。

A 和 B 相连

带权图：边上有代价。

A 到 B 的距离是 5

游戏寻路里经常是带权图，因为不同路段距离、消耗、危险程度可能不同。

邻接矩阵是什么

邻接矩阵就是用二维数组存图。

假设有 4 个点：

A, B, C, D

那就开一个 4 x 4 的二维数组：

matrix[i][j]

如果 i 和 j 相连，就存 1。

如果不相连，就存 0。

例如：

A-B 相连
A-C 相连
B-D 相连
C-D 相连

邻接矩阵可以写成：

    A B C D
A   0 1 1 0
B   1 0 0 1
C   1 0 0 1
D   0 1 1 0

看 A 和 B 是否相连，只要看：

matrix[A][B]

如果是 1，就说明相连。

所以邻接矩阵查“两个点之间有没有边”非常快，是 O(1)。

邻接矩阵代码示例

#include <iostream> // 引入输入输出库，用来打印结果
#include <vector> // 引入 vector 容器，用来创建二维数组
using namespace std; // 使用标准命名空间，避免每次写 std::

int main() // 程序入口函数
{ // main 函数开始
    int vertexCount = 4; // 定义顶点数量，0 表示 A，1 表示 B，2 表示 C，3 表示 D
    vector<vector<int>> matrix(vertexCount, vector<int>(vertexCount, 0)); // 创建 4x4 邻接矩阵，默认都不相连
    matrix[0][1] = 1; // 记录 A 和 B 相连
    matrix[1][0] = 1; // 无向图要反过来也记录 B 和 A 相连
    matrix[0][2] = 1; // 记录 A 和 C 相连
    matrix[2][0] = 1; // 无向图要反过来也记录 C 和 A 相连
    matrix[1][3] = 1; // 记录 B 和 D 相连
    matrix[3][1] = 1; // 无向图要反过来也记录 D 和 B 相连
    matrix[2][3] = 1; // 记录 C 和 D 相连
    matrix[3][2] = 1; // 无向图要反过来也记录 D 和 C 相连
    cout << matrix[0][1] << endl; // 查询 A 和 B 是否相连，输出 1 表示相连
    cout << matrix[0][3] << endl; // 查询 A 和 D 是否相连，输出 0 表示不相连
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

邻接表是什么

邻接表就是：每个点只记录自己直接相连的点。

还是刚才这张图：

A-B
A-C
B-D
C-D

邻接表可以写成：

A: B, C
B: A, D
C: A, D
D: B, C

它不需要存不存在的边。

所以如果点很多，但边很少，邻接表非常省空间。

例如 10000 个点，如果用邻接矩阵，要开：

10000 x 10000 = 100000000 个格子

哪怕大部分点之间没有连接，也要占空间。

但邻接表只存真实存在的边，边少的时候会节省很多内存。

邻接表代码示例

#include <iostream> // 引入输入输出库，用来打印结果
#include <vector> // 引入 vector 容器，用来保存每个点的邻居列表
using namespace std; // 使用标准命名空间，避免每次写 std::

int main() // 程序入口函数
{ // main 函数开始
    int vertexCount = 4; // 定义顶点数量，0 表示 A，1 表示 B，2 表示 C，3 表示 D
    vector<vector<int>> graph(vertexCount); // 创建邻接表，每个点对应一个邻居数组
    graph[0].push_back(1); // A 的邻居加入 B
    graph[1].push_back(0); // B 的邻居加入 A，因为这是无向图
    graph[0].push_back(2); // A 的邻居加入 C
    graph[2].push_back(0); // C 的邻居加入 A，因为这是无向图
    graph[1].push_back(3); // B 的邻居加入 D
    graph[3].push_back(1); // D 的邻居加入 B，因为这是无向图
    graph[2].push_back(3); // C 的邻居加入 D
    graph[3].push_back(2); // D 的邻居加入 C，因为这是无向图
    for (int neighbor : graph[0]) // 遍历 A 的所有邻居
    { // for 循环开始
        cout << neighbor << endl; // 打印 A 的邻居编号，会输出 1 和 2
    } // for 循环结束
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

邻接矩阵和邻接表对比

对比点	邻接矩阵	邻接表
存储方式	二维数组	每个点存一个邻居列表
空间复杂度	O(V²)	O(V + E)
查询两点是否相连	快，O(1)	通常要遍历邻居，O(degree)
遍历某点所有邻居	要扫一整行，O(V)	只遍历真实邻居，O(degree)
适合场景	点少、边多、频繁查边	点多、边少、经常遍历邻居
游戏常见用途	小规模关系表、可达性表	地图寻路、导航图、任务依赖图

这里的 V 是顶点数量，E 是边数量，degree 是某个点的邻居数量。

带权图怎么存

如果是邻接矩阵，原来格子里存 0 或 1。

带权图可以改成存权重：

matrix[A][B] = 5

表示 A 到 B 的代价是 5。

如果是邻接表，每个邻居节点除了存 to，还要存 weight。

例如：

A: (B, 5), (C, 2)

表示：

A 到 B 代价是 5。

A 到 C 代价是 2。

带权邻接表代码示例

#include <iostream> // 引入输入输出库，用来打印结果
#include <vector> // 引入 vector 容器，用来保存邻接表
using namespace std; // 使用标准命名空间，避免每次写 std::

struct Edge // 定义边结构体
{ // Edge 结构体开始
    int to; // 表示这条边连接到哪个点
    int weight; // 表示这条边的权重或代价
}; // Edge 结构体结束

int main() // 程序入口函数
{ // main 函数开始
    int vertexCount = 3; // 定义顶点数量，0 表示 A，1 表示 B，2 表示 C
    vector<vector<Edge>> graph(vertexCount); // 创建带权邻接表，每个点保存若干条边
    graph[0].push_back({1, 5}); // 添加 A 到 B 的边，代价是 5
    graph[0].push_back({2, 2}); // 添加 A 到 C 的边，代价是 2
    for (Edge edge : graph[0]) // 遍历 A 出发的所有边
    { // for 循环开始
        cout << "to = " << edge.to << ", weight = " << edge.weight << endl; // 打印目标点和边权重
    } // for 循环结束
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

面试高分回答

IMPORTANT

图常见的存储方式有邻接矩阵和邻接表。邻接矩阵用二维数组表示点与点之间是否有边，优点是查询任意两个点是否相连非常快，复杂度是 O(1)；缺点是空间固定为 O(V²)，如果点很多但边很少，会浪费大量空间。邻接表是每个点维护一个邻居列表，只存真实存在的边，空间复杂度是 O(V + E)，更适合稀疏图，也方便做 BFS、DFS、Dijkstra、A* 这类需要遍历邻居的算法。简单记忆就是：边很多、频繁查边用邻接矩阵；点多边少、频繁遍历邻居用邻接表。

Trie 树适合什么场景？

一句话理解

Trie 树也叫“前缀树”，最适合处理“字符串前缀相关”的问题，比如搜索提示、字典查词、前缀匹配。

Trie 是什么

Trie 不是按整个字符串存，而是按字符一层一层存。

比如存入：

cat
car
care
dog

cat、car、care 都有公共前缀 ca，Trie 会让它们共用这段路径：

root -> c -> a

然后再分叉成：

t
r -> e

所以 Trie 的核心价值是：公共前缀只存一份。

适合什么场景

Trie 特别适合这些场景：

搜索自动补全：输入 ca，快速找出 cat、car、care。

字典查词：判断某个单词是否存在。

前缀匹配：找所有以某个前缀开头的字符串。

敏感词过滤：把敏感词放进 Trie，然后按字符扫描文本。更复杂的多敏感词匹配常用 AC 自动机。

路径匹配：比如文件路径、URL 路由、配置路径。

IP 路由匹配：网络里常见最长前缀匹配，可以用二进制 Trie 思想。

游戏里也可能用：聊天敏感词过滤、命令自动补全、道具名搜索、技能名搜索、资源路径索引。

Trie 的查询复杂度

如果要查单词 care，Trie 不需要遍历所有单词。

它只需要按字符走：

c -> a -> r -> e

所以复杂度主要取决于字符串长度。

如果字符串长度是 L，那么插入、查找、前缀查询通常是：

O(L)

这点非常重要。

它不是看字典里有多少个词，而是看你要查的字符串有多长。

和哈希表有什么区别

如果你只是想判断完整字符串是否存在，比如：

"cat" 是否存在？

哈希表通常更简单，也可能更省内存。

但如果你想查：

所有以 "ca" 开头的单词有哪些？

哈希表就不擅长了，因为它是按完整 key 算 hash 的，不天然支持前缀关系。

Trie 的强项就是前缀。

C++ 简单代码示例

下面实现三个功能：

Insert：插入单词。

Search：查完整单词是否存在。

StartsWith：查是否存在某个前缀。

#include <iostream> // 引入输入输出库，用来打印结果
#include <string> // 引入 string 类型，用来保存单词
using namespace std; // 使用标准命名空间，避免每次写 std::

struct TrieNode // 定义 Trie 的节点结构体
{ // TrieNode 结构体开始
    TrieNode* children[26]; // 保存 26 个小写字母对应的子节点指针
    bool isEnd; // 标记从根节点走到这里是否形成了一个完整单词
    TrieNode() // 定义构造函数，用来初始化节点
    { // 构造函数开始
        isEnd = false; // 新节点默认不是单词结尾
        for (int i = 0; i < 26; i++) // 遍历 26 个字母位置
        { // for 循环开始
            children[i] = nullptr; // 每个子节点指针一开始都设置为空
        } // for 循环结束
    } // 构造函数结束
}; // TrieNode 结构体结束

class Trie // 定义 Trie 类
{ // Trie 类开始
private: // private 表示下面成员只能在类内部访问
    TrieNode* root; // 保存 Trie 的根节点

public: // public 表示下面函数可以被外部调用
    Trie() // 定义 Trie 构造函数
    { // Trie 构造函数开始
        root = new TrieNode(); // 创建根节点，根节点本身不代表任何字符
    } // Trie 构造函数结束

    void Insert(string word) // 定义插入单词的函数
    { // Insert 函数开始
        TrieNode* current = root; // 从根节点开始往下走
        for (char ch : word) // 逐个读取单词里的字符
        { // for 循环开始
            int index = ch - 'a'; // 把字符转换成 0 到 25 的数组下标
            if (current->children[index] == nullptr) // 如果这个字符对应的节点还不存在
            { // if 语句开始
                current->children[index] = new TrieNode(); // 创建一个新的子节点
            } // if 语句结束
            current = current->children[index]; // 移动到这个字符对应的子节点
        } // for 循环结束
        current->isEnd = true; // 单词走完后，把当前节点标记为单词结尾
    } // Insert 函数结束

    bool Search(string word) // 定义查找完整单词的函数
    { // Search 函数开始
        TrieNode* current = root; // 从根节点开始查找
        for (char ch : word) // 逐个读取要查找的字符
        { // for 循环开始
            int index = ch - 'a'; // 把字符转换成数组下标
            if (current->children[index] == nullptr) // 如果某个字符路径不存在
            { // if 语句开始
                return false; // 说明这个完整单词不存在
            } // if 语句结束
            current = current->children[index]; // 沿着字符路径继续往下走
        } // for 循环结束
        return current->isEnd; // 只有走到单词结尾标记，才算完整单词存在
    } // Search 函数结束

    bool StartsWith(string prefix) // 定义判断前缀是否存在的函数
    { // StartsWith 函数开始
        TrieNode* current = root; // 从根节点开始查找前缀
        for (char ch : prefix) // 逐个读取前缀字符
        { // for 循环开始
            int index = ch - 'a'; // 把字符转换成数组下标
            if (current->children[index] == nullptr) // 如果前缀路径中断
            { // if 语句开始
                return false; // 说明没有任何单词以这个前缀开头
            } // if 语句结束
            current = current->children[index]; // 沿着前缀路径继续往下走
        } // for 循环结束
        return true; // 前缀路径能走完，说明存在这个前缀
    } // StartsWith 函数结束
}; // Trie 类结束

常见坑

Trie 很快，但比较占内存。因为每个节点可能有很多子节点指针。

如果字符集很小，比如只处理小写英文，可以用 `children[26]`。

如果字符集很大，比如中文、路径、任意字符，通常会用 `map` 或 `unordered_map` 存子节点，避免每个节点都开很大的数组。

还有一点：Trie 查前缀很强，但不是所有字符串问题都要用 Trie。只查完整字符串是否存在，用哈希表往往更直接。

面试高分回答

IMPORTANT

Trie 树适合处理前缀相关的字符串问题。它把字符串按字符拆开存储，不同字符串的公共前缀可以共用同一段路径，所以插入、查找、前缀判断的复杂度主要和字符串长度有关，通常是 O(L)。典型场景包括搜索自动补全、字典查词、前缀匹配、敏感词过滤、路径匹配和 IP 最长前缀匹配。它的缺点是节点和指针较多，空间开销可能比较大，所以字符集较小时可以用数组存子节点，字符集较大时通常用哈希表或映射表存子节点。

并查集是什么？

一句话理解

并查集就是专门处理“分组问题”的数据结构。它最擅长回答两个问题：两个元素是不是同一组？能不能把两个组合并成一组？

并查集解决什么问题

假设有 6 个人：

1, 2, 3, 4, 5, 6

一开始每个人都是单独一组：

{1} {2} {3} {4} {5} {6}

后来告诉你：

1 和 2 是朋友
2 和 3 是朋友
4 和 5 是朋友

那么分组就变成：

{1, 2, 3} {4, 5} {6}

这时你想问：

1 和 3 是不是同一组？

答案是：是。

再问：

1 和 5 是不是同一组？

答案是：不是。

并查集就是用来高效处理这种“合并集合”和“查询是否同集合”的。

并查集的三个核心操作

第一个：初始化。

每个元素一开始都是自己的组长。

parent[1] = 1
parent[2] = 2
parent[3] = 3

第二个：查找 Find。

查找某个元素属于哪个集合，也就是找它的“根节点”或“代表元素”。

第三个：合并 Union。

如果两个元素不在同一个集合，就把它们所在的集合合并。

Find 是什么

Find(x) 的意思是：找到 x 所在集合的代表。

可以理解成找“队伍老大”。

比如：

5 -> 2 -> 1

说明：

5 的父节点是 2。

2 的父节点是 1。

1 的父节点是自己。

所以：

Find(5) = 1

也就是说，5 属于以 1 为代表的集合。

Union 是什么

Union(a, b) 的意思是：把 a 所在的集合和 b 所在的集合合并。

比如：

Find(3) = 1
Find(5) = 4

说明 3 属于 1 这组，5 属于 4 这组。

执行：

Union(3, 5)

就可以让其中一个根指向另一个根：

parent[4] = 1

这样两个集合就合并了。

路径压缩是什么

如果树长得很高，查找会变慢。

比如：

6 -> 5 -> 4 -> 3 -> 2 -> 1

找 6 的根要走很多步。

路径压缩的做法是：当你执行 Find(6) 时，顺便把路上的节点都直接挂到根节点下面。

压缩后变成：

6 -> 1
5 -> 1
4 -> 1
3 -> 1
2 -> 1

以后再查这些节点就快很多。

按秩合并是什么

合并时不要随便乱接。

如果总是把高树接到矮树下面，树会越来越高。

按秩合并的思想是：

矮树接到高树下面。

或者小集合接到大集合下面。

这样可以让树尽量保持低，查找更快。

实际写并查集时，常见优化就是：

路径压缩。

按秩合并或按大小合并。

这两个一起用，并查集的效率非常高，几乎可以看成接近 `O(1)`。

C++ 代码示例

下面是带路径压缩和按大小合并的并查集。

#include <iostream> // 引入输入输出库，用来打印结果
#include <vector> // 引入 vector 容器，用来保存 parent 和 size 数组
using namespace std; // 使用标准命名空间，避免每次写 std::

class UnionFind // 定义并查集类
{ // UnionFind 类开始
private: // private 表示下面成员只能在类内部访问
    vector<int> parent; // parent[x] 表示 x 的父节点是谁
    vector<int> size; // size[x] 表示以 x 为根的集合大小

public: // public 表示下面函数可以被外部调用
    UnionFind(int n) // 定义构造函数，用 n 初始化并查集
    { // 构造函数开始
        parent.resize(n); // parent 数组开 n 个位置
        size.resize(n, 1); // size 数组开 n 个位置，每个集合初始大小都是 1
        for (int i = 0; i < n; i++) // 遍历每一个元素
        { // for 循环开始
            parent[i] = i; // 一开始每个元素的父节点都是自己
        } // for 循环结束
    } // 构造函数结束

    int Find(int x) // 定义查找函数，用来找到 x 所在集合的根
    { // Find 函数开始
        if (parent[x] != x) // 如果 x 的父节点不是自己，说明 x 不是根
        { // if 语句开始
            parent[x] = Find(parent[x]); // 路径压缩，让 x 直接指向根节点
        } // if 语句结束
        return parent[x]; // 返回 x 所在集合的根节点
    } // Find 函数结束

    void Union(int a, int b) // 定义合并函数，用来合并 a 和 b 所在的集合
    { // Union 函数开始
        int rootA = Find(a); // 找到 a 所在集合的根节点
        int rootB = Find(b); // 找到 b 所在集合的根节点
        if (rootA == rootB) // 如果两个根相同，说明已经在同一个集合
        { // if 语句开始
            return; // 不需要重复合并，直接返回
        } // if 语句结束
        if (size[rootA] < size[rootB]) // 如果 A 集合比 B 集合小
        { // if 语句开始
            parent[rootA] = rootB; // 把 A 集合的根挂到 B 集合根下面
            size[rootB] += size[rootA]; // 更新 B 集合的大小
        } // if 语句结束
        else // 否则说明 A 集合不小于 B 集合
        { // else 语句开始
            parent[rootB] = rootA; // 把 B 集合的根挂到 A 集合根下面
            size[rootA] += size[rootB]; // 更新 A 集合的大小
        } // else 语句结束
    } // Union 函数结束

    bool IsSameSet(int a, int b) // 定义判断函数，用来判断 a 和 b 是否属于同一集合
    { // IsSameSet 函数开始
        return Find(a) == Find(b); // 如果两个元素的根相同，就说明它们在同一集合
    } // IsSameSet 函数结束
}; // UnionFind 类结束

int main() // 程序入口函数
{ // main 函数开始
    UnionFind uf(6); // 创建包含 0 到 5 六个元素的并查集
    uf.Union(0, 1); // 合并 0 和 1 所在的集合
    uf.Union(1, 2); // 合并 1 和 2 所在的集合
    uf.Union(3, 4); // 合并 3 和 4 所在的集合
    cout << uf.IsSameSet(0, 2) << endl; // 判断 0 和 2 是否同组，输出 1 表示是
    cout << uf.IsSameSet(0, 4) << endl; // 判断 0 和 4 是否同组，输出 0 表示不是
    uf.Union(2, 4); // 合并 2 和 4 所在的集合
    cout << uf.IsSameSet(0, 4) << endl; // 再判断 0 和 4 是否同组，输出 1 表示是
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

适合什么场景

并查集适合处理“连通性问题”。

比如：

判断两个人是否在同一个朋友圈。

判断两个城市是否连通。

判断图里加一条边会不会形成环。

Kruskal 最小生成树算法。

岛屿数量问题。

网络连通问题。

游戏里判断区域是否连通。

地图格子合并。

动态合并阵营、队伍、联盟关系。

它不适合什么

并查集很擅长合并，但不擅长拆分。

比如你已经把两个集合合并了，后来想把其中一个元素拆出去，普通并查集做起来就很麻烦。

它也不关心集合内部顺序。

它只回答：

是不是同一组？

以及：

把两组合并。

如果你要频繁删除边、拆集合、维护集合里所有元素的顺序，就要考虑别的数据结构。

面试高分回答

NOTE

并查集是一种维护不相交集合的数据结构，主要支持 Find 和 Union 两个操作。Find 用来找到元素所在集合的代表节点，Union 用来合并两个元素所在的集合。它常用于判断连通性，比如朋友圈、图的连通分量、Kruskal 最小生成树和判断加边是否成环。实现上通常用 parent 数组表示父节点，并通过路径压缩和按秩或按大小合并来优化效率，使操作复杂度接近常数级。需要注意的是，普通并查集适合合并和查询，不适合频繁拆分集合。

LRU 缓存怎么实现？

一句话理解

LRU Cache 就是：缓存容量满了以后，淘汰“最久没有被使用”的数据。实现上经典组合是：哈希表 + 双向链表。

LRU 是什么

LRU 全称是 Least Recently Used，意思是“最近最少使用”。

它的规则很像手机后台 App：

你刚打开过的 App，认为很新。

很久没打开过的 App，认为很旧。

内存不够时，优先清理最久没用的那个。

放到缓存里就是：

get(key)：访问了这个 key，所以它变成“最近使用”。

put(key, value)：新增或更新这个 key，所以它也变成“最近使用”。

容量满了：删除“最久未使用”的 key。

为什么要用哈希表 + 双向链表

只用数组不行，因为删除中间元素、移动元素成本高。

只用链表也不行，因为按 key 查找会很慢。

所以经典做法是：

哈希表：负责快速找到 key 对应的节点，查找 `O(1)`。

双向链表：负责维护使用顺序，移动节点、删除尾节点都是 `O(1)`。

链表头部表示最近使用。

链表尾部表示最久未使用。

核心流程

get(key)：

先用哈希表查 key。

如果不存在，返回 -1。

如果存在，拿到 value，并把这个节点移动到链表头部。

put(key, value)：

如果 key 已经存在，更新 value，并移动到链表头部。

如果 key 不存在，把新节点插入链表头部。

如果超过容量，删除链表尾部节点，同时从哈希表删除它。

C++ 实现

下面用 std::list 表示双向链表，用 unordered_map 保存 key -> 链表迭代器。

#include <iostream> // 引入输入输出库，用来打印测试结果
#include <list> // 引入 list，std::list 本质是双向链表
#include <unordered_map> // 引入 unordered_map，用来做 key 到链表节点的快速映射
using namespace std; // 使用标准命名空间，避免每次写 std::
class LRUCache // 定义 LRU 缓存类
{ // LRUCache 类开始
private: // private 表示下面成员只能在类内部访问
    int capacity; // 保存缓存最大容量
    list<pair<int, int>> items; // 双向链表保存 key 和 value，链表头是最新使用，链表尾是最久未使用
    unordered_map<int, list<pair<int, int>>::iterator> index; // 哈希表保存 key 到链表节点迭代器的映射
public: // public 表示下面函数可以被外部调用
    LRUCache(int cap) : capacity(cap) // 构造函数，用传入的 cap 初始化缓存容量
    { // 构造函数开始
    } // 构造函数结束
    int Get(int key) // 定义 Get 函数，用来读取 key 对应的 value
    { // Get 函数开始
        auto it = index.find(key); // 在哈希表中查找 key
        if (it == index.end()) // 如果哈希表里找不到 key
        { // if 语句开始
            return -1; // 返回 -1 表示缓存未命中
        } // if 语句结束
        items.splice(items.begin(), items, it->second); // 把命中的链表节点移动到链表头，表示最近使用
        return it->second->second; // 返回链表节点里的 value
    } // Get 函数结束
    void Put(int key, int value) // 定义 Put 函数，用来新增或更新缓存
    { // Put 函数开始
        if (capacity <= 0) // 如果容量小于等于 0
        { // if 语句开始
            return; // 不能存任何数据，直接返回
        } // if 语句结束
        auto it = index.find(key); // 先查找 key 是否已经存在
        if (it != index.end()) // 如果 key 已经存在
        { // if 语句开始
            it->second->second = value; // 更新这个节点中的 value
            items.splice(items.begin(), items, it->second); // 把这个节点移动到链表头，表示最近使用
            return; // 更新完成后直接返回
        } // if 语句结束
        if (items.size() == capacity) // 如果缓存已经满了
        { // if 语句开始
            auto last = items.back(); // 取出链表尾部节点，它就是最久未使用的数据
            index.erase(last.first); // 从哈希表中删除这个最旧 key
            items.pop_back(); // 从链表尾部删除最旧节点
        } // if 语句结束
        items.push_front({key, value}); // 把新 key 和 value 插入链表头部
        index[key] = items.begin(); // 在哈希表中记录 key 对应的链表节点位置
    } // Put 函数结束
}; // LRUCache 类结束
int main() // 程序入口函数
{ // main 函数开始
    LRUCache cache(2); // 创建容量为 2 的 LRU 缓存
    cache.Put(1, 100); // 放入 key=1，value=100
    cache.Put(2, 200); // 放入 key=2，value=200
    cout << cache.Get(1) << endl; // 访问 key=1，输出 100，并让 key=1 变成最近使用
    cache.Put(3, 300); // 放入 key=3，此时容量满了，会淘汰最久未使用的 key=2
    cout << cache.Get(2) << endl; // 查询 key=2，输出 -1，因为它已经被淘汰
    cout << cache.Get(3) << endl; // 查询 key=3，输出 300
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

为什么移动到链表头

因为 LRU 的判断标准是“最近有没有用过”。

只要 get 或 put 访问了某个 key，就说明它刚被使用，应该移动到头部。

链表尾部自然就是最久没有被访问的节点。

为什么不用普通链表

普通单链表删除一个节点时，往往需要知道它的前一个节点。

双向链表节点有前后指针，所以可以在 O(1) 时间把节点摘出来，再放到头部。

C++ 的 std::list 就是双向链表，配合 splice 可以直接移动节点，不需要重新创建节点。

复杂度

get：O(1)。

put：O(1)。

空间复杂度：O(capacity)。

因为最多存 capacity 个节点，同时哈希表也最多存 capacity 个 key。

面试高分回答

IMPORTANT

LRU 缓存一般用哈希表加双向链表实现。哈希表负责根据 key 在 O(1) 时间找到链表节点，双向链表负责维护访问顺序，头部表示最近使用，尾部表示最久未使用。每次 get 命中或 put 更新，都把对应节点移动到链表头；当容量满时，删除链表尾部节点，并同步从哈希表中移除。这样 get 和 put 都可以做到 O(1)。

跳表是什么？

一句话理解

跳表 Skip List 是“带多层索引的有序链表”。普通链表只能一个一个找，跳表可以先在上层快速跳，再往下细找，所以查找、插入、删除的期望复杂度都是 O(log n)。

先用零基础方式理解

普通有序链表是这样：

1 -> 3 -> 5 -> 7 -> 8 -> 9 -> 12 -> 19

如果你要找 12，普通链表只能从头开始：

1 -> 3 -> 5 -> 7 -> 8 -> 9 -> 12

跳表会在链表上面加几层“快捷通道”：

Level 2: head -> 7 -> 12
Level 1: head -> 3 -> 7 -> 9 -> 12
Level 0: head -> 1 -> 3 -> 5 -> 7 -> 8 -> 9 -> 12 -> 19

查找 12 时，就不用从底层一步一步走，可以从高层开始跳。高层走不动了，就下降一层继续找。

跳表查找规则

从最高层开始。

如果右边节点的值小于目标值，就往右走。

如果右边节点的值大于目标值，就往下一层。

一直走到底层后，再判断目标值是否存在。

这句话很重要：

能右走就右走，右边太大就下楼。

跳表为什么快

因为上层节点更少，可以跳过很多底层节点。

它有点像地铁：

底层是每站都停。

上层是快线，只停大站。

你先坐快线到目标附近，再换普通线精确到站。

所以跳表的查找不是每次从头扫到尾，而是逐层缩小范围。

跳表和二叉搜索树有什么像

跳表和二叉搜索树、平衡树都可以做有序数据查找。

它们都支持：

查找某个值。

插入某个值。

删除某个值。

按顺序遍历。

区别是：

平衡树靠旋转维持平衡。

跳表靠随机层数维持概率上的平衡。

所以跳表实现起来通常比红黑树简单一些。

Redis 的有序集合 `zset` 底层就用到了跳表。

复杂度

操作	平均 / 期望复杂度	最坏复杂度
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)
顺序遍历	O(n)	O(n)

为什么最坏是 O(n)？

因为跳表靠随机层数。如果运气特别差，所有节点都只有底层，那它就退化成普通链表。

但实际工程里，随机策略设计得好，平均性能非常稳定。

C++ 简化代码

下面这个例子为了让你看懂跳表核心，没有写随机层数，而是插入时手动传入层数。真实跳表一般会用随机函数决定新节点有几层。

#include <iostream> // 引入输入输出库，用来打印查找结果
#include <vector> // 引入 vector，用来保存每个节点的多层 forward 指针
#include <memory> // 引入 unique_ptr，用来自动管理节点内存
using namespace std; // 使用标准命名空间，避免每次写 std::
struct Node // 定义跳表节点结构体
{ // Node 结构体开始
    int value; // 保存节点的值
    vector<Node*> next; // 保存多层 next 指针，next[0] 是底层链表，next[1] 是上一层索引
    Node(int v, int level) : value(v), next(level, nullptr) // 构造节点，并根据层数创建 next 数组
    { // Node 构造函数开始
    } // Node 构造函数结束
}; // Node 结构体结束
class SkipList // 定义跳表类
{ // SkipList 类开始
private: // private 表示下面成员只能在类内部访问
    int maxLevel; // 保存跳表允许的最大层数
    Node* head; // 保存头节点指针，头节点不存真实数据
    vector<unique_ptr<Node>> storage; // 保存所有节点的所有权，避免手动 delete 导致内存泄漏
public: // public 表示下面函数可以被外部调用
    SkipList(int level) : maxLevel(level), head(nullptr) // 构造跳表，并设置最大层数
    { // SkipList 构造函数开始
        storage.push_back(make_unique<Node>(-1, maxLevel)); // 创建头节点，头节点拥有所有层
        head = storage.back().get(); // 让 head 指向刚创建的头节点
    } // SkipList 构造函数结束
    void Insert(int value, int levelCount) // 插入一个值，levelCount 表示这个节点有几层
    { // Insert 函数开始
        vector<Node*> update(maxLevel, head); // update[i] 记录第 i 层中新节点应该插入到谁后面
        Node* current = head; // 从头节点开始查找插入位置
        for (int level = maxLevel - 1; level >= 0; level--) // 从最高层一路向下查找
        { // for 循环开始
            while (current->next[level] != nullptr && current->next[level]->value < value) // 当前层右侧节点存在并且小于插入值时继续右移
            { // while 循环开始
                current = current->next[level]; // 在当前层向右移动
            } // while 循环结束
            update[level] = current; // 记录这一层中插入位置的前一个节点
        } // for 循环结束
        storage.push_back(make_unique<Node>(value, levelCount)); // 创建新节点，并交给 storage 管理生命周期
        Node* newNode = storage.back().get(); // 取出新节点的裸指针，用来连接链表
        for (int level = 0; level < levelCount; level++) // 在新节点拥有的每一层插入它
        { // for 循环开始
            newNode->next[level] = update[level]->next[level]; // 新节点先指向原本的下一个节点
            update[level]->next[level] = newNode; // 前一个节点再指向新节点，完成插入
        } // for 循环结束
    } // Insert 函数结束
    bool Search(int target) // 查找目标值是否存在
    { // Search 函数开始
        Node* current = head; // 从头节点开始查找
        for (int level = maxLevel - 1; level >= 0; level--) // 从最高层开始往下查
        { // for 循环开始
            while (current->next[level] != nullptr && current->next[level]->value < target) // 右边节点存在并且小于目标值时继续右移
            { // while 循环开始
                current = current->next[level]; // 在当前层向右跳
            } // while 循环结束
        } // for 循环结束
        current = current->next[0]; // 下降到底层后，看目标可能所在的下一个节点
        return current != nullptr && current->value == target; // 如果下一个节点存在且值等于目标，就说明找到了
    } // Search 函数结束
}; // SkipList 类结束
int main() // 程序入口函数
{ // main 函数开始
    SkipList list(4); // 创建一个最大 4 层的跳表
    list.Insert(1, 1); // 插入 1，只放在底层
    list.Insert(3, 2); // 插入 3，放在 2 层
    list.Insert(7, 4); // 插入 7，放在 4 层，作为高层索引节点
    list.Insert(9, 2); // 插入 9，放在 2 层
    list.Insert(12, 4); // 插入 12，放在 4 层，作为高层索引节点
    cout << list.Search(12) << endl; // 查找 12，输出 1 表示找到了
    cout << list.Search(8) << endl; // 查找 8，输出 0 表示没找到
    return 0; // 返回 0，表示程序正常结束
} // main 函数结束

适合什么场景

跳表适合需要维护“有序集合”的场景。

比如：

排行榜。

有序缓存。

范围查询。

按分数排序的数据。

需要频繁插入、删除、查找的有序数据。

Redis 的 `zset`。

如果只是查 key 是否存在，哈希表更直接。

如果既要有序，又要支持较快插入删除查找，跳表就很适合。

面试高分回答

NOTE

跳表是一种基于有序链表的概率型数据结构。它在底层保存完整有序链表，在上层建立多级稀疏索引，查找时从最高层开始，能向右走就向右走，不能走就下降一层，最终在底层定位目标。跳表通过随机层数让结构在概率上保持平衡，因此查找、插入、删除的期望复杂度都是 O(log n)，空间复杂度是 O(n)。它相比红黑树实现更简单，也天然支持顺序遍历和范围查询，典型应用是 Redis 的有序集合。