C++后端面试高频算法题解析与实战

1. C++后端面试算法题深度解析与实战指南

作为C++后端开发者，算法能力是面试中的核心考察点。本文将深入解析20道高频算法题，从原理分析到代码实现，再到优化技巧，提供一站式解决方案。这些题目覆盖了数据结构设计、搜索算法、树操作、滑动窗口、动态规划等关键领域，全部基于C++17标准实现，可直接用于面试准备和日常编码参考。

2. 核心算法题解析与实现

2.1 用栈实现队列（LeetCode 232）

问题本质：利用栈的LIFO特性模拟队列的FIFO行为。关键在于设计元素的反转机制。

双栈法原理：

• 输入栈(pushst)：直接接收push操作
• 输出栈(popst)：当需要pop/peek时，如果为空则将输入栈元素全部转移过来

cpp复制class MyQueue {
    stack<int> pushst;
    stack<int> popst;
    
    void transferIfNeeded() {
        if(popst.empty()) {
            while(!pushst.empty()) {
                popst.push(pushst.top());
                pushst.pop();
            }
        }
    }
public:
    void push(int x) { pushst.push(x); }
    
    int pop() {
        transferIfNeeded();        
        int ret = popst.top();
        popst.pop();
        return ret;
    }
    
    int peek() {
        transferIfNeeded();
        return popst.top();
    }
    
    bool empty() {
        return pushst.empty() && popst.empty();
    }
};

时间复杂度分析：

• push: O(1)
• pop/peek: 摊还O(1)（每个元素最多被压入和弹出各两次）

面试陷阱：面试官可能会追问为什么摊还复杂度是O(1)。关键在于每个元素从pushst到popst只会移动一次。

2.2 二分查找（LeetCode 704）

标准实现要点：

• 循环条件：left <= right（允许左右指针重合）
• 中间值计算：mid = left + (right - left)/2（防溢出）
• 边界更新：根据比较结果+1/-1

cpp复制int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        int mid = left + (right - left)/2;
        if(nums[mid] > target) 
            right = mid - 1;
        else if(nums[mid] < target) 
            left = mid + 1;
        else 
            return mid;
    }
    return -1;
}

变种问题：

1. 查找第一个/最后一个等于target的位置
2. 查找第一个大于等于target的位置
3. 旋转数组中的搜索

实测技巧：在面试手写时，建议先写出这个标准模板，再根据具体问题调整。二分查找的bug率在面试中高达90%，主要问题在于边界条件处理。

2.3 二叉树的中序遍历（LeetCode 94）

递归解法：

cpp复制void inorder(TreeNode* root, vector<int>& res) {
    if(!root) return;
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}

迭代解法（显式栈）：

cpp复制vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> res;
    TreeNode* curr = root;
    
    while(curr || !st.empty()) {
        while(curr) {  // 深入左子树
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top(); st.pop();
        res.push_back(curr->val);
        curr = curr->right;  // 转向右子树
    }
    return res;
}

Morris遍历（O(1)空间）：

cpp复制vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    TreeNode *curr = root, *pre = nullptr;
    
    while(curr) {
        if(!curr->left) {
            res.push_back(curr->val);
            curr = curr->rig