阿Q技术站

深浅色

米哈游一面凉经下 ​

来源：https://www.nowcoder.com/feed/main/detail/7f28c235a0134b4a9be9fea52efe9551

1、静态局部变量的生命周期？ ​

使用 static 关键字声明的局部变量，定义在函数或块作用域内。

作用域：局限于声明的块（如函数内）。

存储位置：静态存储区（全局数据段），而不是栈。

生命周期：从程序开始运行到程序结束。

与全局变量和静态全局变量类似，静态局部变量在程序启动时分配内存，在程序退出时销毁。

2、在已知地址上怎么创建对象？ ​

在 C++ 中，在已知地址上创建对象通常涉及在指定内存位置构造对象，而不是通过 new 分配新内存。C++ 提供了**置位构造（Placement New）**机制来实现这一点。

什么是置位构造（Placement New）？ ​

置位构造是一种特殊的 new 操作符变体，允许在用户提供的内存地址上构造对象，而不分配新内存。

头文件：<new>，提供operator new的重载。

语法：new (address) Type(args...);

  • address：已分配的内存地址。
  • Type：要构造的类型。
  • args：构造函数参数。

置位构造的实现原理 ​

内存分配：

  • 用户负责提供合法的内存地址（如通过 malloc、数组、静态缓冲区）。
  • 内存必须足够大且正确对齐。

对象构造：

  • 置位 new 调用类型的构造函数，在指定地址初始化对象。
  • 不分配新内存，仅执行构造逻辑。

销毁：

  • 需手动调用析构函数（obj->~Type()）。
  • 内存释放由用户管理（若需要）。

与普通 new 的对比 ​

特性普通 new置位 new
内存分配自动分配（堆）用户提供地址
构造调用构造函数调用构造函数
释放delete 自动处理手动析构 + 释放
灵活性固定堆分配可自定义地址

3、tcp udp区别？tcp可靠性体现在？tcp包传输过来 怎么到应用层体现？ ​

TCP 和 UDP 的区别 ​

特性TCP (Transmission Control Protocol)UDP (User Datagram Protocol)
连接性面向连接（需建立连接）无连接（直接发送）
数据传输流式传输（字节流，无边界）数据报（独立数据包）
可靠性可靠（重传、排序、错误检查）不可靠（无重传、无序）
头部开销较大（20-60 字节）较小（8 字节）
速度较慢（因可靠性机制）较快（无额外控制）
拥塞控制有（滑动窗口、流量控制）无
应用场景文件传输、HTTP、邮件视频流、DNS、实时游戏

TCP 的可靠性体现在哪里？ ​

连接管理 ​
  • 三次握手：确保双方准备好通信。
  • 四次挥手：确保连接正常关闭，避免数据丢失。
序列号和确认（Sequence Number & ACK） ​
  • 每个数据段有序列号，接收方确认收到（ACK）。
  • 乱序数据会被重新排序。
重传机制 ​
  • 超时重传：发送方未收到 ACK 时重试。
  • 快速重传：接收方检测到丢包（重复 ACK）时通知重传。
错误检测 ​

TCP 头部包含校验和（Checksum），检测数据错误。

流量控制 ​

使用滑动窗口（Sliding Window）调节发送速率，防止接收方缓冲区溢出。

拥塞控制 ​

通过算法（如慢启动、拥塞避免）调整发送速率，避免网络过载。

TCP 数据包如何到应用层体现？ ​

传输流程 ​

物理层到传输层：

  • 网卡接收：数据包通过网络到达主机网卡。
  • IP 层：解包 IP 头部，确定目标地址和协议（TCP）。
  • TCP 层：
    • 解析 TCP 头部，提取序列号、端口等。
    • 重组数据流（排序、去重）。
    • 存入接收缓冲区。

内核到用户态：

  • 应用程序通过系统调用（如 read、recv）从套接字（Socket）读取数据。
  • 内核将缓冲区数据拷贝到用户态缓冲区。

应用层体现：

  • 数据表现为连续字节流。
  • 应用程序无需关心分包、丢失或乱序（TCP 已处理）。

体现方式 ​

数据流：

  • 应用层看到的是连续的字节流，而不是单独的 TCP 包。
  • 示例：发送方发送 "Hello"和 "World"，接收方可能读到 "HelloWorld"。

接口：

  • 使用 recv 或 read 读取数据，返回实际字节数。
  • 无需解析包边界，TCP 保证完整性。

错误处理：

  • 连接断开返回 EOF（recv 返回 0）。
  • 错误通过 errno 报告。

4、怎么解决粘包？ ​

在使用 TCP 协议进行网络通信时，由于 TCP 是面向字节流的协议，没有消息边界，导致发送的多个数据包可能被合并（粘包）或拆分（半包），这会影响应用层的消息解析。解决粘包问题需要在应用层设计协议或逻辑来正确划分消息边界。

什么是粘包？ ​

定义：

  • 粘包（Packet Sticking）：发送方发送的多个独立消息在接收方被合并成一个数据块。
  • 半包（Partial Packet）：单个消息被拆分成多个部分传输。

原因：

  • TCP 流式传输：TCP 将数据视为连续字节流，不保留消息边界。
  • Nagle 算法：为减少小包发送，TCP 可能合并多个小数据包。
  • 接收缓冲区：接收方可能一次读取多个消息或部分消息。
  • 网络延迟：数据包在传输中被分段或合并。

解决粘包的常用方法 ​

定长消息 ​

原理：每条消息固定长度，不足补齐（如填充空格或零）。

优点：简单，解析容易。

缺点：

  • 浪费空间（短消息需填充）。
  • 不适合变长消息。

适用场景：消息大小固定（如控制指令）。

长度前缀 ​

原理：每条消息前加固定字节（如 4 字节）表示后续数据的长度。

优点：

  • 灵活，支持变长消息。
  • 实现简单。

缺点：需额外字节。

适用场景：通用网络协议（如 HTTP/2）。

分隔符 ​

原理：使用特殊字符（如 \n、\0）分隔消息。

优点：直观，适合文本协议。

缺点：

  • 分隔符不能出现在消息内容中（需转义）。
  • 解析复杂。

适用场景：文本协议（如 SMTP、Redis）。

协议头+数据 ​

原理：定义复杂头部，包含长度、类型等元信息，后接数据。

优点：功能强大，支持复杂协议。

缺点：设计和解析复杂。

适用场景：高性能服务器（如游戏、即时通信）。

5、c++14 17对模板匹配的处理？ ​

C++14 对模板匹配的处理 ​

自动返回类型推导 ​

C++14 允许函数模板使用 auto 作为返回类型，编译器根据 return 语句推导类型。

c++
#include <iostream>

template<typename T, typename U>
auto add(T t, U u) { // C++14：自动推导返回类型
    return t + u;
}

int main() {
    std::cout << add(1, 2.5) << "\n"; // 推导为 double: 3.5
    std::cout << add(10, 20) << "\n";  // 推导为 int: 30
    return 0;
}
变参模板的增强 ​

C++14 放宽了变参模板的限制，支持更自然的递归展开。

配合 decltype 和 auto，变参模板更易用。

c++
#include <iostream>

template<typename... Args>
auto sum(Args... args) { // C++14：变参模板
    return (args + ...); // 折叠表达式（C++17 更优雅）
}

int main() {
    std::cout << sum(1, 2, 3, 4) << "\n"; // 10
    return 0;
}
模板别名 ​

C++11 引入模板别名，C++14 进一步普及。

使用 using 定义类型别名，简化模板匹配。

c++
#include <vector>

template<typename T>
using Vec = std::vector<T>;

template<typename T>
void print(const Vec<T>& v) {
    for (const auto& x : v) {
        std::cout << x << " ";
    }
    std::cout << "\n";
}

int main() {
    Vec<int> v = {1, 2, 3};
    print(v); // 1 2 3
    return 0;
}

C++17 对模板匹配的处理 ​

类模板参数推导 ​

C++17 允许类模板从构造函数实参自动推导模板参数，无需显式指定。

c++
#include <iostream>
#include <utility>

template<typename T1, typename T2>
struct Pair {
    T1 first;
    T2 second;
    Pair(T1 f, T2 s) : first(f), second(s) {}
};

int main() {
    Pair p(1, 2.5); // C++17：自动推导为 Pair<int, double>
    std::cout << p.first << ", " << p.second << "\n"; // 1, 2.5
    return 0;
}
推导指引 ​

允许用户定义类模板的参数推导规则。

用于非标准构造函数或复杂类型。

c++
#include <iostream>
#include <vector>

template<typename T>
struct MyContainer {
    std::vector<T> data;
    MyContainer(std::initializer_list<T> init) : data(init) {}
};

// 推导指引
template<typename T>
MyContainer(std::initializer_list<T>) -> MyContainer<T>;

int main() {
    MyContainer c = {1, 2, 3}; // 推导为 MyContainer<int>
    for (auto x : c.data) {
        std::cout << x << " "; // 1 2 3
    }
    return 0;
}
折叠表达式 ​

C++17 引入折叠表达式，简化变参模板的处理。

支持一元或二元操作（如 +、&&）。

c++
#include <iostream>

template<typename... Args>
auto sum(Args... args) {
    return (args + ...); // 折叠表达式
}

int main() {
    std::cout << sum(1, 2, 3, 4) << "\n"; // 10
    return 0;
}

6、四种转换？ ​

C++四种强制转换类型

7、没有继承关系的两个类怎么转换 用静态或动态会发生什么？ ​

C++ 中，如果两个类之间没有继承关系，意味着它们在类层次结构中不共享基类或子类关系。试图在它们之间进行类型转换需要特别小心，因为这种转换通常不符合类型安全的设计初衷。C++ 提供了四种显式类型转换，但在没有继承关系的类之间，某些转换可能不合法或导致未定义行为。

8、引用计数什么时候加减？ ​

引用计数是一个整数，存储在 std::shared_ptr 的控制块（Control Block）中，表示有多少个 shared_ptr 实例共享同一资源。

当引用计数为 0 时，释放资源（如删除对象）。

引用计数加减的时机 ​

引用计数增加 ​
  1. 创建新的shared_ptr：使用std::make_shared或new创建shared_ptr时，计数初始化为 1。
  2. 拷贝构造：从现有shared_ptr创建新实例（shared_ptr sp2 = sp1）。
  3. 拷贝赋值：将一个shared_ptr赋值给另一个（sp2 = sp1），前提是目标原先不指向同一资源。
  4. 从 weak_ptr 构造：调用 weak_ptr::lock() 创建 shared_ptr，若资源仍存在。
引用计数减少 ​
  1. 销毁 shared_ptr：shared_ptr 离开作用域（如局部变量）或被析构。
  2. 重置（reset）：调用 shared_ptr::reset()，使shared_ptr 不再指向资源。
  3. 赋值新资源：给shared_ptr赋新值（如sp = std::make_shared<int>(42)），释放旧资源。
  4. 清空（赋空）：将shared_ptr置为nullptr（sp = nullptr）。

9、vector list？ ​

定义 ​

std::vector ​

std::vector 是一个动态数组，元素在内存中连续存储，支持随机访问。

头文件：<vector>

特点：

  • 动态调整大小（自动扩容）。
  • 提供快速的随机访问和尾部插入/删除。
  • 内存分配在堆上，连续布局。
std::list ​

std::list 是一个双向链表，元素以节点形式存储，每个节点包含数据和前后指针。

头文件：<list>

特点：

  • 非连续存储，支持高效的任意位置插入/删除。
  • 不支持随机访问，只能通过迭代器遍历。
  • 内存分配在堆上，节点分散。

区别 ​

特性std::vectorstd::list
底层结构动态数组（连续内存）双向链表（分散节点）
内存布局连续非连续
随机访问支持（operator[], at()）不支持（需遍历）
插入/删除尾部高效，中间/头部低效任意位置高效
迭代器类型随机访问迭代器双向迭代器
内存开销较低（仅数组+容量信息）较高（每个节点存指针）
缓存友好性高（连续内存利于缓存）低（分散内存导致缓存失效）
大小调整动态扩容（可能重新分配）无需扩容，逐节点分配

10、类内sizeof(vector)跟vector里数据有没有关系？ ​

C++ 中，std::vector是一个动态数组容器，其对象的大小（通过 sizeof 运算符测得）与它内部存储的数据量（元素个数）没有直接关系。类内sizeof(std::vector)反映的是std::vector对象本身的内存占用，而不是其动态分配的数据部分的占用。

sizeof(std::vector)的基本原理 ​

sizeof(std::vector<T>) 返回 std::vector 对象本身的内存大小（以字节为单位）。

std::vector是一个模板类，管理动态数组，内部通常包含指向数据的指针及其他元数据。

典型实现：

  • 大多数标准库实现中，std::vector<T>包含以下成员：
    1. 指针（T*）：指向动态分配的数组（堆内存）。
    2. 大小（size_t）：当前元素数量。
    3. 容量（size_t）：分配的内存可容纳的元素数量。
  • 这些成员占用固定大小，与vector中存储的元素数量无关。

内存布局：

  • std::vector本身存储在栈上（或类对象内），其指向的动态数组存储在堆上。
  • sizeof 只计算栈上部分，不包括堆上数据。

11、set和unordered_set怎么插入一个class对象 需要做什么？ ​

std::set插入自定义类对象 ​

要求 ​

排序：std::set 维护元素的有序性，插入对象时需要比较大小。

定义 < 运算符：

  • 在类内或全局定义 operator<。
  • 满足严格弱序（不可传递、不对称、不自反）。

自定义比较器：提供比较器类或函数对象，作为模板参数。

拷贝/移动：对象需支持拷贝或移动构造（插入时可能复制）。

实现步骤 ​
  1. 定义类，包含需要比较的成员。
  2. 实现 operator< 或比较器。
  3. 插入对象到 set。
示例 ​

使用 operator<：

c++
#include <iostream>
#include <set>
#include <string>

class MyClass {
public:
    int id;
    std::string name;
    MyClass(int i, std::string n) : id(i), name(n) {}

    // 定义 operator< 进行比较
    bool operator<(const MyClass& other) const {
        return id < other.id; // 按 id 排序
    }
};

int main() {
    std::set<MyClass> my_set;

    // 插入对象
    my_set.emplace(1, "Alice");
    my_set.emplace(2, "Bob");
    my_set.emplace(1, "Charlie"); // id=1 已存在，不会插入

    // 遍历
    for (const auto& obj : my_set) {
        std::cout << "ID: " << obj.id << ", Name: " << obj.name << "\n";
    }

    return 0;
}

std::unordered_set插入自定义类对象 ​

要求 ​

哈希：

  • 需要为类定义哈希函数，计算唯一哈希值。
  • 通常通过 std::hash 特化或自定义哈希类。

相等比较：需要定义 operator== 判断对象是否相等。

拷贝/移动：同 set，对象需支持拷贝或移动。

实现步骤 ​
  1. 定义类，包含需要比较的成员。
  2. 实现operator==。
  3. 提供哈希函数（特化std::hash或自定义）。
  4. 插入对象到unordered_set。
示例 ​

特化 std::hash：

c++
#include <iostream>
#include <unordered_set>
#include <string>

// 自定义类
class MyClass {
public:
    int id;
    std::string name;
    MyClass(int i, std::string n) : id(i), name(n) {}

    // 定义 operator== 判断相等
    bool operator==(const MyClass& other) const {
        return id == other.id && name == other.name;
    }
};

// 特化 std::hash
namespace std {
template<>
struct hash<MyClass> {
    size_t operator()(const MyClass& obj) const {
        size_t h1 = std::hash<int>{}(obj.id);
        size_t h2 = std::hash<std::string>{}(obj.name);
        return h1 ^ (h2 << 1); // 简单哈希组合
    }
};
}

int main() {
    std::unordered_set<MyClass> my_set;

    // 插入对象
    my_set.emplace(1, "Alice");
    my_set.emplace(2, "Bob");
    my_set.emplace(1, "Alice"); // 重复，不会插入

    // 遍历
    for (const auto& obj : my_set) {
        std::cout << "ID: " << obj.id << ", Name: " << obj.name << "\n";
    }

    return 0;
}

性能对比 ​

操作std::setstd::unordered_set
插入O(log n)O(1) 平均，O(n) 最坏
查找O(log n)O(1) 平均，O(n) 最坏
删除O(log n)O(1) 平均，O(n) 最坏
内存红黑树，较紧凑哈希表，桶开销
排序有序无序

12、内存排布？ ​

栈（Stack）：

  • 存储局部变量、函数参数、返回地址。
  • 特点：自动管理，LIFO（后进先出），大小有限（通常几 MB）。
  • 示例：函数内的int x;。

堆（Heap）：

  • 存储动态分配的内存（如 new、malloc）。
  • 特点：手动管理，空间较大，需显式释放（delete、free）。
  • 示例：std::vector的动态数组。

静态/全局区：

  • 初始化数据：全局变量、静态变量（显式初始化）。
  • 未初始化数据（BSS）：全局/静态变量（默认零初始化）。
  • 特点：程序整个生命周期有效。
  • 示例：static int x = 10;。

代码段：

  • 存储程序的机器代码（函数指令）。
  • 特点：只读，固定大小。

常量区：

  • 存储字符串字面量、编译期常量。
  • 特点：通常只读。
  • 示例："Hello"。
高地址
+------------------+
|       栈         |  <- 局部变量，函数调用
+------------------+
|       ...        |
+------------------+
|       堆         |  <- 动态分配 (new, malloc)
+------------------+
| 未初始化数据(BSS)  |  <- 全局/静态变量 (零初始化)
+------------------+
| 初始化数据         |  <- 全局/静态变量 (非零初始化)
+------------------+
| 常量区            |  <- 字符串字面量
+------------------+
| 代码段            |  <- 程序指令
+------------------+
低地址

13、堆和栈区别？ ​

栈（Stack） ​

定义：

  • 栈是一种固定大小、自动管理的内存区域，用于存储局部变量、函数调用信息（如参数、返回地址）。
  • 遵循 LIFO（Last In, First Out，后进先出）原则。

位置：

  • 由操作系统分配，位于程序的栈内存段。

  • 管理：编译器和操作系统自动分配和释放。

堆（Heap） ​

定义：

  • 堆是一个动态分配的内存区域，用于存储程序运行时手动请求的内存（如通过 new 或 malloc）。
  • 没有固定结构，空间较大。

位置：

  • 位于程序的堆内存段，由操作系统提供。

  • 管理：程序员手动分配（new、malloc）和释放（delete、free）。

区别 ​

特性栈 (Stack)堆 (Heap)
分配方式自动（编译器管理）手动（程序员控制）
内存管理自动分配和释放手动分配和释放
大小有限（通常几 MB，系统设定）较大（受可用内存限制）
访问速度快速（固定地址，缓存友好）较慢（动态分配，碎片可能影响）
生命周期作用域结束即销毁手动释放或程序结束
内存碎片无（连续分配）有（可能导致碎片）
用途局部变量、函数调用动态对象、大数据结构
安全性高（自动管理）低（易漏内存或野指针）
线程安全每个线程有独立栈堆是共享的，需同步

14、说几种unix系统调用的函数 read write mmap ​

read系统调用 ​

头文件：<unistd.h>

函数原型：

c++
ssize_t read(int fd, void *buf, size_t count);

功能：

  • 从文件描述符 fd 读取最多 count 字节的数据到缓冲区 buf。
  • 适用于文件、管道、套接字等。

参数：

  • fd：文件描述符（由 open 或 socket 等返回）。
  • buf：用户提供的缓冲区，存储读取的数据。
  • count：请求读取的字节数。

返回值：

  • 成功：返回实际读取的字节数（可能少于 count）。
  • 0：文件末尾（EOF）。
  • -1：错误（errno 指示具体错误，如 EBADF）。

用途：

  • 读取文件内容。
  • 从管道或套接字接收数据。

write系统调用 ​

头文件：<unistd.h>

函数原型：

c++
ssize_t write(int fd, const void *buf, size_t count);

功能：

  • 将缓冲区 buf 中的 count 字节数据写入文件描述符 fd。
  • 适用于文件、管道、套接字等。

参数：

  • fd：文件描述符。
  • buf：待写入数据的缓冲区。
  • count：请求写入的字节数。

返回值：

  • 成功：返回实际写入的字节数（可能少于 count）。
  • -1：错误（errno 指示错误，如 EPIPE）。

用途：

  • 写入文件内容。
  • 发送套接字数据。
  • 输出到终端或管道。

mmap系统调用 ​

头文件：<sys/mman.h>

函数原型：

c++
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

功能：

  • 将文件或设备映射到进程的虚拟内存，允许直接操作文件内容。
  • 可用于文件 I/O、共享内存。

参数：

  • addr：期望的映射地址（通常为 nullptr，由系统选择）。
  • length：映射的字节数。
  • prot：内存保护标志（PROT_READ、PROT_WRITE、PROT_EXEC）。
  • flags：映射类型（MAP_SHARED、MAP_PRIVATE）。
  • fd：文件描述符（可为 -1 用于匿名映射）。
  • offset：文件偏移量（通常为 0）。

返回值：

  • 成功：返回映射的内存地址。
  • MAP_FAILED（(void*)-1）：错误（errno 指示）。

用途：

  • 高效文件读写（避免缓冲拷贝）。
  • 进程间共享内存。
  • 动态加载库。

15、哈希冲突 怎么解决？哈希的流程？ ​

哈希冲突

16、说几种序列化的方式？ ​

序列化是将对象或数据结构转换为可存储或传输的格式（如字节流）的过程，反序列化则是其逆过程。

下面直接用表格看看几种序列化方式吧

对比总结 ​

方式格式性能可读性跨语言复杂性适用场景
手动序列化二进制/文本高低低高嵌入式、高性能
JSON文本 (JSON)中高高中Web、配置文件
Protobuf二进制高低高中网络通信、分布式系统
Boost.Ser二进制/文本中中中高Boost 项目、复杂对象
Cereal二进制/文本高中中低小型项目、简单序列化

17、怎么看linux里内存和cpu使用情况？ ​

查看内存使用情况 ​

free 命令 ​

功能：显示系统内存使用概况（总计、已用、可用等）。

用法：free -h

top / htop ​

功能：实时显示系统资源使用，包括内存和每个进程的占用。

用法：top、htop

/proc/meminfo ​

功能：内核提供的详细内存信息文件。

用法：cat /proc/meminfo

vmstat ​

功能：显示内存、CPU、I/O 等统计信息。

用法：vmstat -s或实时监控vmstat 1

查看 CPU 使用情况 ​

top / htop ​

功能：实时显示 CPU 使用率和进程信息。

用法：top、htop

mpstat ​

功能：显示每个 CPU 核心的使用情况（需 sysstat 包）。

用法：mpstat -P ALL 1

ps ​

功能：列出进程及其 CPU 占用。

用法：ps aux --sort=-%cpu

/proc/stat ​

功能：内核提供的 CPU 使用统计。

用法：cat /proc/stat

sar ​

功能：系统活动报告，监控 CPU、内存等（需 sysstat）。

用法：sar -u 1

18、快排原理及时间复杂度？怎么优化？随机数怎么取？ ​

原理 ​

快速排序的核心思想是 分治法，通过选择一个 基准（pivot） 将数组划分为两个子数组，反复递归排序，最终得到有序序列。

步骤 ​

  1. 选择 pivot：从数组中选择一个元素作为基准（如首元素、末元素、中间元素或随机元素）。

  2. 分区（Partition）：

    将数组重新排列：

    • 小于 pivot 的元素放在左侧。
    • 大于 pivot 的元素放在右侧。
    • pivot 放置在正确位置（最终位置）。

​ 分区后，pivot 位于其在最终排序数组中的位置。

  1. 递归：对 pivot 左侧和右侧的子数组递归应用上述步骤，直到子数组大小为 0 或 1。

时间复杂度 ​

快速排序的时间复杂度取决于 pivot 的选择和输入数据特性。

情况时间复杂度说明
平均情况O(n log n)pivot 平均分割数组为两半，递归深度 log n。
最好情况O(n log n)pivot 每次接近中位数，分割均衡。
最坏情况O(n²)pivot 总是最小/最大值（如已排序数组）。

空间复杂度：

  • 递归栈：平均 O(log n)，最坏 O(n)。
  • 原地排序：不计递归栈，额外空间 O(1)。
最坏情况分析 ​

发生场景：

  • 数组已排序或逆序（选择首/末元素）。
  • 所有元素相等。

结果：每次分区只减少一个元素，递归 n 次，每层 O(n)，总计 O(n²)。

优化方法 ​

随机化 pivot ​

问题：固定选择 pivot（如末元素）在有序或重复数据下退化为 O(n²)。

优化：

  • 随机选择 pivot，降低最坏情况概率。
  • 方法：在分区前随机交换某个元素与末元素。

效果：平均情况接近 O(n log n)，最坏情况概率极低。

实现：使用随机数生成器（如 std::mt19937）。

三数取中 ​

问题：随机化有性能开销，且不保证最佳 pivot。

优化：

  • 选择首、末、中间三个元素的 中位数 作为 pivot。
  • 方法：比较三者大小，选择中间值。

效果：

  • 更接近中位数，分割均衡。
  • 避免随机数生成开销。

适用：中等规模数组。

插入排序优化（小规模子数组） ​

问题：小数组递归调用开销较大。

优化：

  • 当子数组大小低于阈值（如 10），使用插入排序。
  • 插入排序在小规模数据上效率高（O(n²) 但常数小）。

效果：减少递归深度，提升性能。

处理重复元素 ​

问题：大量重复元素可能导致不均衡分区。

优化：

  • 使用三路分区（Dutch Flag Partitioning）：
    • 小于 pivot。
    • 等于 pivot。
    • 大于 pivot。
  • 等于 pivot 的元素不再递归。

效果：重复元素场景下显著提升性能。

C++ 实现 ​

给出一个优化的快速排序实现，结合随机化 pivot 和插入排序优化。

c++
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

class QuickSort {
private:
    static std::mt19937 gen; // 随机数生成器

    // 插入排序（小规模）
    static void insertion_sort(std::vector<int>& arr, int low, int high) {
        for (int i = low + 1; i <= high; ++i) {
            int key = arr[i];
            int j = i - 1;
            while (j >= low && arr[j] > key) {
                arr[j + 1] = arr[j];
                --j;
            }
            arr[j + 1] = key;
        }
    }

    // 分区
    static int partition(std::vector<int>& arr, int low, int high) {
        // 随机 pivot
        std::uniform_int_distribution<> dist(low, high);
        int pivot_idx = dist(gen);
        std::swap(arr[pivot_idx], arr[high]);

        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; ++j) {
            if (arr[j] <= pivot) {
                ++i;
                std::swap(arr[i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);
        return i + 1;
    }

    // 快速排序核心
    static void quick_sort(std::vector<int>& arr, int low, int high) {
        if (high - low <= 10) { // 小规模用插入排序
            insertion_sort(arr, low, high);
            return;
        }
        if (low < high) {
            int pi = partition(arr, low, high);
            quick_sort(arr, low, pi - 1);
            quick_sort(arr, pi + 1, high);
        }
    }

public:
    static void sort(std::vector<int>& arr) {
        if (arr.empty()) return;
        quick_sort(arr, 0, arr.size() - 1);
    }
};

// 初始化随机数生成器
std::mt19937 QuickSort::gen(std::random_device{}());

int main() {
    std::vector<int> arr = {5, 2, 9, 1, 5, 6, 3, 8, 7, 4};
    std::cout << "Before: ";
    for (int x : arr) std::cout << x << " ";
    std::cout << "\n";

    QuickSort::sort(arr);

    std::cout << "After: ";
    for (int x : arr) std::cout << x << " ";
    std::cout << "\n";
    return 0;
}

19、手撕有序链表去重？ ​

解题思路 ​

核心原理 ​

有序性：重复元素连续出现（如 1->1->1->2）。

原地删除：

  • 遍历链表，检查当前节点与下一节点的值。
  • 若相等，跳过下一节点（修改指针，释放内存）。
  • 若不同，前进到下一节点。

指针操作：

  • 使用指针追踪当前节点（curr）。
  • 比较curr->val和curr->next->val。
  • 删除重复节点时，更新curr->next并释放内存。
步骤 ​

  1. 检查边界：若链表为空（head == nullptr）或只有一个节点（head->next == nullptr），直接返回。

  2. 初始化：设置指针curr指向头节点。

  3. 遍历：

    • 循环条件：curr 和curr->next非空。

    • 比较curr->val和curr->next->val：

      若相等：

      • 保存下一节点（temp = curr->next）。
      • 更新 curr->next = temp->next（跳过重复节点）。
      • 删除 temp（释放内存）。

      若不同：curr = curr->next（前进）。

  4. 返回：返回原头节点（已修改）。

示例代码（C++） ​

c++
#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* deleteDuplicates(ListNode* head) {
    // 边界：空链表或单一节点
    if (head == nullptr || head->next == nullptr) {
        return head;
    }

    // 当前指针
    ListNode* curr = head;

    // 遍历
    while (curr != nullptr && curr->next != nullptr) {
        if (curr->val == curr->next->val) {
            // 删除下一节点
            ListNode* temp = curr->next;
            curr->next = temp->next;
            delete temp; // 释放内存
        } else {
            // 前进
            curr = curr->next;
        }
    }

    return head;
}

ListNode* createList(const std::vector<int>& vals) {
    if (vals.empty()) return nullptr;
    ListNode* head = new ListNode(vals[0]);
    ListNode* curr = head;
    for (size_t i = 1; i < vals.size(); ++i) {
        curr->next = new ListNode(vals[i]);
        curr = curr->next;
    }
    return head;
}

void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr) {
        std::cout << curr->val;
        if (curr->next) std::cout << "->";
        curr = curr->next;
    }
    std::cout << "\n";
}

void freeList(ListNode* head) {
    ListNode* curr = head;
    while (curr) {
        ListNode* temp = curr;
        curr = curr->next;
        delete temp;
    }
}

int main() {
    // 测试用例
    std::vector<std::vector<int>> tests = {
        {1, 1, 2, 3, 3, 4}, // 1->1->2->3->3->4
        {1, 1, 1},          // 1->1->1
        {},                  // 空
        {1},                 // 1
        {1, 2, 3}           // 1->2->3
    };

    for (const auto& vals : tests) {
        ListNode* head = createList(vals);
        std::cout << "Input: ";
        printList(head);
        head = deleteDuplicates(head);
        std::cout << "Output: ";
        printList(head);
        freeList(head);
        std::cout << "\n";
    }

    return 0;
}