【C++上岸】C++常见面试题目--算法篇（第十八期）

发布于：2025-09-05 ⋅ 阅读:(19) ⋅ 点赞:(0)

大家好！😊 欢迎来到“C++上岸”系列的第18期——算法篇！算法是面试中的硬核关卡，掌握好这些经典问题，能让你在笔试和面试中游刃有余。今天，我们精选了10道高频算法题，涵盖回溯、动态规划、贪心等核心思想。我会逐一详细解答，包括算法思路和C++代码实现。🔥准备好了吗？让我们开始吧！

文章目录

1. 子集问题

题目描述：给定无重复元素的数组 nums，返回所有可能的子集（包括空集）。
算法思路：使用回溯法（深度优先搜索）。从空集开始，逐步添加元素，递归生成所有子集。时间复杂度为 O ( 2 n ) O(2^n) O(2n)，因为每个元素都有“选”或“不选”两种状态。
C++代码实现：

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(nums, 0, path, result);
        return result;
    }

    void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result) {
        result.push_back(path);  // 添加当前子集
        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);          // 选择当前元素
            backtrack(nums, i + 1, path, result); // 递归
            path.pop_back();                  // 回溯，撤销选择
        }
    }
};

解释：代码中，backtrack 函数递归生成子集。初始调用时 start=0，表示从第一个元素开始。每个元素被添加到 path 中，然后递归处理后续元素。最后，path 被弹出以回溯。😎 试试输入 [1,2,3]，输出会包括 [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]！

2. N皇后问题

题目描述：在 N × N N×N N×N 的棋盘上放置 N N N 个皇后，使得任意两个皇后不在同一行、同一列、同一对角线，返回所有合法的放置方案。
算法思路：回溯法，逐行放置皇后。每行尝试每个列位置，检查是否与已放置皇后冲突（列或对角线）。如果冲突，跳过；否则递归放置下一行。时间复杂度为 O ( N ! ) O(N!) O(N!)，因为每行有 N N N 种选择，但实际通过剪枝优化。
C++代码实现：

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.')); // 初始化棋盘
        backtrack(0, board, result, n);
        return result;
    }

    void backtrack(int row, vector<string>& board, vector<vector<string>>& result, int n) {
        if (row == n) {
            result.push_back(board);  // 找到一个合法方案
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isValid(board, row, col, n)) {
                board[row][col] = 'Q';          // 放置皇后
                backtrack(row + 1, board, result, n); // 递归下一行
                board[row][col] = '.';          // 回溯，移除皇后
            }
        }
    }

    bool isValid(vector<string>& board, int row, int col, int n) {
        // 检查列冲突
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // 检查左上对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // 检查右上对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
};

解释：isValid 函数检查当前位置是否安全。回溯函数在每行尝试所有列，如果合法则放置皇后并递归。👑 例如，当 N = 4 N=4 N=4 时，输出可能包括两个方案：皇后位置如 [".Q..","...Q","Q...","..Q."]。

3. 组合和问题

题目描述：给定无重复元素的数组 candidates 和目标值 target，返回所有和为 target 的组合（元素不重复使用）。
算法思路：回溯法，类似子集问题，但需控制元素不重复使用且和为 target。排序数组后，递归时跳过重复元素和超过 target 的路径。时间复杂度为 O ( 2 n ) O(2^n) O(2n)，实际通过剪枝优化。
C++代码实现：

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end()); // 排序便于剪枝
        vector<vector<int>> result;
        vector<int> path;
        backtrack(candidates, target, 0, path, result);
        return result;
    }

    void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, vector<vector<int>>& result) {
        if (target == 0) {
            result.push_back(path);  // 找到一个组合
            return;
        }
        for (int i = start; i < candidates.size(); i++) {
            if (i > start && candidates[i] == candidates[i-1]) continue; // 跳过重复元素
            if (candidates[i] > target) break; // 剪枝：剩余值不足
            path.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, result); // 递归，元素不重复使用
            path.pop_back(); // 回溯
        }
    }
};

解释：排序后，在循环中跳过重复值（i > start && candidates[i] == candidates[i-1]），避免重复组合。💡 例如，输入 candidates = [10,1,2,7,6,1], target=8，输出可能为 [[1,1,6], [1,2,5], [1,7], [2,6]]（注意元素不重复使用）。

4. 最大和问题

题目描述：给定一个整数数组 A，我们可以选择索引 i 将 A[i] 替换为 -A[i]，重复 K 次（可以多次选择同一个索引）。返回修改后数组的最大和。
算法思路：贪心算法。优先翻转绝对值最小的负数（因为翻转负数能增加和），如果负数翻转完还有剩余次数，则反复翻转最小绝对值的元素（可能是正数或零）。最终和计算公式为：
sum = ∑ i = 0 n − 1 A [ i ] after flips \text{sum} = \sum_{i=0}^{n-1} A[i] \quad \text{after flips} sum=i=0∑n−1​A[i]after flips
时间复杂度为 O ( n log ⁡ n ) O(n \log n) O(nlogn)，主要来自排序。
C++代码实现：

#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(), A.end()); // 排序便于处理
        // 优先翻转负数
        for (int i = 0; i < A.size() && K > 0; i++) {
            if (A[i] < 0) {
                A[i] = -A[i];
                K--;
            }
        }
        // 如果K还有剩余，反复翻转最小绝对值的元素
        if (K % 2 == 1) { // 奇数次翻转才影响和
            auto min_it = min_element(A.begin(), A.end());
            *min_it = -(*min_it);
        }
        int sum = 0;
        for (int num : A) sum += num;
        return sum;
    }
};

解释：先排序数组，然后遍历翻转负数。如果 K 剩余，翻转最小元素（因为翻转偶数次等于没变）。🎯 例如，输入 A = [4,2,3], K=1，翻转最小元素2得 [-2,4,3]，和为5。

5. 加油站问题

题目描述：在一条环路上有 N 个加油站，第 i 个有汽油 gas[i] 升，从 i 到 i+1 消耗 cost[i] 升。从某个加油站出发（油箱空），如果可以绕行一周，返回起始站编号，否则返回 -1。
算法思路：贪心算法。计算每个站的剩余油量（gas[i] - cost[i]），如果总剩余油量小于0，则无解；否则，从起点0开始，累加剩余油量，如果当前累计量小于0，则重置起点为下一站。时间复杂度 O ( n ) O(n) O(n)。
C++代码实现：

#include <vector>
using namespace std;

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0, current = 0, start = 0;
        for (int i = 0; i < gas.size(); i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            current += diff;
            if (current < 0) {
                start = i + 1; // 重置起点
                current = 0;    // 重置当前累计
            }
        }
        return total >= 0 ? start : -1; // 总剩余油量非负则有解
    }
};

解释：total 检查全局可行性，current 模拟当前油箱。如果 current<0，说明从当前起点无法继续，重置起点。🚗 例如，输入 gas = [1,2,3,4,5], cost = [3,4,5,1,2]，输出 3（从索引3出发可行）。

6. 爬楼梯问题

题目描述：需要爬 n 阶楼梯，每次可以爬 1 或 2 阶，返回不同方法数。
算法思路：动态规划。定义 dp[i] 为爬 i 阶的方法数，则状态转移方程为：
d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] for i ≥ 2 dp[i] = dp[i-1] + dp[i-2] \quad \text{for} \quad i \geq 2 dp[i]=dp[i−1]+dp[i−2]fori≥2
其中， d p [ 0 ] = 1 dp[0] = 1 dp[0]=1（空方法）， d p [ 1 ] = 1 dp[1] = 1 dp[1]=1。这本质是斐波那契数列。时间复杂度 O ( n ) O(n) O(n)。
C++代码实现：

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1, b = 1; // dp[0]=1, dp[1]=1
        for (int i = 2; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
};

解释：用两个变量 a 和 b 模拟斐波那契，避免递归开销。😄 例如，n=3 时，方法数为3（1+2, 2+1, 1+1+1）。

7. 最长递增子序列问题

题目描述：给定整数数组 nums，找到最长严格递增子序列的长度。
算法思路：动态规划。定义 dp[i] 为以 nums[i] 结尾的最长递增子序列长度。状态转移：
d p [ i ] = max ⁡ j < i  and  n u m s [ j ] < n u m s [ i ] ( d p [ j ] ) + 1 dp[i] = \max_{j < i \text{ and } nums[j] < nums[i]} (dp[j]) + 1 dp[i]=j<i and nums[j]<nums[i]max​(dp[j])+1
时间复杂度 O ( n 2 ) O(n^2) O(n2)。优化方法（如二分搜索）可达到 O ( n log ⁡ n ) O(n \log n) O(nlogn)，但这里展示基础版。
C++代码实现：

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> dp(n, 1); // 初始化dp数组，每个元素至少为1
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
};

解释：双层循环，内层找比 nums[i] 小的元素更新 dp[i]。📈 例如，输入 nums = [10,9,2,5,3,7,101,18]，输出 4（序列如 [2,5,7,101]）。

8. 硬币找零问题

题目描述：给定硬币 coins 表示不同面额，总金额 amount，返回凑成金额的最少硬币数；如果不行，返回 -1（硬币无限）。
算法思路：动态规划（完全背包）。定义 dp[i] 为金额 i 所需的最少硬币数。状态转移：
d p [ i ] = min ⁡ c o i n ∈ c o i n s ( d p [ i − c o i n ] + 1 ) if i ≥ c o i n dp[i] = \min_{coin \in coins} (dp[i - coin] + 1) \quad \text{if} \quad i \geq coin dp[i]=coin∈coinsmin​(dp[i−coin]+1)ifi≥coin
初始化 d p [ 0 ] = 0 dp[0] = 0 dp[0]=0，其他为较大值。时间复杂度 O ( n × m ) O(n \times m) O(n×m)，其中 n n n 为金额， m m m 为硬币种类数。
C++代码实现：

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX - 1); // 避免溢出
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == INT_MAX - 1 ? -1 : dp[amount];
    }
};

解释：遍历金额，对每个硬币尝试更新 dp[i]。💸 例如，输入 coins = [1,2,5], amount=11，输出 3（5+5+1）。

9. 分割等和子集问题

题目描述：给定正整数数组 nums，判断是否可以分割成两个子集，元素和相等。
算法思路：动态规划（0-1背包）。先计算总和，如果总和为奇数则无解；否则，目标为 text{sum}/2。定义 dp[i] 表示能否凑出和为 i 的子集。状态转移：
d p [ j ] = d p [ j ] ∨ d p [ j − n u m s [ i ] ] for j  from sum/2 down to nums[i] dp[j] = dp[j] \lor dp[j - nums[i]] \quad \text{for} \quad j \text{ from sum/2 down to nums[i]} dp[j]=dp[j]∨dp[j−nums[i]]forj from sum/2 down to nums[i]
时间复杂度 O ( n × sum / 2 ) O(n \times \text{sum}/2) O(n×sum/2)。
C++代码实现：

#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if (total % 2 != 0) return false;
        int target = total / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }
};

解释：逆序遍历 j 避免重复使用元素。⚖️ 例如，输入 nums = [1,5,11,5]，总和22，目标11，输出 true（子集如 [1,5,5] 和 [11]）。

10. 任务调度问题

题目描述：给定任务列表 tasks，每个任务单位时间完成，相同任务之间必须有冷却时间 n，返回完成所有任务的最短时间。
算法思路：贪心算法。优先安排频率最高的任务，以最大化利用冷却时间。最短时间计算公式：
time = max ⁡ ( len ( t a s k s ) , ( maxFreq − 1 ) × ( n + 1 ) + countMax ) \text{time} = \max(\text{len}(tasks), (\text{maxFreq} - 1) \times (n + 1) + \text{countMax}) time=max(len(tasks),(maxFreq−1)×(n+1)+countMax)
其中， maxFreq \text{maxFreq} maxFreq 是最高频率， countMax \text{countMax} countMax 是最高频率任务的数量。时间复杂度 O ( m ) O(m) O(m)， m m m 为任务种类数。
C++代码实现：

#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> freq;
        for (char task : tasks) freq[task]++;
        int maxFreq = 0, countMax = 0;
        for (auto& [task, count] : freq) {
            if (count > maxFreq) {
                maxFreq = count;
                countMax = 1;
            } else if (count == maxFreq) {
                countMax++;
            }
        }
        int time = (maxFreq - 1) * (n + 1) + countMax;
        return max(time, (int)tasks.size());
    }
};

解释：计算最高频率任务，并插入冷却时间。⏱️ 例如，输入 tasks = ['A','A','A','B','B','B'], n=2，输出 8（序列如 A->B->idle->A->B->idle->A->B）。

总结

恭喜你坚持到了最后！🎉 本期我们覆盖了10道经典算法题，包括回溯、动态规划、贪心等核心思想。掌握这些，能让你在C++面试中脱颖而出。算法学习重在实践，建议多写代码和模拟测试。如果你有疑问或想讨论，欢迎留言！😊 下期见，继续“C++上岸”之旅！🔥

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布