C++八股文（数据结构2）

1. 如何实现动态规划？

动态规划核心思想：将复杂问题分解为子问题，保存子问题结果避免重复计算

经典例子：斐波那契数列

// 递归（指数时间）
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

// DP自底向上（O(n)时间，O(n)空间）
int fibDP(int n) {
    if (n <= 1) return n;
    vector<int> dp(n + 1);
    dp[0] = 0, dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// 空间优化（O(1)空间）
int fibOptimized(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

四个步骤：①定义状态（dp数组含义）②状态转移方程 ③初始化边界 ④确定计算顺序
两种实现：自顶向下（记忆化递归）、自底向上（迭代）
优化技巧：滚动数组降维、状态压缩
经典问题：最长公共子序列、最长递增子序列、编辑距离、股票买卖

2. 如何解决背包问题？

0-1背包（每个物品只能选一次）

// 物品i，容量j，dp[i][j]表示前i个物品容量j的最大价值
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (weights[i-1] <= j) {
                // 选或不选第i个物品
                dp[i][j] = max(dp[i-1][j], 
                              dp[i-1][j-weights[i-1]] + values[i-1]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][capacity];
}

// 空间优化：一维数组（倒序遍历）
int knapsackOptimized(vector<int>& weights, vector<int>& values, int capacity) {
    vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < weights.size(); i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

完全背包：物品可无限选，内层循环正序遍历
多重背包：每个物品有数量限制，转化为0-1背包
时间复杂度：O(n×capacity)
应用：资源分配、投资组合、切割问题

3. 如何实现 KMP 算法？

// 构建next数组（部分匹配表）
vector<int> buildNext(string pattern) {
    int m = pattern.length();
    vector<int> next(m, 0);
    int j = 0;  // 前缀长度
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];  // 回退
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

// KMP匹配
int kmpSearch(string text, string pattern) {
    int n = text.length(), m = pattern.length();
    if (m == 0) return 0;
    
    vector<int> next = buildNext(pattern);
    int j = 0;  // pattern的索引
    
    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];  // 不匹配时回退
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;  // 找到匹配
        }
    }
    return -1;  // 未找到
}

核心思想：利用已匹配信息，避免重复比较
next数组：记录模式串中最长相同前后缀长度
时间复杂度：O(n+m)，优于暴力的O(n×m)
应用：字符串搜索、文本编辑器、DNA序列匹配

4. 什么是二分查找？如何实现？

// 标准二分查找（有序数组）
int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防溢出
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;  // 未找到
}

// 查找第一个>=target的位置（lower_bound）
int lowerBound(vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

// 查找第一个>target的位置（upper_bound）
int upperBound(vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

前提条件：数组有序
时间复杂度：O(log n)
边界处理：left<=right还是left<right，mid+1还是mid
STL函数：binary_search、lower_bound、upper_bound
变体：旋转数组、峰值查找、平方根

5. 如何找到二叉树的最低公共祖先（LCA）？

// 递归解法
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    
    if (left && right) return root;  // p和q分别在左右子树
    return left ? left : right;  // 都在一侧
}

// BST的LCA（利用有序性）
TreeNode* lcaBST(TreeNode* root, TreeNode* p, TreeNode* q) {
    while (root) {
        if (p->val < root->val && q->val < root->val) {
            root = root->left;  // 都在左子树
        } else if (p->val > root->val && q->val > root->val) {
            root = root->right;  // 都在右子树
        } else {
            return root;  // 分叉点就是LCA
        }
    }
    return nullptr;
}

思路：如果p和q分别在左右子树，当前节点就是LCA；否则LCA在有p或q的那一侧
时间复杂度：O(n)
BST优化：利用有序性，O(h)时间
变体：多个节点的LCA、带父指针的树

6. 如何实现堆排序？

// 调整堆（大顶堆）
void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;
    
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);  // 递归调整
    }
}

// 堆排序
void heapSort(vector<int>& arr) {
    int n = arr.size();
    
    // 建堆：从最后一个非叶子节点开始
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 排序：依次取出堆顶元素
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);  // 堆顶（最大值）放到末尾
        heapify(arr, i, 0);    // 调整剩余元素
    }
}

堆性质：完全二叉树，父节点>=子节点（大顶堆）或<=（小顶堆）
时间复杂度：O(n log n)，建堆O(n)，每次调整O(log n)
空间复杂度：O(1)，原地排序
不稳定排序：相同元素相对位置可能改变
STL：priority_queue、make_heap、push_heap、pop_heap

7. 如何使用哈希表来解决重复问题？

// 判断数组是否有重复元素
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int num : nums) {
        if (seen.count(num)) return true;
        seen.insert(num);
    }
    return false;
}

// 两数之和
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;  // 值->索引
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.count(complement)) {
            return {map[complement], i};
        }
        map[nums[i]] = i;
    }
    return {};
}

// 字符串中第一个不重复的字符
int firstUniqChar(string s) {
    unordered_map<char, int> count;
    for (char c : s) count[c]++;
    for (int i = 0; i < s.length(); i++) {
        if (count[s[i]] == 1) return i;
    }
    return -1;
}

常见应用：去重、计数、查找配对、缓存
时间复杂度：平均O(1)查找和插入
空间换时间：用额外空间换取时间效率
STL容器：unordered_set、unordered_map

8. 如何在 C++ 中实现并查集？

class UnionFind {
    vector<int> parent;
    vector<int> rank;  // 秩（树的高度）
    
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 初始每个元素是自己的父节点
        }
    }
    
    // 查找根节点（路径压缩）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }
    
    // 合并两个集合（按秩合并）
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
    
    // 判断是否在同一集合
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

核心操作：find（查找）、union（合并）
优化技巧：①路径压缩（find时将节点直接连到根）②按秩合并（矮树连到高树）
时间复杂度：接近O(1)（反阿克曼函数）
应用：连通性问题、最小生成树（Kruskal）、朋友圈、岛屿数量

9. 如何使用 STL 实现有序容器？

// set：有序集合，不允许重复
set<int> s = {3, 1, 4, 1, 5};  // 自动排序去重：{1,3,4,5}
s.insert(2);
s.erase(3);
if (s.count(4)) cout << "存在";
auto it = s.lower_bound(3);  // 第一个>=3的元素

// multiset：允许重复
multiset<int> ms = {1, 2, 2, 3};
ms.erase(ms.find(2));  // 只删除一个2

// map：有序键值对
map<string, int> m;
m["apple"] = 1;
m.insert({"banana", 2});
for (auto& [key, val] : m) {  // 按key有序遍历
    cout << key << ":" << val;
}

// multimap：key可重复
multimap<int, string> mm;
mm.insert({1, "one"});
mm.insert({1, "uno"});

底层实现：红黑树（平衡二叉搜索树）
时间复杂度：插入、删除、查找都是O(log n)
有序性：按key自动排序，可自定义比较函数
迭代器稳定：插入删除不影响其他迭代器
与unordered对比：有序但慢，unordered无序但快

10. 如何使用 C++ 实现二分查找树？

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BST {
    TreeNode* root;
    
    // 插入（递归）
    TreeNode* insert(TreeNode* node, int val) {
        if (!node) return new TreeNode(val);
        if (val < node->val) {
            node->left = insert(node->left, val);
        } else if (val > node->val) {
            node->right = insert(node->right, val);
        }
        return node;
    }
    
    // 查找
    TreeNode* search(TreeNode* node, int val) {
        if (!node || node->val == val) return node;
        if (val < node->val) return search(node->left, val);
        return search(node->right, val);
    }
    
    // 删除
    TreeNode* deleteNode(TreeNode* node, int val) {
        if (!node) return nullptr;
        if (val < node->val) {
            node->left = deleteNode(node->left, val);
        } else if (val > node->val) {
            node->right = deleteNode(node->right, val);
        } else {
            // 找到要删除的节点
            if (!node->left) return node->right;
            if (!node->right) return node->left;
            // 两个子节点：找右子树最小值替换
            TreeNode* minNode = findMin(node->right);
            node->val = minNode->val;
            node->right = deleteNode(node->right, minNode->val);
        }
        return node;
    }
    
    TreeNode* findMin(TreeNode* node) {
        while (node->left) node = node->left;
        return node;
    }
    
public:
    BST() : root(nullptr) {}
    void insert(int val) { root = insert(root, val); }
    bool search(int val) { return search(root, val) != nullptr; }
    void remove(int val) { root = deleteNode(root, val); }
};