算法 / 计基必背

数组和链表

一句话理解

数组是连续内存，靠下标直接算地址，所以访问快。 链表是一个个节点用指针串起来，所以插删灵活，但查找慢。

数组底层

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

访问 arr[i] 时，地址可以直接算：

arr[i] 地址 = 起始地址 + i * 元素大小

所以随机访问是 O(1)。

但如果在中间插入或删除，后面的元素要整体移动，所以通常是 O(n)。

链表底层

链表由很多节点组成，每个节点保存：

数据 data
下一个节点地址 next

它的节点不要求连续存放。 要找第 i 个节点，通常只能从头节点一路 next 走过去，所以查找是 O(n)。

但如果已经找到了某个节点，要插入或删除，只需要改指针，操作本身可以是 O(1)。

代码示例：数组访问

#include <iostream> // 引入输入输出库
int main() // 程序入口函数
{ // main 函数体开始
    int arr[5] = {10, 20, 30, 40, 50}; // 创建一个长度为 5 的数组
    std::cout << arr[3] << std::endl; // 通过下标直接访问第 4 个元素
    arr[2] = 99; // 通过下标直接修改第 3 个元素
    for (int i = 0; i < 5; ++i) // 从 0 遍历到 4
    { // for 循环体开始
        std::cout << arr[i] << std::endl; // 输出当前下标对应的元素
    } // for 循环体结束
    return 0; // 程序正常结束
} // main 函数体结束

代码示例：单链表插入

#include <iostream> // 引入输入输出库
struct Node // 定义链表节点结构体
{ // Node 结构体开始
    int value; // 保存节点数据
    Node* next; // 保存下一个节点的地址
}; // Node 结构体结束
int main() // 程序入口函数
{ // main 函数体开始
    Node node1{10, nullptr}; // 创建第一个节点，值为 10
    Node node2{20, nullptr}; // 创建第二个节点，值为 20
    Node node3{30, nullptr}; // 创建第三个节点，值为 30
    node1.next = &node2; // 让 node1 指向 node2
    node2.next = &node3; // 让 node2 指向 node3
    Node newNode{99, nullptr}; // 创建一个新节点，值为 99
    newNode.next = node1.next; // 新节点先指向 node1 原来后面的节点
    node1.next = &newNode; // node1 再指向新节点，完成插入
    Node* current = &node1; // 从头节点开始遍历链表
    while (current != nullptr) // 只要当前节点不为空就继续
    { // while 循环体开始
        std::cout << current->value << std::endl; // 输出当前节点的值
        current = current->next; // 移动到下一个节点
    } // while 循环体结束
    return 0; // 程序正常结束
} // main 函数体结束

怎么选择？

频繁随机访问、顺序遍历、追求缓存友好：选数组或 vector。 频繁在已知位置插入删除、不方便申请连续大内存：可以考虑链表。

但工程里要注意，链表不一定比数组快。因为链表节点分散，CPU 缓存命中率差，而且每个节点还要多存一个指针。

面试高分回答

NOTE

数组底层是一段连续内存，所以可以通过起始地址加偏移量直接访问任意元素，随机访问复杂度是 O(1)，缓存友好，但中间插入删除需要移动元素，复杂度通常是 O(n)。链表由节点组成，每个节点通过指针指向下一个节点，不要求连续内存，已知节点位置时插入删除只需要修改指针，可以是 O(1)，但查找第几个元素必须从头遍历，复杂度是 O(n)，并且指针额外占空间、缓存不友好。实际开发中，如果没有非常明确的插删需求，通常优先考虑数组或 vector。

栈和队列

一句话理解

栈是后进先出，像一摞盘子。 队列是先进先出，像排队买票。

栈 Stack

栈只能从一端操作，这一端叫栈顶。

常见操作：

• push：入栈
• pop：出栈
• top：看栈顶元素

特点是 LIFO：Last In First Out，后进先出。

适合场景：

• 括号匹配
• 函数调用栈
• 撤销操作
• DFS 深度优先搜索

队列 Queue

队列从队尾进入，从队头离开。

常见操作：

• push：入队
• pop：出队
• front：看队头元素
• back：看队尾元素

特点是 FIFO：First In First Out，先进先出。

适合场景：

• 任务排队
• 消息队列
• BFS 广度优先搜索
• 生产者消费者模型

C++ 标准库代码

#include <iostream> // 引入输入输出库
#include <stack> // 引入 stack 容器适配器
#include <queue> // 引入 queue 容器适配器
int main() // 程序入口函数
{ // main 函数体开始
    std::stack<int> s; // 创建一个 int 类型的栈
    s.push(1); // 把 1 压入栈
    s.push(2); // 把 2 压入栈
    s.push(3); // 把 3 压入栈
    std::cout << s.top() << std::endl; // 输出栈顶元素，此时是 3
    s.pop(); // 弹出栈顶元素 3
    std::cout << s.top() << std::endl; // 输出新的栈顶元素，此时是 2
    std::queue<int> q; // 创建一个 int 类型的队列
    q.push(1); // 把 1 放入队尾
    q.push(2); // 把 2 放入队尾
    q.push(3); // 把 3 放入队尾
    std::cout << q.front() << std::endl; // 输出队头元素，此时是 1
    q.pop(); // 弹出队头元素 1
    std::cout << q.front() << std::endl; // 输出新的队头元素，此时是 2
    return 0; // 程序正常结束
} // main 函数体结束

注意点

std::stack 和 std::queue 是容器适配器，不是普通容器。 它们底层默认通常用 deque，也可以指定其他底层容器。

空栈不能直接 top()。 空队列不能直接 front()。 实际使用前最好先判断 empty()。

面试高分回答

TIP

栈和队列都是受限线性结构。栈只允许在栈顶插入和删除，遵循后进先出，所以适合括号匹配、函数调用、撤销、DFS 等场景。队列从队尾插入、队头删除，遵循先进先出，所以适合任务调度、消息队列、BFS、生产者消费者等场景。在 C++ STL 中，stack 和 queue 是容器适配器，默认底层常用 deque，主要暴露特定的访问接口，而不是让用户随机访问内部元素。

哈希表

一句话理解

哈希表就是用 hash(key) 把 key 映射到数组下标，从而快速找到数据的位置。

理想情况下，插入、查找、删除都是平均 O(1)。

底层怎么工作？

哈希表底层通常有一个桶数组：

index = hash(key) % bucketCount

比如 key 是 "apple"，先算出哈希值，再对桶数量取模，得到它应该放在哪个桶。

但是不同 key 可能算到同一个桶，这叫哈希冲突。

冲突怎么解决？

链地址法：每个桶后面挂链表或节点集合。多个 key 落到同一个桶，就挂在同一个桶后面。unordered_map 常见实现可以理解成这种思路。

开放寻址法：如果目标桶被占了，就继续按照某种规则找下一个空桶，比如线性探测。

代码示例：简单链地址哈希表

#include <iostream> // 引入输入输出库
#include <list> // 引入 list，用来做桶里的链表
#include <string> // 引入 string 字符串类型
#include <vector> // 引入 vector，用来做桶数组
class HashTable // 定义一个简单哈希表类
{ // 类体开始
private: // 私有成员开始
    std::vector<std::list<std::pair<std::string, int>>> buckets; // 桶数组，每个桶里是一条链表
    int Hash(const std::string& key) const // 定义哈希函数，把字符串转成桶下标
    { // 哈希函数体开始
        int sum = 0; // 定义累加值，用来计算简单哈希
        for (char c : key) // 遍历字符串里的每个字符
        { // for 循环体开始
            sum += c; // 把字符编码累加到 sum
        } // for 循环体结束
        return sum % buckets.size(); // 对桶数量取模，得到桶下标
    } // 哈希函数体结束
public: // 公有成员开始
    explicit HashTable(int bucketCount) : buckets(bucketCount) // 构造函数，创建指定数量的桶
    { // 构造函数体开始
    } // 构造函数体结束
    void Insert(const std::string& key, int value) // 插入或更新 key-value
    { // Insert 函数体开始
        int index = Hash(key); // 计算 key 应该进入哪个桶
        for (auto& item : buckets[index]) // 遍历这个桶里的所有节点
        { // for 循环体开始
            if (item.first == key) // 如果找到了相同 key
            { // if 代码块开始
                item.second = value; // 更新已有 key 的 value
                return; // 更新完成后直接返回
            } // if 代码块结束
        } // for 循环体结束
        buckets[index].push_back({key, value}); // 如果没找到，就把新节点插入桶链表
    } // Insert 函数体结束
    bool Find(const std::string& key, int& outValue) const // 查找 key，并通过 outValue 返回值
    { // Find 函数体开始
        int index = Hash(key); // 计算 key 所在桶下标
        for (const auto& item : buckets[index]) // 遍历桶链表
        { // for 循环体开始
            if (item.first == key) // 比较 key 是否相等
            { // if 代码块开始
                outValue = item.second; // 找到后写出 value
                return true; // 返回 true 表示查找成功
            } // if 代码块结束
        } // for 循环体结束
        return false; // 没找到就返回 false
    } // Find 函数体结束
}; // HashTable 类定义结束

复杂度

平均情况：O(1)。 极端情况：O(n)。

如果哈希函数很差，很多 key 都落到同一个桶，哈希表就会退化成链表。

面试高分回答

IMPORTANT

哈希表通过哈希函数把 key 映射到桶数组下标，理想情况下可以做到平均 O(1) 的插入、查找和删除。因为不同 key 可能映射到同一个桶，所以必须处理哈希冲突，常见方式有链地址法和开放寻址法。哈希表还会维护负载因子，当元素数量相对桶数量过多时，会扩容并 rehash，把元素重新分布到更多桶中。它的优点是平均查找快，缺点是不保证顺序，哈希函数差或冲突严重时可能退化。

二叉树遍历

一句话理解

二叉树遍历就是按照某种顺序，把树里的每个节点都访问一遍。

最常见四种：

• 前序：根左右
• 中序：左根右
• 后序：左右根
• 层序：一层一层

递归代码

#include <iostream> // 引入输入输出库
#include <queue> // 引入队列，用于层序遍历
struct TreeNode // 定义二叉树节点结构体
{ // 结构体开始
    int val; // 保存节点的值
    TreeNode* left; // 指向左子节点
    TreeNode* right; // 指向右子节点
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数，初始化节点值和左右指针
}; // 结构体结束
void PreOrder(TreeNode* root) // 前序遍历：根左右
{ // 函数体开始
    if (root == nullptr) return; // 如果节点为空，直接返回
    std::cout << root->val << " "; // 先访问根节点
    PreOrder(root->left); // 再遍历左子树
    PreOrder(root->right); // 最后遍历右子树
} // 函数体结束
void InOrder(TreeNode* root) // 中序遍历：左根右
{ // 函数体开始
    if (root == nullptr) return; // 如果节点为空，直接返回
    InOrder(root->left); // 先遍历左子树
    std::cout << root->val << " "; // 再访问根节点
    InOrder(root->right); // 最后遍历右子树
} // 函数体结束
void PostOrder(TreeNode* root) // 后序遍历：左右根
{ // 函数体开始
    if (root == nullptr) return; // 如果节点为空，直接返回
    PostOrder(root->left); // 先遍历左子树
    PostOrder(root->right); // 再遍历右子树
    std::cout << root->val << " "; // 最后访问根节点
} // 函数体结束
void LevelOrder(TreeNode* root) // 层序遍历：按层访问
{ // 函数体开始
    if (root == nullptr) return; // 如果根节点为空，直接返回
    std::queue<TreeNode*> q; // 创建队列，保存等待访问的节点
    q.push(root); // 先把根节点入队
    while (!q.empty()) // 只要队列不为空，就继续遍历
    { // while 循环体开始
        TreeNode* node = q.front(); // 取出队头节点
        q.pop(); // 弹出队头节点
        std::cout << node->val << " "; // 访问当前节点
        if (node->left != nullptr) q.push(node->left); // 如果左子节点存在，就入队
        if (node->right != nullptr) q.push(node->right); // 如果右子节点存在，就入队
    } // while 循环体结束
} // 函数体结束

示例树结果

如果树是：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

前序：1 2 4 5 3 6 7 中序：4 2 5 1 6 3 7 后序：4 5 2 6 7 3 1 层序：1 2 3 4 5 6 7

复杂度

时间复杂度：O(n)，因为每个节点都访问一次。 递归空间复杂度：O(h)，h 是树高。 层序空间复杂度：O(w)，w 是某一层最大节点数。

面试高分回答

WARNING

二叉树遍历分为深度优先和广度优先。前序、中序、后序属于 DFS，区别是访问根节点的位置：前序根在前，中序根在中，后序根在后。层序遍历属于 BFS，通常用队列实现，先把根节点入队，每次弹出队头节点，再把它的左右子节点入队。所有遍历的时间复杂度都是 O(n)，递归 DFS 的额外空间是树高 O(h)，层序遍历的额外空间和队列最大宽度有关。

BFS 和 DFS

一句话理解

BFS 是广度优先，一层一层往外扩散。 DFS 是深度优先，沿着一条路一直走到底，走不通再回退。

BFS 用什么实现？

BFS 通常用队列 queue。

因为队列是先进先出，所以先发现的节点会先处理，自然形成“按层访问”。

BFS 常用于：

• 二叉树层序遍历
• 无权图最短路径
• 地图格子最少步数
• 一圈一圈扩散的搜索

DFS 用什么实现？

DFS 可以用递归，也可以手写栈 stack。

递归本质上就是系统帮你维护函数调用栈。 DFS 常用于：

• 连通块搜索
• 回溯
• 岛屿数量
• 拓扑排序思想
• 路径枚举

C++ 代码：邻接表 BFS 和 DFS

#include <iostream> // 引入输入输出库
#include <vector> // 引入 vector，用来保存邻接表
#include <queue> // 引入 queue，用来实现 BFS
using Graph = std::vector<std::vector<int>>; // 定义图类型，graph[u] 保存 u 能到达的点
void BFS(const Graph& graph, int start) // 定义 BFS 函数，从 start 开始广度优先遍历
{ // BFS 函数体开始
    std::vector<bool> visited(graph.size(), false); // 创建 visited 数组，记录节点是否访问过
    std::queue<int> q; // 创建队列，保存等待访问的节点
    visited[start] = true; // 标记起点已经访问
    q.push(start); // 把起点放入队列
    while (!q.empty()) // 只要队列不为空，就继续遍历
    { // while 循环体开始
        int cur = q.front(); // 取出队头节点
        q.pop(); // 弹出队头节点
        std::cout << cur << " "; // 访问当前节点
        for (int next : graph[cur]) // 遍历当前节点的所有邻居
        { // for 循环体开始
            if (visited[next]) // 如果邻居已经访问过
            { // if 代码块开始
                continue; // 跳过这个邻居，避免重复访问
            } // if 代码块结束
            visited[next] = true; // 标记邻居已经访问
            q.push(next); // 把邻居加入队列，等待后续访问
        } // for 循环体结束
    } // while 循环体结束
} // BFS 函数体结束
void DFS(const Graph& graph, int cur, std::vector<bool>& visited) // 定义 DFS 函数，从 cur 开始深度优先遍历
{ // DFS 函数体开始
    visited[cur] = true; // 标记当前节点已经访问
    std::cout << cur << " "; // 访问当前节点
    for (int next : graph[cur]) // 遍历当前节点的所有邻居
    { // for 循环体开始
        if (visited[next]) // 如果邻居已经访问过
        { // if 代码块开始
            continue; // 跳过这个邻居，避免重复访问
        } // if 代码块结束
        DFS(graph, next, visited); // 递归访问这个还没访问过的邻居
    } // for 循环体结束
} // DFS 函数体结束
int main() // 程序入口函数
{ // main 函数体开始
    Graph graph(7); // 创建 7 个节点的图，节点编号 0 到 6
    graph[0] = {1, 2}; // 节点 0 连接节点 1 和节点 2
    graph[1] = {3, 4}; // 节点 1 连接节点 3 和节点 4
    graph[2] = {5, 6}; // 节点 2 连接节点 5 和节点 6
    graph[3] = {}; // 节点 3 没有后续邻居
    graph[4] = {}; // 节点 4 没有后续邻居
    graph[5] = {}; // 节点 5 没有后续邻居
    graph[6] = {}; // 节点 6 没有后续邻居
    BFS(graph, 0); // 从节点 0 开始 BFS，输出按层访问顺序
    std::cout << std::endl; // 输出换行
    std::vector<bool> visited(graph.size(), false); // 创建 DFS 使用的 visited 数组
    DFS(graph, 0, visited); // 从节点 0 开始 DFS，输出深度优先访问顺序
    return 0; // 程序正常结束
} // main 函数体结束

复杂度

如果图用邻接表存储：

时间复杂度：O(V + E)V 是点数，E 是边数，因为每个点和每条边最多处理一次。

空间复杂度：O(V) 主要来自 visited、队列或递归栈。

面试高分回答

CAUTION

BFS 和 DFS 都是图或树的基础遍历算法。BFS 使用队列，按照距离从近到远一层层扩散，所以在无权图里可以求最短路径或最少步数。DFS 使用递归或栈，会沿着一条路径尽可能深入，走不通再回退，所以适合连通性判断、回溯、路径搜索等问题。二者在邻接表下时间复杂度都是 O(V+E)，实现时一定要用 visited 防止图中有环导致重复访问或死循环。

二分查找

一句话理解

二分查找就是在有序数组里找目标值。 每次看中间元素 mid，如果中间值小了，就去右半边；如果中间值大了，就去左半边；如果相等，就找到了。

核心条件

数组必须有序。 因为只有有序，才能通过 nums[mid] 和 target 的大小关系判断该丢掉哪一半。

C++ 代码：标准闭区间写法

#include <iostream> // 引入输入输出库
#include <vector> // 引入 vector 容器
int BinarySearch(const std::vector<int>& nums, int target) // 定义二分查找函数，返回目标下标
{ // 函数体开始
    int left = 0; // 定义左边界，从数组第一个位置开始
    int right = static_cast<int>(nums.size()) - 1; // 定义右边界，从数组最后一个位置开始
    while (left <= right) // 当搜索区间没有变空时继续查找
    { // while 循环体开始
        int mid = left + (right - left) / 2; // 计算中间位置，避免 left + right 溢出
        if (nums[mid] == target) // 如果中间值正好等于目标值
        { // if 代码块开始
            return mid; // 返回目标值所在下标
        } // if 代码块结束
        else if (nums[mid] < target) // 如果中间值小于目标值
        { // else if 代码块开始
            left = mid + 1; // 目标只可能在右半边，所以移动左边界
        } // else if 代码块结束
        else // 如果中间值大于目标值
        { // else 代码块开始
            right = mid - 1; // 目标只可能在左半边，所以移动右边界
        } // else 代码块结束
    } // while 循环体结束
    return -1; // 搜索区间为空还没找到，返回 -1
} // 函数体结束
int main() // 程序入口函数
{ // main 函数体开始
    std::vector<int> nums = {1, 3, 5, 7, 9, 11, 13}; // 创建一个有序数组
    int target = 9; // 定义要查找的目标值
    int index = BinarySearch(nums, target); // 调用二分查找函数
    std::cout << index << std::endl; // 输出目标下标，结果是 4
    return 0; // 程序正常结束
} // main 函数体结束

为什么是 O(log n)

因为每一轮都会丢掉一半数据：

n -> n/2 -> n/4 -> n/8 -> ... -> 1

所以最多查找次数大约是 log2(n)。 时间复杂度：O(log n)。 空间复杂度：迭代写法是 O(1)。

常见坑

mid 不推荐写成：

int mid = (left + right) / 2;

如果 left 和 right 很大，可能整数溢出。

更安全写法：

int mid = left + (right - left) / 2;

面试高分回答

NOTE

二分查找用于有序数组，每次取搜索区间中点 mid，将 nums[mid] 与目标值比较。如果相等就返回下标；如果 nums[mid] < target，说明目标只可能在右半区，令 left = mid + 1；如果 nums[mid] > target，说明目标只可能在左半区，令 right = mid - 1。它每轮把搜索范围缩小一半，所以时间复杂度是 O(log n)，迭代实现空间复杂度是 O(1)。边界更新和循环条件是最容易出错的地方。

快排和归并

一句话理解

快排：先选 pivot 分区，再递归排左右。 归并：先递归拆分，再合并两个有序数组。

快排特点

平均时间复杂度：O(n log n)。 最坏时间复杂度：O(n^2)，比如每次 pivot 都选得很差。 空间复杂度：平均 O(log n)，来自递归栈。 稳定性：不稳定。

#include <vector> // 引入 vector 容器
#include <algorithm> // 引入 std::swap
int Partition(std::vector<int>& nums, int left, int right) // 分区函数，把小于 pivot 的放左边
{ // 函数体开始
    int pivot = nums[right]; // 选择最右边元素作为基准值
    int store = left; // store 表示下一个小元素应该放的位置
    for (int i = left; i < right; ++i) // 遍历 left 到 right - 1 的元素
    { // for 循环体开始
        if (nums[i] < pivot) // 如果当前元素小于基准值
        { // if 代码块开始
            std::swap(nums[i], nums[store]); // 把当前元素交换到小元素区域
            ++store; // 小元素区域向右扩大一格
        } // if 代码块结束
    } // for 循环体结束
    std::swap(nums[store], nums[right]); // 把 pivot 放到最终位置
    return store; // 返回 pivot 的最终下标
} // 分区函数结束
void QuickSort(std::vector<int>& nums, int left, int right) // 快速排序函数
{ // 函数体开始
    if (left >= right) // 如果区间长度小于等于 1
    { // if 代码块开始
        return; // 直接返回，因为已经有序
    } // if 代码块结束
    int pivotIndex = Partition(nums, left, right); // 分区并得到 pivot 位置
    QuickSort(nums, left, pivotIndex - 1); // 递归排序 pivot 左边
    QuickSort(nums, pivotIndex + 1, right); // 递归排序 pivot 右边
} // 快速排序函数结束

归并特点

时间复杂度：稳定 O(n log n)。 空间复杂度：O(n)，需要临时数组辅助合并。 稳定性：稳定排序。 适合：链表排序、外部排序、要求稳定性的场景。

#include <vector> // 引入 vector 容器
void Merge(std::vector<int>& nums, int left, int mid, int right) // 合并两个有序区间
{ // 函数体开始
    std::vector<int> temp; // 创建临时数组保存合并结果
    int i = left; // i 指向左半区起点
    int j = mid + 1; // j 指向右半区起点
    while (i <= mid && j <= right) // 当左右两边都还有元素时
    { // while 循环体开始
        if (nums[i] <= nums[j]) // 如果左边元素更小或相等
        { // if 代码块开始
            temp.push_back(nums[i]); // 把左边元素放入临时数组
            ++i; // 左半区指针右移
        } // if 代码块结束
        else // 如果右边元素更小
        { // else 代码块开始
            temp.push_back(nums[j]); // 把右边元素放入临时数组
            ++j; // 右半区指针右移
        } // else 代码块结束
    } // while 循环体结束
    while (i <= mid) // 如果左半区还有剩余元素
    { // while 循环体开始
        temp.push_back(nums[i]); // 把左半区剩余元素加入临时数组
        ++i; // 左半区指针右移
    } // while 循环体结束
    while (j <= right) // 如果右半区还有剩余元素
    { // while 循环体开始
        temp.push_back(nums[j]); // 把右半区剩余元素加入临时数组
        ++j; // 右半区指针右移
    } // while 循环体结束
    for (int k = 0; k < static_cast<int>(temp.size()); ++k) // 遍历临时数组
    { // for 循环体开始
        nums[left + k] = temp[k]; // 把排序结果拷贝回原数组
    } // for 循环体结束
} // 合并函数结束
void MergeSort(std::vector<int>& nums, int left, int right) // 归并排序函数
{ // 函数体开始
    if (left >= right) // 如果区间长度小于等于 1
    { // if 代码块开始
        return; // 直接返回，因为单个元素天然有序
    } // if 代码块结束
    int mid = left + (right - left) / 2; // 计算中点，避免整数溢出
    MergeSort(nums, left, mid); // 递归排序左半区
    MergeSort(nums, mid + 1, right); // 递归排序右半区
    Merge(nums, left, mid, right); // 合并两个已经有序的区间
} // 归并排序函数结束

面试高分回答

TIP

快排和归并都是分治思想。快排是先通过 partition 把数组按 pivot 分成左右两边，再递归处理左右区间，平均 O(n log n)，原地排序，但最坏会退化到 O(n^2)，且不稳定。归并是先递归拆到单个元素，再把两个有序区间合并，时间稳定 O(n log n)，而且稳定，但需要 O(n) 额外空间。工程里数组排序常偏向快排或内省排序，要求稳定或处理链表、外部排序时归并更合适。

堆和 Top K

一句话理解

堆是一棵逻辑上的完全二叉树，通常用数组存储。 Top K 最大元素，常用“大小为 K 的小根堆”解决。

堆是什么？

堆不是内存里的堆。这里说的是数据结构。

大根堆：父节点大于等于子节点，堆顶是最大值。 小根堆：父节点小于等于子节点，堆顶是最小值。

堆用数组存时，如果当前下标是 i：

左孩子 = 2 * i + 1
右孩子 = 2 * i + 2
父节点 = (i - 1) / 2

为什么 Top K 最大值用小根堆？

因为我们只想保留最大的 K 个数。

维护一个大小为 K 的小根堆，堆顶就是“当前 Top K 里面最小的那个”。 新数字来了：

• 堆没满：直接放进去。
• 堆满了，且新数字大于堆顶：弹出堆顶，把新数字放进去。
• 堆满了，且新数字小于等于堆顶：说明它进不了 Top K，直接丢弃。

C++ 代码：找最大的 K 个数

#include <functional> // 引入 std::greater，用来创建小根堆
#include <iostream> // 引入输入输出库
#include <queue> // 引入 priority_queue 优先队列
#include <vector> // 引入 vector 容器
std::vector<int> TopKLargest(const std::vector<int>& nums, int k) // 定义函数，返回最大的 k 个数
{ // 函数体开始
    std::priority_queue<int, std::vector<int>, std::greater<int>> heap; // 定义小根堆，堆顶是当前最小值
    for (int num : nums) // 遍历数组中的每个数字
    { // for 循环体开始
        if (static_cast<int>(heap.size()) < k) // 如果堆里元素数量还不到 k 个
        { // if 代码块开始
            heap.push(num); // 直接把当前数字放入堆
        } // if 代码块结束
        else if (num > heap.top()) // 如果堆已满，并且当前数字大于堆顶
        { // else if 代码块开始
            heap.pop(); // 弹出当前 Top K 里最小的那个数
            heap.push(num); // 把更大的当前数字加入堆
        } // else if 代码块结束
    } // for 循环体结束
    std::vector<int> result; // 创建结果数组
    while (!heap.empty()) // 当堆不为空时继续取数
    { // while 循环体开始
        result.push_back(heap.top()); // 把堆顶元素加入结果数组
        heap.pop(); // 弹出堆顶元素
    } // while 循环体结束
    return result; // 返回最大的 k 个数，顺序不一定是从大到小
} // 函数体结束
int main() // 程序入口函数
{ // main 函数体开始
    std::vector<int> nums = {7, 1, 9, 3, 8, 2, 10}; // 创建测试数组
    std::vector<int> result = TopKLargest(nums, 3); // 查找最大的 3 个数
    for (int num : result) // 遍历结果数组
    { // for 循环体开始
        std::cout << num << " "; // 输出当前结果数字
    } // for 循环体结束
    return 0; // 程序正常结束
} // main 函数体结束

复杂度

如果数组长度是 n，要找最大的 k 个：

时间复杂度：O(n log k) 因为每个元素最多进出大小为 k 的堆。

空间复杂度：O(k) 因为堆里最多只保存 k 个元素。

IMPORTANT

面试高分回答

堆是一种满足堆性质的完全二叉树，通常用数组实现。大根堆堆顶是最大值，小根堆堆顶是最小值，插入和删除堆顶都需要调整堆，复杂度是 O(log n)。Top K 最大元素常用大小为 K 的小根堆：堆里始终保存当前最大的 K 个数，堆顶是这 K 个数里最小的，如果新元素比堆顶大，就替换堆顶，否则丢弃。这样时间复杂度是 O(n log k)，空间复杂度是 O(k)。

动态规划思想

一句话理解

动态规划就是：把大问题拆成小问题，把小问题答案存起来，再用小答案推出大答案，避免重复计算。

什么时候想到 DP？

看到这几类题，要敏感：

• 求最值：最大收益、最短路径、最小花费。
• 求方案数：有多少种走法、有多少种组合。
• 求可行性：能不能凑出某个数。
• 子序列、路径、背包、爬楼梯。

DP 五步法

1. 定义状态：dp[i] 到底表示什么。
2. 写转移：dp[i] 从哪些旧状态推出来。
3. 初始化：最小规模的答案是什么。
4. 遍历顺序：保证算当前状态时，依赖的旧状态已经算过。
5. 返回答案：最终要的是 dp[n] 还是某个最大值。

例子：爬楼梯

一次可以爬 1 阶或 2 阶，问爬到第 n 阶有多少种方法。

状态定义：

dp[i] 表示爬到第 i 阶的方法数

状态转移：

dp[i] = dp[i - 1] + dp[i - 2]

因为到第 i 阶只有两种来源：

• 从第 i - 1 阶爬 1 阶上来。
• 从第 i - 2 阶爬 2 阶上来。

C++ 代码

#include <iostream> // 引入输入输出库
#include <vector> // 引入 vector 容器
int ClimbStairs(int n) // 定义爬楼梯函数，返回爬到第 n 阶的方法数
{ // 函数体开始
    if (n <= 0) // 如果楼梯阶数小于等于 0
    { // if 代码块开始
        return 0; // 返回 0，表示没有有效爬法
    } // if 代码块结束
    if (n == 1) // 如果只有 1 阶
    { // if 代码块开始
        return 1; // 只有一种爬法
    } // if 代码块结束
    std::vector<int> dp(n + 1, 0); // 创建 dp 数组，dp[i] 表示爬到第 i 阶的方法数
    dp[1] = 1; // 初始化第 1 阶的方法数
    dp[2] = 2; // 初始化第 2 阶的方法数
    for (int i = 3; i <= n; ++i) // 从第 3 阶开始向后计算
    { // for 循环体开始
        dp[i] = dp[i - 1] + dp[i - 2]; // 当前方法数来自前一阶和前两阶
    } // for 循环体结束
    return dp[n]; // 返回爬到第 n 阶的方法数
} // 函数体结束
int main() // 程序入口函数
{ // main 函数体开始
    int n = 5; // 定义楼梯阶数
    int answer = ClimbStairs(n); // 调用动态规划函数
    std::cout << answer << std::endl; // 输出答案，n 为 5 时结果是 8
    return 0; // 程序正常结束
} // main 函数体结束

复杂度

时间复杂度：O(n)，因为从 3 到 n 算了一遍。 空间复杂度：O(n)，因为用了 dp 数组。

这个题还能优化成 O(1) 空间，因为每次只依赖前两个状态。

面试高分回答

TIP

动态规划适合有最优子结构和重叠子问题的问题。它的核心不是套公式，而是定义状态，比如 dp[i] 表示什么，然后找到状态之间的转移关系，再确定初始化和遍历顺序。暴力递归会反复计算相同子问题，而 DP 把子问题答案存下来，所以能把指数级重复搜索优化成多项式复杂度。DP 题最重要的是状态定义，状态定义清楚了，转移方程通常就自然出来了。

A* 寻路

一句话理解

A* 是“带方向感的最短路算法”。它不像 BFS 那样一圈一圈盲目扩散，而是每次优先选择“看起来最有希望到终点”的格子。

核心公式：

f(n) = g(n) + h(n)

g(n)：从起点走到当前点的真实代价。 h(n)：从当前点估计走到终点的代价。 f(n)：综合评分，A* 每次从 OpenSet 里取 f 最小的点继续搜索。

A* 怎么走

1. 把起点放进 OpenSet。
2. 每次取出 f 最小的点。
3. 如果这个点是终点，就通过 parent 回溯路径。
4. 否则检查它的上下左右邻居。
5. 如果发现一条到邻居更短的路，就更新邻居的 g / h / f / parent。
6. 搜索过的点放进 ClosedSet，避免重复处理。

C++ 核心代码

#include <algorithm> // 使用 reverse 反转最终路径
#include <cmath> // 使用 abs 计算曼哈顿距离
#include <queue> // 使用 priority_queue 实现 OpenSet
#include <vector> // 使用 vector 存地图、代价表和路径
using namespace std; // 为了示例简洁，直接使用标准命名空间
struct Point { int x; int y; }; // 表示一个格子坐标
struct Node { int x; int y; int g; int h; int f; }; // 表示 A* 搜索中的节点
struct Compare { // priority_queue 的比较规则
    bool operator()(const Node& a, const Node& b) const { return a.f > b.f; } // f 小的节点优先弹出
}; // 比较器结束
int H(Point a, Point b) { return abs(a.x - b.x) + abs(a.y - b.y); } // 曼哈顿距离启发函数
vector<Point> AStar(vector<vector<int>>& grid, Point start, Point end) { // 在网格地图上执行 A*
    int rows = grid.size(); // 地图行数
    int cols = grid[0].size(); // 地图列数
    const int INF = 1e9; // 表示一个很大的初始代价
    priority_queue<Node, vector<Node>, Compare> open; // OpenSet：等待探索的节点
    vector<vector<int>> g(rows, vector<int>(cols, INF)); // 记录起点到每个格子的最小真实代价
    vector<vector<bool>> closed(rows, vector<bool>(cols, false)); // ClosedSet：记录已经处理过的格子
    vector<vector<Point>> parent(rows, vector<Point>(cols, {-1, -1})); // 记录路径父节点
    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; // 四方向移动
    g[start.y][start.x] = 0; // 起点到自己的代价是 0
    open.push({start.x, start.y, 0, H(start, end), H(start, end)}); // 把起点加入 OpenSet
    while (!open.empty()) { // 只要还有可探索节点就继续
        Node cur = open.top(); // 取出当前 f 最小的节点
        open.pop(); // 从 OpenSet 中移除它
        if (closed[cur.y][cur.x]) continue; // 如果已经处理过，就跳过
        closed[cur.y][cur.x] = true; // 标记当前节点已经处理
        if (cur.x == end.x && cur.y == end.y) { // 如果到达终点
            vector<Point> path; // 创建最终路径数组
            Point p = end; // 从终点开始回溯
            while (p.x != -1) { // 只要父节点还存在
                path.push_back(p); // 把当前点加入路径
                p = parent[p.y][p.x]; // 跳到父节点
            } // 回溯结束
            reverse(path.begin(), path.end()); // 路径反转成从起点到终点
            return path; // 返回找到的路径
        } // 终点处理结束
        for (auto& d : dirs) { // 遍历上下左右四个方向
            int nx = cur.x + d[0]; // 计算邻居 x 坐标
            int ny = cur.y + d[1]; // 计算邻居 y 坐标
            if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) continue; // 越界则跳过
            if (grid[ny][nx] == 1 || closed[ny][nx]) continue; // 障碍或已处理则跳过
            int newG = cur.g + 1; // 当前点走到邻居的总代价
            if (newG < g[ny][nx]) { // 如果找到更短路径
                g[ny][nx] = newG; // 更新邻居的最小 g 值
                parent[ny][nx] = {cur.x, cur.y}; // 记录邻居从当前点走来
                int h = H({nx, ny}, end); // 计算邻居到终点的估计代价
                open.push({nx, ny, newG, h, newG + h}); // 把邻居加入 OpenSet
            } // 更新邻居结束
        } // 遍历邻居结束
    } // 搜索循环结束
    return {}; // 没有找到路径，返回空数组
} // AStar 函数结束

面试高分说法

NOTE

A* 的本质是 Dijkstra 加启发函数。g 保证当前路径成本真实，h 提供朝终点搜索的方向感，f = g + h 决定搜索优先级。只要 h 不高估真实距离，A* 就能保证找到最短路径；在网格寻路里常用曼哈顿距离或欧几里得距离作为启发函数。复杂度通常可按 O(E log V) 理解，实际性能取决于启发函数好不好、地图障碍分布以及 OpenSet 的实现。

进程和线程

一句话理解

进程是“资源容器”，线程是“执行路线”。 一个程序运行起来就是一个进程；一个进程里可以有多个线程一起干活。

核心区别

进程有独立的地址空间、堆、全局变量、文件句柄等资源。不同进程之间默认互相隔离，一个进程崩了通常不会直接破坏另一个进程。

线程属于某个进程。同一个进程里的多个线程共享代码段、堆、全局变量、文件句柄，但每个线程都有自己的栈、寄存器上下文和执行位置。

所以面试里常说：

进程：操作系统分配资源的基本单位
线程：CPU 调度执行的基本单位

为什么线程更轻

创建进程时，系统要准备独立地址空间、资源表、句柄表等，成本更高。 创建线程时，它复用所属进程的大部分资源，只需要自己的栈和执行上下文，所以更轻。

但轻也有代价：线程共享内存，多个线程同时改同一份数据，容易出现数据竞争，所以要用 mutex、atomic 等同步手段。

C++ 线程共享数据示例

#include <iostream> // 引入 cout 用于输出结果
#include <mutex> // 引入 mutex 和 lock_guard 用于加锁
#include <thread> // 引入 thread 用于创建线程
using namespace std; // 使用标准命名空间，方便示例书写
int counter = 0; // 定义全局变量，多个线程会共享这个变量
mutex counterMutex; // 定义互斥锁，用来保护 counter
void AddWork() { // 定义线程要执行的函数
    for (int i = 0; i < 100000; ++i) { // 每个线程循环累加十万次
        lock_guard<mutex> lock(counterMutex); // 自动加锁，离开作用域会自动解锁
        ++counter; // 修改共享变量，必须放在锁保护范围内
    } // 循环结束
} // 线程函数结束
int main() { // 程序入口函数
    thread t1(AddWork); // 创建第一个线程执行 AddWork
    thread t2(AddWork); // 创建第二个线程执行 AddWork
    t1.join(); // 等待第一个线程执行完
    t2.join(); // 等待第二个线程执行完
    cout << counter << endl; // 输出最终结果，正常应该是 200000
    return 0; // 返回 0 表示程序正常结束
} // main 函数结束

面试高分回答

IMPORTANT

进程之间隔离性好，安全稳定，但创建、切换、通信成本更高；线程共享进程资源，创建和切换更轻，通信方便，但要处理同步、锁、死锁和数据竞争问题。游戏开发里通常把主逻辑、渲染、Unity API 放主线程，把下载、解压、寻路、日志、资源 IO 等耗时任务放工作线程。

死锁条件

一句话理解

死锁就是：多个线程互相等对方释放资源，结果谁都继续不了。

死锁通常需要四个条件同时成立，少一个就不容易形成死锁。

四个必要条件

1. 互斥条件

某个资源一次只能被一个线程占有。

比如一把 mutex，线程 A 拿到了，线程 B 就只能等。

2. 请求并保持

线程已经拿着一部分资源，同时又去请求新的资源。

比如线程 A 已经拿了 lockA，还想拿 lockB。

3. 不可剥夺

线程已经拿到的资源，不能被别人强行抢走。

锁只能由持有它的线程主动释放。

4. 循环等待

多个线程形成等待环。

线程 A 拿着 lockA，等待 lockB
线程 B 拿着 lockB，等待 lockA

这样 A 等 B，B 等 A，就卡死了。

容易死锁的代码

#include <mutex> // 引入 mutex 互斥锁
using namespace std; // 使用标准命名空间
mutex lockA; // 定义第一把锁
mutex lockB; // 定义第二把锁
void ThreadA() { // 线程 A 执行的函数
    lock_guard<mutex> guardA(lockA); // 线程 A 先拿 lockA
    lock_guard<mutex> guardB(lockB); // 线程 A 再等 lockB
} // 线程 A 函数结束
void ThreadB() { // 线程 B 执行的函数
    lock_guard<mutex> guardB(lockB); // 线程 B 先拿 lockB
    lock_guard<mutex> guardA(lockA); // 线程 B 再等 lockA
} // 线程 B 函数结束

这个代码危险点在于：两个线程加锁顺序相反。

线程 A 是：

lockA -> lockB

线程 B 是：

lockB -> lockA

如果 A 拿到 lockA，B 拿到 lockB，接下来它们就互相等待。

避免死锁的写法

最常用方法：所有地方都按统一顺序加锁，或者使用 std::scoped_lock 一次性锁多把锁。

#include <mutex> // 引入 mutex 和 scoped_lock
using namespace std; // 使用标准命名空间
mutex lockA; // 定义第一把锁
mutex lockB; // 定义第二把锁
void SafeWork() { // 定义安全的多锁操作函数
    scoped_lock lock(lockA, lockB); // 一次性锁住 lockA 和 lockB，避免反向等待
} // 函数结束时 scoped_lock 自动释放两把锁

std::scoped_lock 内部会用避免死锁的方式处理多把锁，比手动一把一把锁更安全。

面试高分回答

IMPORTANT

死锁产生需要四个必要条件：互斥、请求并保持、不可剥夺、循环等待。工程中最常见的避免方式是破坏循环等待，也就是规定统一加锁顺序；另外也可以缩小锁粒度、减少持锁时间、使用 try_lock 或超时机制、用 std::lock / scoped_lock 一次性获取多把锁。面试时重点强调：死锁不是锁本身的问题，而是资源申请顺序和等待关系形成了环。

虚拟内存

一句话理解

虚拟内存就是：程序看到的地址不是真实物理内存地址，而是操作系统给每个进程“假装”出来的一片连续地址空间。

程序访问内存时，大概流程是：

虚拟地址 -> MMU 查询页表 -> 物理地址 -> 访问真正的 RAM

为什么需要虚拟内存

第一，隔离进程。 每个进程都有自己的虚拟地址空间，A 进程不能随便访问 B 进程的内存，所以更安全。

第二，让程序感觉内存连续。 即使物理内存可能是碎片化的，程序看到的仍然可以是连续地址。

第三，支持按需加载。 程序不需要一启动就把所有代码和数据放进内存，用到哪一页，再加载哪一页。

第四，支持缺页异常。 如果访问的页面暂时不在物理内存中，会触发 page fault，操作系统把需要的页从磁盘或文件调入内存。

页表是什么

页表可以理解成一张映射表：

虚拟页号 -> 物理页号

比如：

虚拟地址 0x2000
先找到虚拟页号
页表查到它对应物理页 5
再加上页内偏移
得到真正的物理地址

CPU 里面的 MMU 负责地址翻译。 为了加速翻译，还会有 TLB，它可以理解成“页表缓存”。

C++ 代码观察地址

注意：下面打印出来的是虚拟地址，不是物理地址。

#include <iostream> // 引入输入输出库，用来打印地址
using namespace std; // 使用标准命名空间，简化 cout 写法
int globalValue = 10; // 定义全局变量，通常位于全局数据区
int main() { // 程序入口函数
    int stackValue = 20; // 定义局部变量，通常位于栈区
    int* heapValue = new int(30); // 在堆区申请一个 int 对象
    cout << "global address: " << &globalValue << endl; // 打印全局变量的虚拟地址
    cout << "stack address: " << &stackValue << endl; // 打印栈变量的虚拟地址
    cout << "heap address: " << heapValue << endl; // 打印堆对象的虚拟地址
    delete heapValue; // 释放堆内存，避免内存泄漏
    heapValue = nullptr; // 指针置空，避免变成悬空指针
    return 0; // 返回 0 表示程序正常结束
} // main 函数结束

面试高分回答

NOTE

虚拟内存是操作系统提供的内存抽象。每个进程看到独立、连续的虚拟地址空间，真正访问时由 MMU 根据页表翻译成物理地址。它的好处是进程隔离、内存保护、地址空间连续、按需加载；代价是地址翻译有开销，缺页异常会比较慢。如果频繁缺页或者频繁换页，就会导致程序明显卡顿。

TCP 和 UDP

一句话理解

TCP 追求“可靠、有序、稳定”；UDP 追求“简单、低延迟、实时”。

TCP：我发给你的数据，你必须按顺序收到
UDP：我直接发出去，能不能到、顺序对不对，协议本身不保证

TCP 是什么

TCP 是面向连接的可靠传输协议。通信前要先建立连接，也就是常说的“三次握手”。传输过程中，TCP 会用序号、ACK、重传、流量控制、拥塞控制来保证数据可靠到达。

它的特点是：

面向连接
可靠传输
保证顺序
字节流协议
有重传机制
开销相对更大

注意：TCP 是“字节流”，不是“消息流”。所以 TCP 会有粘包、半包问题，需要业务层自己设计消息长度或分隔符。

UDP 是什么

UDP 是无连接的数据报协议。它不需要三次握手，想发就发。它保留数据报边界，但不保证可靠、不保证顺序，也不保证只收到一次。

它的特点是：

无连接
速度快
延迟低
不保证可靠
不保证顺序
业务自己处理丢包和重传

C# 简单示例

using System.Net.Sockets; // 引入 TcpClient、UdpClient 等网络类
using System.Text; // 引入 Encoding，用来把字符串转成字节数组
public static class NetDemo // 定义一个网络示例类
{ // 类开始
    public static void SendTcp(string host, int port, string msg) // 定义 TCP 发送方法
    { // TCP 方法开始
        using TcpClient client = new TcpClient(host, port); // 创建 TCP 客户端并连接服务器
        using NetworkStream stream = client.GetStream(); // 获取 TCP 连接上的字节流
        byte[] bytes = Encoding.UTF8.GetBytes(msg); // 把字符串消息编码成字节数组
        stream.Write(bytes, 0, bytes.Length); // 通过 TCP 流发送字节数据
    } // TCP 方法结束
    public static void SendUdp(string host, int port, string msg) // 定义 UDP 发送方法
    { // UDP 方法开始
        using UdpClient udp = new UdpClient(); // 创建 UDP 客户端，不需要先建立连接
        byte[] bytes = Encoding.UTF8.GetBytes(msg); // 把字符串消息编码成字节数组
        udp.Send(bytes, bytes.Length, host, port); // 直接把 UDP 数据报发送到目标地址
    } // UDP 方法结束
} // 类结束

游戏开发怎么选

登录、支付、背包、邮件、聊天、配置拉取，这类数据不能丢，通常适合 TCP。

角色移动、战斗同步、帧同步输入、实时语音，这类更关注低延迟，通常适合 UDP，然后业务层自己加：

包序号
ACK
重传
心跳
超时
乱序处理
关键包可靠发送

面试高分回答

IMPORTANT

TCP 和 UDP 的核心区别是可靠性和延迟的取舍。TCP 面向连接，保证可靠和有序，但有握手、确认、重传和拥塞控制，所以延迟和开销更高；UDP 无连接，协议本身不保证可靠和顺序，但延迟低、控制权更灵活。游戏实时同步常用 UDP，是因为旧位置包丢了可以直接用新位置包覆盖，不一定值得等待重传；但登录、支付、背包这类强一致业务更适合 TCP。

三次握手

一句话理解

TCP 三次握手就是：客户端和服务端在真正传数据前，先互相确认“我能发、你能收；你能发、我能收”，并同步双方的初始序列号。

第一次：Client -> Server：SYN
第二次：Server -> Client：SYN + ACK
第三次：Client -> Server：ACK

三次分别做了什么

第一次握手：

Client 发送 SYN，seq = x

意思是：我想和你建立连接，我的初始序列号是 x。 客户端进入 SYN_SENT 状态。

第二次握手：

Server 回复 SYN + ACK，seq = y，ack = x + 1

意思是：我收到你的连接请求了，我也同意连接，我的初始序列号是 y。 服务端进入 SYN_RCVD 状态。

第三次握手：

Client 回复 ACK，ack = y + 1

意思是：我也收到你的确认了，我们可以开始传数据了。 双方进入 ESTABLISHED 状态。

为什么不是两次握手

两次握手只能证明：

客户端能发，服务端能收
服务端能发，客户端能收

但服务端还不知道：客户端是否收到了自己的 SYN + ACK。

如果没有第三次 ACK，服务端可能以为连接建立成功，但客户端其实没收到回复，双方状态就不一致。

还有一个经典问题：网络里可能残留旧的 SYN 包。 如果只有两次握手，服务端可能因为一个旧 SYN 误创建连接，浪费资源。

C# 里怎么触发三次握手

应用层代码一般不会手动发 SYN / ACK，这些由操作系统 TCP 协议栈完成。你调用 Connect 时，底层就会触发三次握手。

using System.Net.Sockets; // 引入 TcpClient 类型
public class TcpConnectDemo // 定义 TCP 连接示例类
{ // 类开始
    public void ConnectServer() // 定义连接服务器的方法
    { // 方法开始
        TcpClient client = new TcpClient(); // 创建 TCP 客户端对象
        client.Connect("127.0.0.1", 9000); // 发起 TCP 连接，底层会执行三次握手
        client.Close(); // 关闭 TCP 连接，释放 socket 资源
    } // 方法结束
} // 类结束

面试高分回答

TIP

TCP 三次握手的核心目的不是单纯“连上”，而是确认双方收发能力、同步初始序列号，并避免历史连接请求造成错误连接。第一次客户端发 SYN，第二次服务端回 SYN+ACK，第三次客户端回 ACK。三次之后双方状态才一致，连接进入 ESTABLISHED，后续才能可靠、有序地传输数据。

粘包半包

一句话理解

粘包半包不是 TCP 出错，而是因为 TCP 是字节流协议，它只保证字节按顺序到达，不保证“一次发送对应一次接收”。

发送端：Send(A) + Send(B)
接收端：可能 Receive(A+B)      这叫粘包
接收端：也可能 Receive(A的一半) 这叫半包

为什么会粘包

TCP 底层会把数据放进发送缓冲区和接收缓冲区。 多条小消息可能被 TCP 合并后一起发出去，接收端一次 Read 就读到了多条消息。

发送：消息 A，消息 B
接收：A + B

这就是粘包。

为什么会半包

一条大消息可能因为网络、缓冲区大小、读取长度限制，被拆成多次收到。

发送：消息 A
接收第一次：A 的前半段
接收第二次：A 的后半段

这就是半包。

怎么解决

核心思路：应用层自己定义协议格式，接收端按协议拆包。

最常见方案是：

包头长度 + 包体内容

例如：

[4字节长度][真正消息内容]

接收端逻辑：

收到字节 -> 放进缓存 -> 先看够不够 4 字节包头
够包头 -> 读出 body 长度
够完整 body -> 拆出一包
不够完整 body -> 等下一次 Receive

C# 长度前缀拆包示例

using System; // 引入基础类型
using System.Collections.Generic; // 引入 List 集合
using System.Net; // 引入 IPAddress 处理网络字节序
using System.Text; // 引入 Encoding 处理字符串编码
public sealed class PacketCodec // 定义一个 TCP 拆包工具类
{ // 类开始
    private readonly List<byte> _buffer = new List<byte>(); // 保存未解析完的接收缓存
    public static byte[] Encode(string message) // 把一条字符串消息编码成完整数据包
    { // Encode 方法开始
        byte[] body = Encoding.UTF8.GetBytes(message); // 把消息内容转成 UTF8 字节
        int netLength = IPAddress.HostToNetworkOrder(body.Length); // 把包体长度转成网络字节序
        byte[] header = BitConverter.GetBytes(netLength); // 把长度写成 4 字节包头
        byte[] packet = new byte[header.Length + body.Length]; // 创建完整数据包数组
        Buffer.BlockCopy(header, 0, packet, 0, header.Length); // 把包头复制到数据包开头
        Buffer.BlockCopy(body, 0, packet, header.Length, body.Length); // 把包体复制到包头后面
        return packet; // 返回完整数据包
    } // Encode 方法结束
    public List<string> Feed(byte[] data, int count) // 输入本次 Receive 收到的字节并尝试拆包
    { // Feed 方法开始
        for (int i = 0; i < count; i++) // 遍历本次收到的有效字节
        { // for 循环开始
            _buffer.Add(data[i]); // 把收到的字节追加到缓存末尾
        } // for 循环结束
        List<string> messages = new List<string>(); // 保存本次成功拆出来的完整消息
        while (true) // 循环尝试从缓存里拆出多条消息
        { // while 循环开始
            if (_buffer.Count < 4) break; // 如果连 4 字节包头都不够，就等待下次接收
            byte[] header = _buffer.GetRange(0, 4).ToArray(); // 取出前 4 字节作为长度包头
            int bodyLength = IPAddress.NetworkToHostOrder(BitConverter.ToInt32(header, 0)); // 解析包体长度
            if (bodyLength < 0 || bodyLength > 1024 * 1024) throw new Exception("Invalid packet length"); // 防止非法长度攻击
            if (_buffer.Count < 4 + bodyLength) break; // 如果包体还没收完整，就等待下次接收
            byte[] body = _buffer.GetRange(4, bodyLength).ToArray(); // 取出完整包体内容
            _buffer.RemoveRange(0, 4 + bodyLength); // 从缓存中移除已经解析完成的数据包
            messages.Add(Encoding.UTF8.GetString(body)); // 把包体字节转成字符串并加入结果
        } // while 循环结束
        return messages; // 返回本次拆出来的所有完整消息
    } // Feed 方法结束
} // 类结束

面试高分回答

IMPORTANT

TCP 是面向字节流的协议，没有消息边界，所以一次 Send 不一定对应一次 Receive。粘包是多条业务消息被一次读到，半包是一条业务消息被多次读到。解决方式不是依赖 TCP，而是在应用层设计协议，比如长度前缀、固定包长、分隔符。游戏网络里通常用“包头长度 + 消息 ID + 包体”的二进制协议，接收端维护一个缓存区，循环判断是否够一整包，够就拆出来分发，不够就继续等待下一次网络数据。

HTTP 和 WebSocket

一句话理解

HTTP 像“发消息问客服”：客户端问一次，服务端答一次。 WebSocket 像“打电话”：连接建立后，双方都可以随时说话。

HTTP 是什么

HTTP 是应用层的请求响应协议，典型流程是：

Client 发 Request
Server 回 Response

它适合：

登录
支付
拉配置
请求排行榜
下载资源清单
普通 REST API

HTTP 的特点是简单、通用、生态成熟，但它天然是客户端主动请求，服务端不能很自然地持续主动推送。如果想实时更新，只能轮询或长轮询，开销会更高。

WebSocket 是什么

WebSocket 是建立在 TCP 上的长连接协议。它一开始会通过 HTTP 发起握手：

HTTP Upgrade: websocket

升级成功后，就不再是普通 HTTP 请求响应模式，而是变成一条持续存在的双向连接：

Client 可以主动发
Server 也可以主动推

它适合：

聊天
实时通知
匹配状态
房间状态同步
网页游戏实时通信
弱实时战斗消息

C# 简单示例

using System; // 引入 Uri 等基础类型
using System.Net.Http; // 引入 HttpClient 用于 HTTP 请求
using System.Net.WebSockets; // 引入 ClientWebSocket 用于 WebSocket
using System.Text; // 引入 Encoding 用于字符串和字节转换
using System.Threading; // 引入 CancellationToken
using System.Threading.Tasks; // 引入 Task 异步任务
public class NetworkDemo // 定义网络示例类
{ // 类开始
    public async Task UseHttp() // 定义 HTTP 请求示例方法
    { // HTTP 方法开始
        using HttpClient client = new HttpClient(); // 创建 HTTP 客户端
        string json = await client.GetStringAsync("https://example.com/config.json"); // 发起一次请求并等待响应
        Console.WriteLine(json); // 输出服务端返回的数据
    } // HTTP 方法结束
    public async Task UseWebSocket() // 定义 WebSocket 示例方法
    { // WebSocket 方法开始
        using ClientWebSocket socket = new ClientWebSocket(); // 创建 WebSocket 客户端
        await socket.ConnectAsync(new Uri("wss://example.com/ws"), CancellationToken.None); // 建立 WebSocket 长连接
        byte[] data = Encoding.UTF8.GetBytes("hello"); // 把要发送的字符串转成字节数组
        await socket.SendAsync(data, WebSocketMessageType.Text, true, CancellationToken.None); // 通过 WebSocket 发送消息
        byte[] buffer = new byte[1024]; // 创建接收缓冲区
        WebSocketReceiveResult result = await socket.ReceiveAsync(buffer, CancellationToken.None); // 等待服务端推送消息
        string msg = Encoding.UTF8.GetString(buffer, 0, result.Count); // 把收到的字节转成字符串
        Console.WriteLine(msg); // 输出收到的 WebSocket 消息
    } // WebSocket 方法结束
} // 类结束

面试高分回答

WARNING

HTTP 和 WebSocket 都是应用层协议，底层通常都跑在 TCP 上。HTTP 是请求响应模型，适合普通接口、资源拉取和无状态业务；WebSocket 先通过 HTTP Upgrade 完成握手，之后保持一条长连接，实现全双工通信，适合实时推送和频繁双向消息。WebSocket 的优势是实时性好、减少频繁建连和轮询开销，但需要处理心跳、断线重连、消息序号、状态恢复等问题。

帧同步和状态同步

一句话理解

帧同步同步的是“玩家输入”，状态同步同步的是“游戏结果”。

帧同步：大家拿到同一帧输入，然后各自本地计算
状态同步：服务端算出权威结果，再把状态发给客户端

帧同步是什么

帧同步的核心是：网络只传输入，不传完整状态。

比如第 100 帧：

玩家 A 输入：向右移动
玩家 B 输入：释放技能
服务器收集输入
广播给所有客户端
所有客户端在第 100 帧执行同样的输入

只要所有客户端初始状态一样、输入顺序一样、逻辑计算完全确定，最后结果就应该一样。

它最怕的是“不确定性”，比如：

浮点误差
随机数不一致
遍历顺序不一致
不同平台数学库结果不同
某个客户端漏了一帧输入

所以帧同步常用于 RTS、战棋、房间制对战等。

状态同步是什么

状态同步的核心是：服务端权威计算，客户端只负责表现。

客户端会把输入或操作请求发给服务端：

我要移动
我要攻击
我要释放技能

服务端判断是否合法，然后计算最终结果：

角色位置
血量
Buff
技能状态
怪物状态

再把这些状态快照同步给客户端。客户端收到后做插值、预测、外推、校正，让画面看起来平滑。

C# 简化示例

public struct InputFrame // 定义一帧输入数据
{ // 结构体开始
    public int Tick; // 当前输入属于第几帧
    public int PlayerId; // 输入来自哪个玩家
    public float MoveX; // 水平方向输入
    public float MoveY; // 垂直方向输入
    public bool Skill; // 是否释放技能
} // 结构体结束
public struct StateSnapshot // 定义状态同步快照
{ // 结构体开始
    public int Tick; // 快照对应的服务器逻辑帧
    public int EntityId; // 实体 ID
    public float X; // 服务端计算后的 X 坐标
    public float Y; // 服务端计算后的 Y 坐标
    public int Hp; // 服务端计算后的血量
} // 结构体结束
public class SyncExample // 定义同步示例类
{ // 类开始
    public void LockstepApply(InputFrame input) // 帧同步处理输入
    { // 方法开始
        if (input.Skill) // 判断这一帧是否释放技能
        { // if 开始
            // 在同一 Tick 执行技能逻辑，所有客户端必须算出相同结果 // 解释帧同步要求
        } // if 结束
    } // 方法结束
    public void ApplySnapshot(StateSnapshot snapshot) // 状态同步应用快照
    { // 方法开始
        // 客户端把角色表现插值到服务端下发的位置 // 解释状态同步表现层处理
    } // 方法结束
} // 类结束

面试高分回答

CAUTION

帧同步传的是输入，要求所有客户端用相同初始状态和相同输入序列跑出相同结果，所以它流量小、适合单位多的 RTS，但对确定性要求很高，浮点、随机数、执行顺序都要严格控制。状态同步传的是服务端权威状态，客户端做预测、插值和校正，安全性和一致性更好，适合 MMO、FPS、动作游戏，但流量更大，也要处理延迟、抖动、弱网和回滚校正。

客户端预测

一句话理解

客户端预测就是：玩家按下移动键后，客户端不等服务器确认，先让角色本地动起来；等服务器权威结果回来，如果不一致，再做校正。

本地先动 -> 输入发服务器 -> 服务器返回权威状态 -> 客户端回滚并重放未确认输入

为什么需要客户端预测

如果不预测，玩家每次移动都要等一次网络往返：

按键 -> 发服务器 -> 服务器处理 -> 返回结果 -> 客户端移动

假设延迟 100ms，角色就会明显“慢半拍”。 预测的目的就是隐藏这段延迟，让操作立刻有反馈。

核心流程

客户端每个输入都带一个序号：

seq = 101，向右移动
seq = 102，继续向右
seq = 103，停止

客户端本地先执行这些输入，并把它们存起来。 服务端处理后返回：

我已经处理到 seq = 101
你的权威位置是 x = 9.7

客户端收到后：

丢掉已经确认的输入 101
把位置修正到服务端的 x = 9.7
重新播放还没确认的输入 102、103

C# 简化代码

using System.Collections.Generic; // 引入 List，用来保存未确认输入
public struct InputCommand // 定义客户端输入命令
{ // 输入命令结构体开始
    public int Sequence; // 输入序号，用来判断服务器确认到哪一条
    public float MoveX; // 水平移动输入，例如 -1、0、1
    public float DeltaTime; // 当前输入对应的时间间隔
} // 输入命令结构体结束
public struct ServerSnapshot // 定义服务器权威快照
{ // 服务器快照结构体开始
    public int LastAckSequence; // 服务器已经处理到的输入序号
    public float X; // 服务器计算出来的权威 X 坐标
} // 服务器快照结构体结束
public sealed class ClientPrediction // 定义客户端预测类
{ // 客户端预测类开始
    private readonly List<InputCommand> _pendingInputs = new List<InputCommand>(); // 保存还没被服务器确认的输入
    private int _nextSequence = 1; // 下一个输入序号
    private float _predictedX; // 客户端当前预测出来的位置
    private const float Speed = 5f; // 移动速度
    public float PredictedX => _predictedX; // 对外暴露当前预测位置
    public InputCommand CreateAndPredict(float moveX, float deltaTime) // 创建输入并立即本地预测
    { // CreateAndPredict 方法开始
        InputCommand command = new InputCommand { Sequence = _nextSequence++, MoveX = moveX, DeltaTime = deltaTime }; // 创建带序号的输入
        ApplyInput(command); // 客户端先执行输入，保证手感立即响应
        _pendingInputs.Add(command); // 保存输入，等待服务器确认后用于回滚重放
        return command; // 返回输入命令，外部可以把它发送给服务器
    } // CreateAndPredict 方法结束
    public void ReceiveServerSnapshot(ServerSnapshot snapshot) // 收到服务器权威快照
    { // ReceiveServerSnapshot 方法开始
        _predictedX = snapshot.X; // 先把客户端位置对齐到服务器权威位置
        _pendingInputs.RemoveAll(input => input.Sequence <= snapshot.LastAckSequence); // 删除服务器已经确认处理过的输入
        for (int i = 0; i < _pendingInputs.Count; i++) // 遍历剩下还没确认的输入
        { // for 循环开始
            ApplyInput(_pendingInputs[i]); // 从服务器权威位置开始重新播放未确认输入
        } // for 循环结束
    } // ReceiveServerSnapshot 方法结束
    private void ApplyInput(InputCommand command) // 执行一条移动输入
    { // ApplyInput 方法开始
        _predictedX += command.MoveX * Speed * command.DeltaTime; // 根据输入、速度和时间推进预测位置
    } // ApplyInput 方法结束
} // 客户端预测类结束

面试高分回答

NOTE

客户端预测是为了降低操作延迟。客户端收到玩家输入后立即本地模拟，同时把输入带序号发给服务器；服务器做权威校验和模拟，再返回包含最后处理输入序号的快照。客户端收到快照后丢弃已确认输入，把状态回滚到服务器权威状态，再重放未确认输入。这样既保证手感，又最终服从服务端权威。实际项目里还要配合插值、平滑校正、输入重发、序号 ACK、误差阈值和反作弊校验。

断线重连

一句话理解

断线重连不是“socket 再连一次”这么简单，而是：

发现断线 -> 重新连接 -> 重新鉴权 -> 恢复会话 -> 同步最新状态 -> 回到游戏

为什么需要断线重连

网络游戏里，玩家可能因为弱网、切后台、电梯、WiFi/4G 切换导致连接中断。 如果直接踢回登录页，体验很差。所以客户端要尽量自动恢复连接。

但重连成功后，客户端本地状态可能已经过期了，所以必须向服务端重新同步：

角色位置
血量
Buff
房间状态
战斗帧号
背包变化
未读消息
任务进度

核心流程

客户端平时通过心跳检测连接是否还活着：

Client -> ping
Server -> pong

如果超过一段时间没收到 pong，就认为断线：

lastPongTime 超时
socket 异常
发送失败
服务器主动断开

然后进入重连状态：

关闭旧连接
等待一小段时间
重新 Connect
发送 token / sessionId
服务端验证身份
服务端返回最新快照
客户端恢复场景和 UI

C# 简化代码

using System; // 引入 Action 事件类型
using System.Collections; // 引入 IEnumerator 用于 Unity 协程
using UnityEngine; // 引入 Unity 的 MonoBehaviour 和 Time
public sealed class ReconnectManager : MonoBehaviour // 定义断线重连管理器
{ // 类开始
    private enum NetState { Connected, Disconnected, Reconnecting } // 定义网络状态枚举
    private NetState _state = NetState.Connected; // 当前网络状态
    private float _lastPongTime; // 最后一次收到服务器心跳回复的时间
    private int _retryCount; // 当前已经重试的次数
    private const float HeartbeatTimeout = 10f; // 心跳超时时间
    private const int MaxRetryCount = 5; // 最大重连次数
    public Action OnReconnectSuccess; // 重连成功事件
    public Action OnReconnectFailed; // 重连失败事件
    private void Start() // Unity 启动时调用
    { // Start 开始
        _lastPongTime = Time.realtimeSinceStartup; // 初始化最后心跳时间
    } // Start 结束
    private void Update() // Unity 每帧调用
    { // Update 开始
        if (_state != NetState.Connected) return; // 如果不是连接状态，就不检测心跳
        if (Time.realtimeSinceStartup - _lastPongTime < HeartbeatTimeout) return; // 如果还没超时，就继续等待
        OnDisconnected(); // 心跳超时，进入断线流程
    } // Update 结束
    public void OnReceivePong() // 收到服务器 pong 时调用
    { // OnReceivePong 开始
        _lastPongTime = Time.realtimeSinceStartup; // 更新最后心跳时间
    } // OnReceivePong 结束
    private void OnDisconnected() // 处理断线
    { // OnDisconnected 开始
        if (_state == NetState.Reconnecting) return; // 如果已经在重连中，就不要重复启动
        _state = NetState.Reconnecting; // 切换到重连状态
        _retryCount = 0; // 重置重试次数
        StartCoroutine(ReconnectLoop()); // 启动重连协程
    } // OnDisconnected 结束
    private IEnumerator ReconnectLoop() // 重连循环协程
    { // ReconnectLoop 开始
        while (_retryCount < MaxRetryCount) // 只要没超过最大重试次数
        { // while 开始
            _retryCount++; // 重试次数加一
            float delay = Mathf.Min(1f * _retryCount, 5f); // 计算退避等待时间
            yield return new WaitForSecondsRealtime(delay); // 等待一段真实时间，不受 timeScale 影响
            bool connected = TryConnect(); // 尝试重新建立网络连接
            if (!connected) continue; // 如果连接失败，就进入下一轮重试
            bool authed = SendReconnectAuth(); // 发送 token 或 sessionId 做重连鉴权
            if (!authed) continue; // 如果鉴权失败，就继续重试
            RequestLatestSnapshot(); // 请求服务端最新状态快照
            _state = NetState.Connected; // 切回已连接状态
            _lastPongTime = Time.realtimeSinceStartup; // 重置心跳时间
            OnReconnectSuccess?.Invoke(); // 通知外部重连成功
            yield break; // 结束重连协程
        } // while 结束
        _state = NetState.Disconnected; // 多次失败后切到断线状态
        OnReconnectFailed?.Invoke(); // 通知外部重连失败
    } // ReconnectLoop 结束
    private bool TryConnect() // 尝试连接服务器
    { // TryConnect 开始
        return true; // 示例代码直接返回成功，真实项目里这里连接 socket
    } // TryConnect 结束
    private bool SendReconnectAuth() // 发送重连鉴权请求
    { // SendReconnectAuth 开始
        return true; // 示例代码直接返回成功，真实项目里发送 token 和 sessionId
    } // SendReconnectAuth 结束
    private void RequestLatestSnapshot() // 请求最新服务器状态
    { // RequestLatestSnapshot 开始
        Debug.Log("Request room, player and battle snapshot."); // 示例输出恢复状态的动作
    } // RequestLatestSnapshot 结束
} // 类结束

面试高分回答

IMPORTANT

断线重连的核心不是重新建立连接，而是恢复一致性。客户端通过心跳和 socket 异常判断断线，进入重连状态后使用指数退避避免疯狂请求；重连成功后要用 token 或 sessionId 做鉴权，让服务端恢复原会话；最后客户端拉取最新快照，恢复房间、角色、战斗和 UI 状态。对于战斗类游戏，还要处理未确认输入、服务器帧号、状态校正和超时失败回退。