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 (!ro