当前位置：首页 > web >正文

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

web 2025/9/7 23:21:28

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

1. 移动零

要求：原地将数组中的零移到末尾，保持非零元素顺序。
思路：双指针法。指针left标记非零元素位置，遍历数组，遇到非零元素就交换到left处。

void moveZeroes(vector<int>& nums) {for (int left = 0, i = 0; i < nums.size(); i++) {if (nums[i] != 0) swap(nums[left++], nums[i]);}
}

时间复杂度： $O (n)$ ，空间复杂度： $O (1)$ 。
（假装有图）

2. 比较含退格的字符串

要求：#代表退格，判断两字符串是否相等。
思路：重构字符串（模拟栈）。遇到非#入栈，遇到#出栈。

bool backspaceCompare(string s, string t) {return build(s) == build(t);
}
string build(string str) {string res;for (char c : str) {if (c == '#') { if (!res.empty()) res.pop_back(); }else res.push_back(c);}return res;
}

时间复杂度： $O (n)$ ，空间复杂度： $O (n)$ 。

3. 有序数组的平方

要求：非递减数组平方后仍非递减。
思路：双指针从两端向中间遍历，比较平方值。

vector<int> sortedSquares(vector<int>& nums) {int left = 0, right = nums.size() - 1;vector<int> res(nums.size());for (int i = nums.size() - 1; i >= 0; i--) {if (abs(nums[left]) > abs(nums[right])) {res[i] = nums[left] * nums[left];left++;} else {res[i] = nums[right] * nums[right];right--;}}return res;
}

时间复杂度： $O (n)$ 。

4. 长度最小的子数组

要求：和≥s的最短连续子数组长度。
思路：滑动窗口。右指针扩张，左指针收缩。

int minSubArrayLen(int target, vector<int>& nums) {int left = 0, sum = 0, minLen = INT_MAX;for (int right = 0; right < nums.size(); right++) {sum += nums[right];while (sum >= target) {minLen = min(minLen, right - left + 1);sum -= nums[left++];}}return minLen == INT_MAX ? 0 : minLen;
}

时间复杂度： $O (n)$ 。

5. 水果成篮

要求：最多收集两种水果的最大连续数量。
思路：滑动窗口+哈希表记录水果类型数。

int totalFruit(vector<int>& fruits) {unordered_map<int, int> basket;int left = 0, maxFruits = 0;for (int right = 0; right < fruits.size(); right++) {basket[fruits[right]]++;while (basket.size() > 2) {if (--basket[fruits[left]] == 0) basket.erase(fruits[left]);left++;}maxFruits = max(maxFruits, right - left + 1);}return maxFruits;
}

时间复杂度： $O (n)$ 。

6. 最小覆盖子串

要求：s中包含t所有字符的最短子串。
思路：滑动窗口+双哈希表（需求窗口+当前窗口）。

string minWindow(string s, string t) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, valid = 0, start = 0, minLen = INT_MAX;for (int right = 0; right < s.size(); right++) {char c = s[right];if (need.count(c)) {window[c]++;if (window[c] == need[c]) valid++;}while (valid == need.size()) {if (right - left < minLen) {minLen = right - left;start = left;}char d = s[left++];if (need.count(d)) {if (window[d] == need[d]) valid--;window[d]--;}}}return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

时间复杂度： $O (n)$ 。

7. 螺旋矩阵 II

要求：生成顺时针螺旋的 $\times n$ 矩阵。
思路：模拟螺旋路径，控制边界。

vector<vector<int>> generateMatrix(int n) {vector<vector<int>> matrix(n, vector<int>(n));int top = 0, bottom = n - 1, left = 0, right = n - 1;int num = 1;while (num <= n * n) {for (int i = left; i <= right; i++) matrix[top][i] = num++;top++;for (int i = top; i <= bottom; i++) matrix[i][right] = num++;right--;for (int i = right; i >= left; i--) matrix[bottom][i] = num++;bottom--;for (int i = bottom; i >= top; i--) matrix[i][left] = num++;left++;}return matrix;
}

示例：n=3 → [[1,2,3],[8,9,4],[7,6,5]]。

8. 螺旋遍历二维数组

要求：返回二维数组的螺旋遍历结果。
思路：同问题7，按层模拟方向。

vector<int> spiralOrder(vector<vector<int>>& matrix) {if (matrix.empty()) return {};int m = matrix.size(), n = matrix[0].size();int top = 0, bottom = m - 1, left = 0, right = n - 1;vector<int> res;while (res.size() < m * n) {for (int i = left; i <= right; i++) res.push_back(matrix[top][i]);top++;for (int i = top; i <= bottom; i++) res.push_back(matrix[i][right]);right--;if (top <= bottom) {for (int i = right; i >= left; i--) res.push_back(matrix[bottom][i]);bottom--;}if (left <= right) {for (int i = bottom; i >= top; i--) res.push_back(matrix[i][left]);left++;}}return res;
}

9. 区间求和

要求：多次查询数组区间和。
思路：前缀和预处理。

int main() {int n;cin >> n;vector<int> nums(n), prefix(n + 1, 0);for (int i = 0; i < n; i++) {cin >> nums[i];prefix[i + 1] = prefix[i] + nums[i];}int l, r;while (cin >> l >> r) {cout << prefix[r + 1] - prefix[l] << endl; // [l, r]区间和}
}

时间复杂度：查询 $O (1)$ ，预处理 $O (n)$ 。

10. 土地价值最小差

要求：横向或纵向切割网格，使两区域价值和差最小。
思路：枚举切割线 + 前缀和优化。

int minDifference(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();// 计算行前缀和vector<vector<int>> rowSum(n, vector<int>(m + 1, 0));for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) rowSum[i][j + 1] = rowSum[i][j] + grid[i][j];int total = 0, minDiff = INT_MAX;for (auto& row : grid) for (int val : row) total += val;// 枚举横向切割for (int i = 1; i < n; i++) {int sumTop = 0;for (int k = 0; k < i; k++) sumTop += rowSum[k][m];minDiff = min(minDiff, abs(2 * sumTop - total));}// 枚举纵向切割（类似）// ...return minDiff;
}