C++中的算法与数据结构面试常见问题

《C++中的算法与数据结构面试常见问题》

在C++技术面试中，算法与数据结构是核心考察内容。无论是校招还是社招，面试官常通过这类问题评估候选人的编程思维、问题解决能力以及对底层原理的理解。本文系统梳理了C++面试中高频出现的算法与数据结构问题，涵盖基础概念、经典题目、底层实现及优化技巧，帮助读者构建完整的知识体系。

一、基础数据结构核心问题

1. 数组与字符串

数组是连续内存存储的线性结构，而字符串可视为字符数组。面试中常考察数组操作、字符串处理及边界条件处理。

问题示例：如何反转一个字符串？

#include 
#include 
void reverseString(std::string& s) {
    std::reverse(s.begin(), s.end()); // STL方法
    // 或手动实现双指针
    int left = 0, right = s.size() - 1;
    while (left 

关键点：时间复杂度O(n)，空间复杂度O(1)。需注意字符串为空或长度为1时的边界情况。

2. 链表操作

链表通过指针连接节点，面试中常考察反转、环检测、合并等操作。

问题示例：反转单链表（递归与非递归）。

// 非递归实现
struct ListNode {
    int val;
    ListNode *next;
};
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr) {
        ListNode *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}
// 递归实现
ListNode* reverseListRecursive(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode *newHead = reverseListRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

关键点：理解指针操作顺序，避免断链。递归需明确终止条件与递归关系。

3. 栈与队列

栈（LIFO）与队列（FIFO）是基础容器，常考察其实现及应用场景。

问题示例：用两个栈实现队列。

#include 
class QueueWithStacks {
private:
    std::stack in, out;
public:
    void push(int x) { in.push(x); }
    int pop() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        int val = out.top();
        out.pop();
        return val;
    }
    bool empty() { return in.empty() && out.empty(); }
};

关键点：入队操作O(1)，出队操作均摊O(1)。需理解栈的顺序反转特性。

二、树与图算法

1. 二叉树遍历

二叉树遍历分为深度优先（前序、中序、后序）与广度优先（层次遍历）。

问题示例：二叉树的中序遍历（递归与非递归）。

// 递归实现
void inorderTraversal(TreeNode* root, std::vector& res) {
    if (!root) return;
    inorderTraversal(root->left, res);
    res.push_back(root->val);
    inorderTraversal(root->right, res);
}
// 非递归实现（使用栈）
std::vector inorderTraversalIterative(TreeNode* root) {
    std::vector res;
    std::stack s;
    TreeNode *curr = root;
    while (curr || !s.empty()) {
        while (curr) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top(); s.pop();
        res.push_back(curr->val);
        curr = curr->right;
    }
    return res;
}

关键点：非递归实现需模拟递归调用栈，明确节点访问顺序。

2. 二叉搜索树（BST）

BST满足左子树小于根、右子树大于根的特性，常考察插入、删除、验证等操作。

问题示例：验证二叉搜索树。

bool isValidBST(TreeNode* root, long long min = LLONG_MIN, long long max = LLONG_MAX) {
    if (!root) return true;
    if (root->val val >= max) return false;
    return isValidBST(root->left, min, root->val) && 
           isValidBST(root->right, root->val, max);
}

关键点：利用上下界约束递归验证，避免仅比较左右子节点。

3. 图算法

图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）及拓扑排序等。

问题示例：课程表问题（拓扑排序）。

#include 
#include 
bool canFinish(int numCourses, std::vector<:vector>>& prerequisites) {
    std::vector<:vector>> graph(numCourses);
    std::vector inDegree(numCourses, 0);
    for (auto& edge : prerequisites) {
        graph[edge[1]].push_back(edge[0]);
        inDegree[edge[0]]++;
    }
    std::queue q;
    for (int i = 0; i 

关键点：构建有向图并计算入度，通过BFS实现拓扑排序。

三、排序与搜索算法

1. 快速排序与归并排序

快速排序通过分治思想实现，归并排序则依赖递归与合并。

问题示例：快速排序实现。

#include 
#include 
void quickSort(std::vector& nums, int left, int right) {
    if (left >= right) return;
    int pivot = nums[(left + right) / 2];
    int i = left, j = right;
    while (i  pivot) j--;
        if (i 

关键点：选择合适基准值（pivot），避免最坏时间复杂度O(n²)。

2. 二分查找

二分查找要求数组有序，常考察边界条件与变种问题。

问题示例：寻找旋转排序数组中的最小值。

int findMin(std::vector& nums) {
    int left = 0, right = nums.size() - 1;
    while (left  nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

关键点：通过比较中间值与右边界确定搜索方向，终止条件为left == right。

四、动态规划与贪心算法

1. 动态规划基础

动态规划通过状态转移方程解决重叠子问题，常考察背包问题、最长子序列等。

问题示例：0-1背包问题。

int knapsack(int W, std::vector& weights, std::vector& values) {
    int n = weights.size();
    std::vector<:vector>> dp(n + 1, std::vector(W + 1, 0));
    for (int i = 1; i 

关键点：定义状态dp[i][w]表示前i个物品在容量w下的最大价值，优化空间复杂度至O(W)。

2. 贪心算法应用

贪心算法通过局部最优解推导全局最优，常考察区间调度、硬币找零等问题。

问题示例：区间调度最大化非重叠区间数。

#include 
#include 
int eraseOverlapIntervals(std::vector<:vector>>& intervals) {
    if (intervals.empty()) return 0;
    std::sort(intervals.begin(), intervals.end(), 
              [](auto& a, auto& b) { return a[1] = end) {
            end = intervals[i][1];
            count++;
        }
    }
    return intervals.size() - count;
}

关键点：按结束时间排序，每次选择结束最早的区间以保留更多空间。

五、STL与底层实现

1. STL容器特性

面试中常考察vector、map、unordered_map等容器的底层实现与时间复杂度。

问题示例：vector扩容机制。

vector在容量不足时按2倍（或1.5倍）扩容，涉及内存重新分配与元素拷贝。例如：

std::vector v;
v.reserve(10); // 预留空间但不改变size
v.push_back(1); // 若容量不足则触发扩容

关键点：理解capacity与size的区别，扩容导致迭代器失效。

2. 智能指针

智能指针（unique_ptr、shared_ptr）用于管理动态内存，常考察引用计数与循环引用问题。

问题示例：shared_ptr循环引用导致内存泄漏。

#include 
struct Node {
    std::shared_ptr next;
    ~Node() { std::cout ();
    auto b = std::make_shared();
    a->next = b; // 循环引用
    b->next = a;
    // 此时引用计数为2，无法释放
    return 0;
}

解决方案：使用weak_ptr打破循环引用。

六、系统设计与优化

1. 大数据量处理

面试中常考察海量数据下的算法优化，如分治、布隆过滤器、哈希分片等。

问题示例：设计一个支持增删改查的亿级数据系统。

解决方案：

• 分库分表：按哈希或范围分割数据
• 缓存层：使用Redis缓存热点数据
• 异步处理：消息队列解耦读写操作

2. 算法空间优化

通过位运算、原地修改等方式减少空间占用。

问题示例：原地删除排序数组中的重复项。

int removeDuplicates(std::vector& nums) {
    if (nums.empty()) return 0;
    int slow = 0;
    for (int fast = 1; fast 

关键点：双指针法，时间复杂度O(n)，空间复杂度O(1)。

关键词、简介

关键词：C++面试、算法、数据结构、链表反转、二叉树遍历、动态规划、二分查找、STL容器、智能指针、系统设计

简介：本文系统梳理C++面试中算法与数据结构的高频问题，涵盖数组、链表、树、图等基础数据结构，排序、搜索、动态规划等核心算法，以及STL使用与系统设计优化技巧。通过代码示例与关键点解析，帮助读者掌握面试常见问题的解题思路与实现细节。