C++ 数据结构与算法 常考面试题(一)
1. 如何实现快速排序？快排优化有哪些？
核心思想
快速排序基于分治思想，核心逻辑是：选择一个基准值，将数组划分为「小于基准」和「大于基准」的两个子数组，递归对两个子数组重复该过程，直至子数组长度为1（天然有序）。快排的性能核心取决于基准值的选择和分区效率。
代码实现（经典Hoare分区法）
#include <vector>
#include <algorithm>
using namespace std;
// 分区函数：返回基准值最终位置
int partition(vector<int>& nums, int left, int right) {
// 选左边界为基准值
int pivot = nums[left];
int i = left, j = right;
while (i < j) {
// 右指针找小于基准的数
while (i < j && nums[j] >= pivot) j--;
// 左指针找大于基准的数
while (i < j && nums[i] <= pivot) i++;
// 交换不符合分区规则的元素
if (i < j) swap(nums[i], nums[j]);
}
// 基准值归位（放到分区中间）
swap(nums[left], nums[i]);
return i;
}
// 快速排序主函数
void quickSort(vector<int>& nums, int left, int right) {
// 递归终止条件：子数组长度≤1
if (left >= right) return;
int pivotIdx = partition(nums, left, right);
// 递归排序左、右子数组
quickSort(nums, left, pivotIdx - 1);
quickSort(nums, pivotIdx + 1, right);
}
快排经典优化手段
- 基准值优化：三数取中法（取左、中、右边界的中间值作为基准），避免有序数组导致的O(n²)最坏情况。
- 小区间优化：当子数组长度小于10时，改用插入排序（减少递归调用的栈开销）。
- 尾递归优化：对较长的子数组递归，较短的子数组用循环处理，降低栈帧消耗。
- 去重优化：三路快排（将等于基准值的元素聚集到中间），避免重复元素的无效排序。
时间/空间复杂度
- 平均时间复杂度：O(nlogn)（面试必背）
- 最坏时间复杂度：O(n²)（优化后可规避）
- 空间复杂度：O(logn)（递归栈开销，最坏O(n)）
2. 如何解决二叉树的层序遍历问题？变体如何应对？
核心思想
二叉树层序遍历基于广度优先搜索（BFS），核心是利用队列记录每一层的节点，通过「记录当前层节点数」实现按层遍历，而非单纯的广度遍历。
代码实现（基础层序遍历，按行输出）
#include <vector>
#include <queue>
using namespace std;
// 二叉树节点定义
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 层序遍历：返回二维数组，每行对应二叉树的一层
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res; // 空树直接返回
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size(); // 记录当前层的节点数
vector<int> curLevel;
// 遍历当前层所有节点
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
curLevel.push_back(node->val);
// 子节点入队，为下一层遍历做准备
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res.push_back(curLevel);
}
return res;
}
经典变体及应对技巧
时间/空间复杂度
- 时间复杂度：O(n)（每个节点仅访问一次）
- 空间复杂度：O(n)（队列最多存储一层节点，最坏为满二叉树的最后一层）
3. 如何实现哈希表？解决哈希冲突的方法有哪些？
核心思想
哈希表（散列表）的核心是通过哈希函数将键（key）映射到数组的指定索引，实现O(1)平均时间复杂度的增删改查；核心解决的问题是「哈希冲突」（不同key映射到同一索引）。
代码实现（链地址法解决冲突，工业界主流）
#include <vector>
#include <string>
#include <stdexcept>
using namespace std;
// 哈希表节点结构
template <typename K, typename V>
struct HashNode {
K key;
V val;
HashNode* next;
HashNode(K k, V v) : key(k), val(v), next(nullptr) {}
};
// 简易哈希表（链地址法）
template <typename K, typename V>
class HashMap {
private:
vector<HashNode<K, V>*> table; // 底层数组
int size; // 实际存储节点数
const int DEFAULT_CAP = 16; // 默认初始容量
const float LOAD_FACTOR = 0.75; // 负载因子阈值（超过则扩容）
// 简易哈希函数（针对int键，可扩展至其他类型）
int hash(K key) {
return abs((int)key) % table.size();
}
// 扩容：容量翻倍，重新哈希所有节点
void resize() {
int newCap = table.size() * 2;
vector<HashNode<K, V>*> newTable(newCap, nullptr);
for (auto& node : table) {
HashNode<K, V>* cur = node;
while (cur) {
HashNode<K, V>* next = cur->next;
int idx = abs((int)cur->key) % newCap;
cur->next = newTable[idx];
newTable[idx] = cur;
cur = next;
}
}
table.swap(newTable);
}
public:
HashMap() : table(DEFAULT_CAP, nullptr), size(0) {}
// 插入/更新键值对
void put(K key, V val) {
if ((float)size / table.size() >= LOAD_FACTOR) resize();
int idx = hash(key);
HashNode<K, V>* cur = table[idx];
// 已存在该key，更新值
while (cur) {
if (cur->key == key) {
cur->val = val;
return;
}
cur = cur->next;
}
// 不存在，头插法新增节点
HashNode<K, V>* newNode = new HashNode<K, V>(key, val);
newNode->next = table[idx];
table[idx] = newNode;
size++;
}
// 根据key查找值
V get(K key) {
int idx = hash(key);
HashNode<K, V>* cur = table[idx];
while (cur) {
if (cur->key == key) return cur->val;
cur = cur->next;
}
throw out_of_range("key not found");
}
// 删除指定key
void remove(K key) {
int idx = hash(key);
HashNode<K, V>* cur = table[idx];
HashNode<K, V>* pre = nullptr;
while (cur) {
if (cur->key == key) {
if (pre) pre->next = cur->next;
else table[idx] = cur->next;
delete cur;
size--;
return;
}
pre = cur;
cur = cur->next;
}
}
~HashMap() {
// 释放所有节点内存
for (auto& node : table) {
HashNode<K, V>* cur = node;
while (cur) {
HashNode<K, V>* next = cur->next;
delete cur;
cur = next;
}
}
}
};
解决哈希冲突的常用方法
- 链地址法：本文实现方式，数组每个索引挂链表，冲突节点加入链表（Java HashMap、C++ unordered_map底层）。
- 开放定址法：冲突后按规则（线性探测、二次探测）寻找下一个空位置，缺点是易产生聚集。
- 再哈希法：冲突后用另一个哈希函数计算新索引，缺点是增加计算开销。
- 公共溢出区法：冲突节点全部放入溢出区，适合冲突较少的场景。
4. 如何解决拓扑排序问题？Kahn 算法与 DFS 实现？
核心思想
拓扑排序针对有向无环图（DAG），核心是将图中所有节点排成一个线性序列，使得任意有向边u→v中，u都出现在v之前；常用来解决「依赖关系」问题（如课程安排、任务调度）。
方法1：Kahn算法（基于入度的BFS实现）
核心逻辑
- 计算所有节点的入度；
- 将入度为0的节点入队（无前置依赖）；
- 出队节点并加入结果，将其邻接节点入度减1；
- 重复步骤2-3，直至队空；
- 若结果长度≠节点总数，说明图有环，无拓扑序。
#include <vector>
#include <queue>
using namespace std;
// 拓扑排序（Kahn算法）：返回拓扑序列，空数组表示有环
vector<int> topologicalSortKahn(int n, vector<vector<int>>& edges) {
vector<int> inDegree(n, 0); // 入度数组
vector<vector<int>> adj(n); // 邻接表
// 构建邻接表+统计入度
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
adj[u].push_back(v);
inDegree[v]++;
}
queue<int> q;
// 入度为0的节点入队
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) q.push(i);
}
vector<int> res;
while (!q.empty()) {
int u = q.front();
q.pop();
res.push_back(u);
// 遍历邻接节点，入度减1
for (int v : adj[u]) {
inDegree[v]--;
if (inDegree[v] == 0) q.push(v);
}
}
// 有环：结果长度≠节点数
if (res.size() != n) return {};
return res;
}
方法2：DFS实现（基于后序遍历）
核心逻辑
- 递归遍历节点，标记访问状态（未访问/访问中/已访问）；
- 访问中遇到「访问中」的节点，说明有环；
- 后序遍历完成后，将节点加入结果；
- 最终反转结果，得到拓扑序。
#include <vector>
#include <algorithm>
using namespace std;
// 辅助DFS函数
bool dfs(int u, vector<vector<int>>& adj, vector<int>& visited, vector<int>& res) {
visited[u] = 1; // 标记为访问中
for (int v : adj[u]) {
if (visited[v] == 1) return false; // 发现环
if (visi
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
C++ 常考面试题总结 文章被收录于专栏
本专栏系统梳理C++方向, 大中厂高频高频面试考点 , 内容皆来自真实面试经历，从基础语法、内存管理、STL与设计模式，到操作系统与项目实战，结合真实面试题深度解析，帮助开发者高效查漏补缺，提升技术理解与面试通过率，打造扎实的C++工程能力.
查看7道真题和解析