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

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

---

---

1. 子集问题

题目描述：给定无重复元素的数组 nums，返回所有可能的子集（包括空集）。
算法思路：使用回溯法（深度优先搜索）。从空集开始，逐步添加元素，递归生成所有子集。时间复杂度为 $O(2^n)$，因为每个元素都有“选”或“不选”两种状态。
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\times N$ 的棋盘上放置 $N$ 个皇后，使得任意两个皇后不在同一行、同一列、同一对角线，返回所有合法的放置方案。
算法思路：回溯法，逐行放置皇后。每行尝试每个列位置，检查是否与已放置皇后冲突（列或对角线）。如果冲突，跳过；否则递归放置下一行。时间复杂度为 $O(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$ 时，输出可能包括两个方案：皇后位置如 [".Q..","...Q","Q...","..Q."]。

---

3. 组合和问题

题目描述：给定无重复元素的数组 candidates 和目标值 target，返回所有和为 target 的组合（元素不重复使用）。
算法思路：回溯法，类似子集问题，但需控制元素不重复使用且和为 target。排序数组后，递归时跳过重复元素和超过 target 的路径。时间复杂度为 $O(2^n)$，实际通过剪枝优化。
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 次（可以多次选择同一个索引）。返回修改后数组的最大和。
算法思路：贪心算法。优先翻转绝对值最小的负数（因为翻转负数能增加和），如果负数翻转完还有剩余次数，则反复翻转最小绝对值的元素（可能是正数或零）。最终和计算公式为：
$$\text{sum}=\sum _{i=0}^{n-1}A[i]\text{after flips}$$
时间复杂度为 $O(n\log n)$，主要来自排序。
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)$。
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 阶的方法数，则状态转移方程为：
$$dp[i]=dp[i-1]+dp[i-2]\text{for}i\ge 2$$
其中，$dp[0]=1$（空方法），$dp[1]=1$。这本质是斐波那契数列。时间复杂度 $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]=1for (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] 结尾的最长递增子序列长度。状态转移：
$$dp[i]=\underset{j<i\text{ and }nums[j]<nums[i]}{\max }(dp[j])+1$$
时间复杂度 $O(n^2)$。优化方法（如二分搜索）可达到 $O(n\log n)$，但这里展示基础版。
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数组，每个元素至少为1int 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 所需的最少硬币数。状态转移：
$$dp[i]=\underset{coin\in coins}{\min }(dp[i-coin]+1)\text{if}i\ge coin$$
初始化 $dp[0]=0$，其他为较大值。时间复杂度 $O(n\times m)$，其中 $n$ 为金额，$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 的子集。状态转移：
$$dp[j]=dp[j]\vee dp[j-nums[i]]\text{for}j\text{ from sum/2 down to nums[i]}$$
时间复杂度 $O(n\times \text{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，返回完成所有任务的最短时间。
算法思路：贪心算法。优先安排频率最高的任务，以最大化利用冷却时间。最短时间计算公式：
$$\text{time}=\max (\text{len}(tasks),(\text{maxFreq}-1)\times (n+1)+\text{countMax})$$
其中，$\text{maxFreq}$ 是最高频率，$\text{countMax}$ 是最高频率任务的数量。时间复杂度 $O(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++上岸”之旅！🔥