【C++上岸】C++常见面试题目--数据结构篇（第十七期）

大家好！😊 欢迎来到第十七期C++面试系列博文。今天，我们聚焦数据结构篇，涵盖常见面试题：哈希防碰撞算法、字符串哈希、贪心算法、动态规划、回溯算法的基本原理，以及几个经典问题（如小饼干分配、摆动序列等）。我会用通俗语言解释概念，提供C++代码示例，记住，面试时理解原理比死记硬背更重要哦！💡 文章结构清晰，一步步带你解题。准备好了吗？Let’s go! 🚀

---

---

一、哈希防碰撞算法

哈希表是C++面试高频考点（如std::unordered_map），但哈希碰撞（多个键映射到同一槽位）会影响性能。防碰撞算法就是解决这个问题的利器！核心思想是：当碰撞发生时，通过特定策略重新定位键值对。常见方法有：

• 开放寻址法：如果槽位被占用，就探测下一个可用位置（如线性探测：$h^{\prime }(k)=(h(k)+i)\mathrm{mod}m$，其中$i$是探测次数，$m$是表大小）。
• 链地址法：每个槽位用链表存储冲突元素（C++的std::unordered_map默认用此方法）。
  这些方法平衡了时间和空间复杂度，一般时间复杂度为$O(1)$平均情况。记住，选择合适哈希函数是关键！😎

---

二、字符串哈希

字符串哈希常用于快速比较或匹配字符串（如Rabin-Karp算法）。核心是将字符串映射到整数，避免逐字符比较。常用多项式哈希：
$$h(s)=\sum _{i=0}^{n-1}s[i]\times p^i\mathrm{mod}m$$
其中$s[i]$是字符的ASCII值，$p$是质数（如31），$m$是大质数（如$10^9+7$）。这能减少碰撞概率。例如，字符串"abc"的哈希计算为：
$$h=(97\times p^2+98\times p^1+99\times p^0)\mathrm{mod}m$$
在C++中，可用于高效实现字符串搜索。代码示例（计算哈希值）：

#include <string>
using namespace std;long long computeHash(string s, int p = 31, long long m = 1e9+7) {long long hash = 0;long long power = 1;for (char c : s) {hash = (hash + (c - 'a' + 1) * power) % m; // 假设小写字母power = (power * p) % m;}return hash;
}
// 时间复杂度：O(n)，空间复杂度：O(1)

---

三、贪心算法基本原理

贪心算法超实用！🎯 核心思想：每一步选择当前最优解，希望最终达到全局最优。它简单高效，但需问题满足“贪心选择性质”（局部最优能导向全局最优）。应用场景包括：最短路径、调度问题等。

• 优点：时间复杂度低，常为$O(n\log n)$或$O(n)$。
• 缺点：不保证所有问题都最优（需证明贪心策略有效）。
  例如，在“小饼干问题”中，贪心策略能完美解决（见下文）。记住：面试时，先分析问题是否适合贪心哦！💪

---

四、动态规划基本原理

动态规划（DP）是解决最优化问题的神器！✨ 核心思想：将问题分解为重叠子问题，存储子问题解，避免重复计算。关键概念：

• 最优子结构：全局最优解包含子问题最优解（如$dp[i]=\max (dp[i-1]+nums[i],nums[i])$）。
• 重叠子问题：子问题被多次计算，用表格（数组）存储结果。
  DP通常用自底向上（迭代）或自顶向下（递归+记忆化）实现。时间复杂度取决于状态数，空间可优化。在“最大子数组和”问题中，DP大显身手（见下文）！😊

---

五、回溯算法基本原理

回溯算法是“试错法”，常用于组合、排列问题（如八皇后）。🎭 核心思想：深度优先搜索（DFS），尝试所有可能路径，无效时回溯。

• 步骤：选择路径 → 递归探索 → 失败则撤销选择（剪枝优化效率）。
• 关键：递归函数设计，状态恢复（避免全局污染）。
  时间复杂度常为$O(2^n)$或$O(n!)$，但剪枝能显著提升性能。在“股票买卖”问题中，回溯可解但贪心更优（见下文）。面试时，注意边界条件！🚫

---

六、经典问题详解

下面，我们逐一解决大纲中的问题。我会给出算法思路、C++代码和复杂度分析，确保你理解透彻！每个问题都贴切对应算法原理。

1. 小饼干问题（贪心算法应用）

题目：作为家长，你有孩子胃口值数组g和饼干尺寸数组s。每个孩子最多一块饼干，若$s[j]\ge g[i]$，则孩子满足。求最大满足孩子数。
贪心原理：排序后，用最小饼干满足最小胃口孩子，确保“局部最优”导向全局最大。
算法步骤：

1. 排序g和s（升序）。
2. 双指针遍历：饼干指针$j$，孩子指针$i$。
3. 如果$s[j]\ge g[i]$，则满足孩子，$i$和$j$均增；否则只增$j$（换更大饼干）。
   C++代码：

#include <algorithm>
#include <vector>
using namespace std;int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end()); // 排序孩子胃口sort(s.begin(), s.end()); // 排序饼干尺寸int i = 0, j = 0;while (i < g.size() && j < s.size()) {if (s[j] >= g[i]) i++; // 满足孩子j++; // 移动饼干指针}return i; // 最大满足数
}
// 时间复杂度：O(n log n)（排序主导），空间复杂度：O(1)

解释：排序后贪心匹配，时间复杂度主要由排序决定。🎯 测试用例：g = [1,2,3], s = [1,1]，输出1（只能满足一个孩子）。

2. 摆动序列（贪心或动态规划）

题目：求整数序列的最长摆动子序列长度（序列差正负交替）。
贪心原理：直接遍历序列，计数符号变化点（忽略非摆动元素）。
算法步骤：

1. 处理边界（序列长度$<2$，直接返回长度）。
2. 初始化摆动长度$len=1$（至少一个元素），前一个差值$prevDiff$。
3. 遍历数组，计算当前差值$diff=nums[i]-nums[i-1]$。
4. 如果$(prevDiff\le 0$ and $diff>0)$ or $(prevDiff\ge 0$ and $diff<0)$，则$len++$，并更新$prevDiff=diff$。
   C++代码（贪心实现）：

#include <vector>
using namespace std;int wiggleMaxLength(vector<int>& nums) {if (nums.size() < 2) return nums.size();int len = 1;int prevDiff = 0;for (int i = 1; i < nums.size(); i++) {int diff = nums[i] - nums[i-1];if ((prevDiff <= 0 && diff > 0) || (prevDiff >= 0 && diff < 0)) {len++;prevDiff = diff; // 更新差值}}return len;
}
// 时间复杂度：O(n)，空间复杂度：O(1)

解释：贪心高效，一次遍历搞定！😊 测试用例：nums = [1,7,4,9,2,5]，输出6（整个序列是摆动）。动态规划也可解（定义$up[i]$和$down[i]$为以$i$结尾的最长摆动），但贪心更优。

3. 最大子数组和（动态规划应用）

题目：求整数数组nums的连续子数组最大和。
DP原理：定义$dp[i]$为以$i$结尾的最大子数组和，状态转移：$dp[i]=\max (dp[i-1]+nums[i],nums[i])$。
算法步骤：

1. 初始化$dp[0]=nums[0]$，全局最大和$maxSum=dp[0]$。
2. 遍历数组，更新$dp[i]$和$maxSum$。
3. 空间优化：用变量代替数组。
   C++代码（空间优化版）：

#include <vector>
#include <algorithm>
using namespace std;int maxSubArray(vector<int>& nums) {int currSum = nums[0];int maxSum = nums[0];for (int i = 1; i < nums.size(); i++) {currSum = max(nums[i], currSum + nums[i]); // 状态转移maxSum = max(maxSum, currSum);}return maxSum;
}
// 时间复杂度：O(n)，空间复杂度：O(1)

解释：Kadane’s algorithm经典案例！💡 测试用例：nums = [-2,1,-3,4,-1,2,1,-5,4]，输出6（子数组[4,-1,2,1]）。

4. 股票买卖问题（贪心算法应用）

题目：数组prices表示股票每天价格，可多次买卖（买前必须卖出），求最大利润。
贪心原理：只要价格上升就买卖（累积所有正差值）。
算法步骤：

1. 遍历数组，从第2天开始。
2. 如果$prices[i]>prices[i-1]$，则利润增加$prices[i]-prices[i-1]$。
   C++代码：

#include <vector>
using namespace std;int maxProfit(vector<int>& prices) {int profit = 0;for (int i = 1; i < prices.size(); i++) {if (prices[i] > prices[i-1]) {profit += prices[i] - prices[i-1]; // 贪心累积利润}}return profit;
}
// 时间复杂度：O(n)，空间复杂度：O(1)

解释：贪心简单高效！🚀 测试用例：prices = [7,1,5,3,6,4]，输出7（买1卖5赚4，买3卖6赚3）。回溯算法可解但效率低（$O(2^n)$），贪心更优。

5. 跳跃游戏（贪心算法应用）

题目：非负整数数组nums，每个元素表示可跳跃长度，判断是否能从起点到终点。
贪心原理：维护最远可达位置，遍历更新。
算法步骤：

1. 初始化最远位置$maxReach=0$。
2. 遍历数组，如果当前位置$i>maxReach$，则返回false。
3. 更新$maxReach=\max (maxReach,i+nums[i])$。
4. 如果$maxReach\ge$ 数组末位，返回true。
   C++代码：

#include <vector>
using namespace std;bool canJump(vector<int>& nums) {int maxReach = 0;for (int i = 0; i < nums.size(); i++) {if (i > maxReach) return false; // 无法到达当前位置maxReach = max(maxReach, i + nums[i]);if (maxReach >= nums.size() - 1) return true; // 提前终止}return true;
}
// 时间复杂度：O(n)，空间复杂度：O(1)

解释：贪心一次遍历，高效判断！🎯 测试用例：nums = [2,3,1,1,4]，输出true；nums = [3,2,1,0,4]，输出false。

---

结语

恭喜你坚持到这里！👏 本期我们覆盖了哈希、字符串哈希、贪心、DP、回溯的基本原理，并实战解决了5个高频面试题。记住：理解算法思想比硬背代码更重要，多练习才能在面试中游刃有余。😊 如果有疑问，欢迎评论区讨论～ 下期见！🚀

关键词回顾：哈希防碰撞、字符串哈希、贪心算法、动态规划、回溯算法、C++面试。
表情包彩蛋：学习数据结构就像搭积木🧩——一步一个脚印，稳扎稳打才能上岸！💪