C++ 后端面试必刷大厂算法题（附代码实现）第六期

C++ 后端面试必刷大厂算法题

文章目录

• C++ 后端面试必刷大厂算法题
• 一、240. 搜索二维矩阵 II
• 二、662. 二叉树最大宽度
• 三、543. 二叉树的直径
• 四、162. 寻找峰值
• 五、179. 最大数
• 六、152. 乘积最大子数组
• 七、113. 路径总和 II
• 八、62. 不同路径
• 九、560. 和为 K 的子数组
• 十、198. 打家劫舍
• 十一、112. 路径总和
• 十二、209. 长度最小的子数组
• 十三、24. 两两交换链表中的节点
• 十四、227. 基本计算器 II
• 十五、83. 删除排序链表中的重复元素
• 十六、226. 翻转二叉树
• 十七、169. 多数元素
• 十八、139. 单词拆分
• 十九、283. 移动零
• 二十、718. 最长重复子数组
• 总结

一、240. 搜索二维矩阵 II

代码如下（示例）：

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
// 这道题是一个好题，解题思路很新颖 , 但是你要按照自己的想法来做
int i = 0 , j = matrix[0].size() – 1;
while(i < matrix.size() && j >= 0)
{
if(matrix[i][j] > target)
{
j—;
}
else if(matrix[i][j] < target)
{
i++;
}
else
{
return true;
}
}
return false;
}
};

二、662. 二叉树最大宽度

代码如下（示例）：

class Solution {
public:
int widthOfBinaryTree(TreeNode* root)
{
vector<pair<TreeNode*, unsigned int>> q; // 用数组模拟队列
q.push_back({root, 1});
unsigned int ret = 0;
while (q.size())
{
// 先更新这一层的宽度
auto& [x1, y1] = q[0];
auto& [x2, y2] = q.back();
ret = max(ret, y2 – y1 + 1);
// 让下一层进队列
vector<pair<TreeNode*, unsigned int>> tmp; // 让下一层进入这个队列
for (auto& [x, y] : q)
{
if (x->left)
tmp.push_back({x->left, y * 2});
if (x->right)
tmp.push_back({x->right, y * 2 + 1});
}
q = tmp;
}
return ret;
}
};

// 自己写的 很重要
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int widthOfBinaryTree(TreeNode* root)
{
// 层序遍历来找二叉树最大宽度
vector<pair<TreeNode* , unsigned int>> q;
q.push_back({root , 1});
unsigned int res = 0;

while(q.size())
{
auto& [x1,y1] = q[0];
auto& [x2,y2] = q.back();
res = max(res , y2 – y1 + 1);

vector<pair<TreeNode* , unsigned int>> tmp;
for(auto& [x,y] : q)
{
if(x->left) tmp.push_back({x->left , y * 2});
if(x->right) tmp.push_back({x->right , y * 2 + 1});
}
q = tmp; // 层序遍历最重要的一步
}
return res;
}
};

三、543. 二叉树的直径

代码如下（示例）：

class Solution
{
private:
int maxDiameter = 0; // 全局变量：记录所有节点的最大直径

// 递归求高度，同时遍历所有节点计算直径
int getDepth(TreeNode* root)
{
if (root == NULL)
{
return 0; // 空节点高度为0（节点数定义）
}
int leftDepth = getDepth(root->left); // 左子树高度
int rightDepth = getDepth(root->right); // 右子树高度

// 关键：计算当前节点的直径，并更新全局最大值
int currentDiameter = leftDepth + rightDepth;
if (currentDiameter > maxDiameter)
{
maxDiameter = currentDiameter;
}

// 返回当前节点的高度（节点数）
return max(leftDepth, rightDepth) + 1;
}

public:
int diameterOfBinaryTree(TreeNode* root)
{
getDepth(root); // 触发递归：遍历所有节点，计算高度+更新最大直径
return maxDiameter;
}
};

// 自己写的
class Solution
{
// 全局变量求 二叉树的最大直径
int maxDiameter = 0;
public:
int getDepth(TreeNode* root)
{
if(root == nullptr) return 0;
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);

int currentDiameter = leftDepth + rightDepth;
if(currentDiameter > maxDiameter)
{
maxDiameter = currentDiameter;
}
return max(leftDepth , rightDepth) + 1;
}
int diameterOfBinaryTree(TreeNode* root)
{
getDepth(root);
return maxDiameter;
}
};

// 非递归的版本，看看就行
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root)
{
if (root == nullptr) return 0; // 空树直径为0

int maxDiameter = 0;
// 哈希表：存储每个节点的高度（节点数定义，空节点高度0）
unordered_map<TreeNode*, int> nodeHeight;
// 栈：存储<节点指针，是否已访问>，false=未处理左右子树，true=已处理
stack<pair<TreeNode*, bool>> stk;

stk.push({root, false});

while (!stk.empty())
{
auto [currNode, isVisited] = stk.top();
stk.pop();

if (!isVisited)
{
// 第一步：未访问过，先把当前节点压回栈（标记为已访问），再压入右、左子节点（栈是后进先出，保证左先处理）
stk.push({currNode, true});
if (currNode->right)
{
stk.push({currNode->right, false});
}
if (currNode->left)
{
stk.push({currNode->left, false});
}
}
else
{
// 第二步：已访问过（左右子树已处理），计算当前节点高度和直径
// 左子树高度：空节点为0，否则从哈希表取
int leftDepth = currNode->left ? nodeHeight[currNode->left] : 0;
// 右子树高度：同理
int rightDepth = currNode->right ? nodeHeight[currNode->right] : 0;

// 计算当前节点的直径，更新最大值
int currentDiameter = leftDepth + rightDepth;
maxDiameter = max(maxDiameter, currentDiameter);

// 计算当前节点的高度，存入哈希表
nodeHeight[currNode] = max(leftDepth, rightDepth) + 1;
}
}

return maxDiameter;
}
};

四、162. 寻找峰值

代码如下（示例）：

class Solution {
public:
int findPeakElement(vector<int>& nums)
{
// 二分查找
int left = 0 , right = nums.size() – 1;
while(left < right)
{
int mid = left + (right – left) / 2;
if(nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}
return left;
}
};

五、179. 最大数

代码如下（示例）：

class Solution {
public:
string largestNumber(vector<int>& nums)
{
// 优化：把所有的数转化成字符串
vector<string> strs;
for (int x : nums)
{
strs.push_back(to_string(x));
}
// 排序
sort(strs.begin(), strs.end(), [](const string& s1, const string& s2) {
return s1 + s2 > s2 + s1;
});
// 提取结果
string ret;
for (auto& s : strs)
{
ret += s;
}
if (ret[0] == '0')
{
return "0";
}
return ret;
}
};

// 自己写的
class Solution {
public:
string largestNumber(vector<int>& nums)
{
// 1.先把所有的数字转换为字符串
vector<string> strs;
for(auto x : nums)
{
strs.push_back(to_string(x));
}
// 2.排序strs
sort(strs.begin() , strs.end() , [](string& s1 , string& s2){
return s1 + s2 > s2 + s1;
});
// 3.提取结果
string res;
for(auto x : strs)
{
res += x;
}
if(res[0] == '0') return "0";
return res;
}
};

六、152. 乘积最大子数组

代码如下（示例）：

class Solution {
public:
int maxProduct(vector<int>& nums)
{
// 两个状态转移方程
int n = nums.size();
vector<int> f(n + 1);
vector<int> g(n + 1);
f[0] = g[0] = 1;
int ret = INT_MIN;

for(int i = 1 ; i <= n ; i++)
{
f[i] = max(nums[i – 1] , max(f[i – 1] * nums[i – 1] , g[i – 1] * nums[i – 1]));
g[i] = min(nums[i – 1] , min(f[i – 1] * nums[i – 1] , g[i – 1] * nums[i – 1]));
ret = max(ret , f[i]);
}
return ret;
}
};

class Solution {
public:
int maxProduct(vector<int>& nums)
{
int n = nums.size();
vector<int> f(n+1);
vector<int> g(n+1);
f[0] = g[0] = 1;
int ret = INT_MIN;
for(int i = 1 ; i <= n ; i++)
{
int x = nums[i–1] , y = f[i–1]*nums[i–1] , z = g[i–1]*nums[i–1];
f[i] = max(x , max(y , z));
g[i] = min(x , min(y , z));
ret = max(ret , f[i]);
}
return ret;
}
};

七、113. 路径总和 II

代码如下（示例）：

class Solution
{
int count; // 当前路径的和
int targetSum; // 目标和
vector<int> path; // 当前路径
vector<vector<int>> ret; // 最终结果

public:
void dfs(TreeNode* root)
{
if (root == nullptr) return; // 空节点直接返回（终止条件1）

// 1. 加入当前节点到路径，更新当前和
path.push_back(root->val);
count += root->val;

// 2. 终止条件2：当前是叶子节点 + 路径和等于目标和 → 加入结果
if (root->left == nullptr && root->right == nullptr && count == targetSum)
{
ret.push_back(path);
}

// 3. 递归遍历左右子树
dfs(root->left);
dfs(root->right);

// 4. 回溯：移除当前节点，恢复当前和
path.pop_back();
count -= root->val;
}

vector<vector<int>> pathSum(TreeNode* root, int target)
{
// 初始化成员变量（关键！）
targetSum = target;
dfs(root);
return ret;
}
};

// 自己写的
class Solution
{
// 其实就是之前的代码改装一下
int count;
int resultsum;
vector<int> path;
vector<vector<int>> res;
public:
void dfs(TreeNode* root)
{
if(root == nullptr) return;

count += root->val;
path.push_back(root->val);

if(root->left == nullptr && root->right == nullptr && count == resultsum)
{
res.push_back(path);
}

dfs(root->left);
dfs(root->right);

// 回溯
path.pop_back();
count -= root->val;
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum)
{
resultsum = targetSum;
dfs(root);
return res;
}
};

八、62. 不同路径

代码如下（示例）：

class Solution {
public:
int uniquePaths(int m, int n)
{
vector<vector<int>> dp(m+1 , vector<int>(n+1));
dp[0][1] = 1;
for(int i = 1 ; i <= m ; i++)
{
for(int j = 1 ; j <= n ; j++)
{
dp[i][j] = dp[i–1][j] + dp[i][j–1];
}
}
return dp[m][n];
}
};

九、560. 和为 K 的子数组

代码如下（示例）：

class Solution {
public:
int subarraySum(vector<int>& nums, int k)
{
// 哈希表：key = 前缀和，value = 该前缀和出现的次数
unordered_map<int, int> prefixSumCount;
// 初始化：前缀和为0的情况出现1次（处理从数组开头到当前位置和为k的情况）
prefixSumCount[0] = 1;

int currentSum = 0; // 当前累计的前缀和
int result = 0; // 记录符合条件的子数组个数

for (int num : nums)
{
currentSum += num; // 累加当前元素，更新前缀和

// 核心逻辑：如果存在前缀和 = currentSum – k，说明这两个前缀和之间的子数组和为k
if (prefixSumCount.find(currentSum – k) != prefixSumCount.end())
{
result += prefixSumCount[currentSum – k];
}

// 将当前前缀和存入哈希表（次数+1）
prefixSumCount[currentSum]++;
}

return result;
}
};

class Solution {
public:
int subarraySum(vector<int>& nums, int k)
{
unordered_map<int,int> hash;
hash[0] = 1;
int sum = 0;
int res = 0;

for(auto x : nums)
{
sum += x;
if(hash.count(sum – k))
{
res += hash[sum – k];
}
hash[sum]++;
}
return res;
}
};

十、198. 打家劫舍

代码如下（示例）：

class Solution
{
public:
int rob(vector<int>& nums)
{
// 边界情况：空数组直接返回0
if (nums.empty()) return 0;
int n = nums.size();
// 状态定义：
// f[i]：考虑前i间房屋，且第i间被偷时的最大金额
// g[i]：考虑前i间房屋，且第i间不被偷时的最大金额
vector<int> f(n + 1, 0);
vector<int> g(n + 1, 0);

// 初始状态：第1间房屋（i=1）
f[1] = nums[0]; // 偷第1间，金额就是nums[0]
g[1] = 0; // 不偷第1间，金额为0

// 状态转移：从第2间开始遍历
for (int i = 2; i <= n; i++)
{
// 第i间偷 → 第i-1间必须不偷，金额=前i-1间不偷的最大金额 + 第i间的金额
f[i] = g[i–1] + nums[i–1];
// 第i间不偷 → 第i-1间可偷可不偷，取两者最大值
g[i] = max(f[i–1], g[i–1]);
}

// 最终结果：前n间房屋，偷或不偷最后一间的最大值
return max(f[n], g[n]);
}
};

// 自己写的
class Solution {
public:
int rob(vector<int>& nums)
{
// 动态规划
if(nums.size() == 0) return 0;
int n = nums.size();
vector<int> f(n + 1 , 0);
vector<int> g(n + 1 , 0);
f[1] = nums[0] , g[1] = 0;

for(int i = 2 ; i <= n ; i++)
{
f[i] = g[i – 1] + nums[i – 1]; //注意重点
g[i] = max(f[i – 1] , g[i – 1]);
}
return max(f[n] , g[n]);
}
};

// 空间优化版本
class Solution {
public:
int rob(vector<int>& nums)
{
// 动态规划滚动数组空间优化
if(nums.size() == 0) return 0;
int n = nums.size();
int buy = nums[0] , nobuy = 0;

for(int i = 2 ; i <= n ; i++)
{
int currentbuy = nobuy + nums[i – 1];
int currentnobuy = max(buy , nobuy);

buy = currentbuy;
nobuy = currentnobuy;
}
return max(buy , nobuy);
}
};

十一、112. 路径总和

代码如下（示例）：

class Solution
{
public:
bool dfs(TreeNode* root, int currentSum, int targetSum)
{
// 边界：空节点（无路径）
if (root == nullptr) return false;

// 累加当前节点值到路径和
currentSum += root->val;

// 叶子节点：判断路径和是否等于目标和
if (root->left == nullptr && root->right == nullptr)
{
return currentSum == targetSum;
}

// 递归遍历左右子树：只要有一个子树返回true，就说明存在符合条件的路径
bool leftRes = dfs(root->left, currentSum, targetSum);
bool rightRes = dfs(root->right, currentSum, targetSum);

// 回溯（这里currentSum是值传递，无需手动减，函数栈退出后自动恢复）
return leftRes || rightRes;
}

bool hasPathSum(TreeNode* root, int targetSum)
{
return dfs(root, 0, targetSum);
}
};

class Solution {
public:
bool dfs(TreeNode* root , int currentSum , int targetSum)
{
if(root == nullptr) return false;
currentSum += root->val;

if(root->left == nullptr && root->right == nullptr)
{
return currentSum == targetSum;
}
// 这里不用回溯currentSum -= root->val 因为是值传递，不是传引用

bool leftres = dfs(root->left , currentSum , targetSum);
bool rightres = dfs(root->right , currentSum , targetSum);

return leftres || rightres;
}
bool hasPathSum(TreeNode* root, int targetSum)
{
return dfs(root , 0 , targetSum);
}
};

十二、209. 长度最小的子数组

代码如下（示例）：

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

十三、24. 两两交换链表中的节点

代码如下（示例）：

class Solution {
public:
ListNode* swapPairs(ListNode* head)
{
ListNode* dummy = new ListNode(0, head);
ListNode* node0 = dummy;
ListNode* node1 = head;
while (node1 && node1->next)
{
ListNode* node2 = node1->next;
ListNode* node3 = node2->next;

node0->next = node2; // 0 -> 2
node2->next = node1; // 2 -> 1
node1->next = node3; // 1 -> 3

node0 = node1; // 下一轮交换，0 是 1
node1 = node3; // 下一轮交换，1 是 3
}
return dummy->next; // 返回新链表的头节点
}
};

class Solution {
public:
ListNode* swapPairs(ListNode* head)
{
ListNode* dummy = new ListNode(0 , head);
ListNode* node0 = dummy;
ListNode* node1 = dummy->next;
while(node1 && node1->next)
{
ListNode* node2 = node1->next;
ListNode* node3 = node2->next;

node0->next = node2;
node2->next = node1;
node1->next = node3;

node0 = node1;
node1 = node3;
}
ListNode* cur = dummy->next;
delete dummy;
return cur;
}
};

代码如下（示例）：

class Solution {
public:
ListNode* swapPairs(ListNode* head)
{
if (head == nullptr || head->next == nullptr) return head;

ListNode* node1 = head;
ListNode* node2 = head->next;
ListNode* node3 = node2->next;

node1->next = swapPairs(node3); // 1 指向递归返回的链表头
node2->next = node1; // 2 指向 1

return node2; // 返回交换后的链表头节点
}
};

十四、227. 基本计算器 II

代码如下（示例）：

class Solution {
public:
int calculate(string s)
{
int i = 0 , n = s.size();
vector<int> st;
char op = '+';

while(i < n)
{
if(s[i] == ' ') i++;
else if(s[i] >= '0' && s[i] <= '9')
{
int tmp = 0;
while(i < n && s[i] >= '0' && s[i] <= '9')
{
tmp = tmp * 10 + (s[i++] – '0');
}

if(op == '+')
{
st.push_back(tmp);
}
else if(op == '-')
{
st.push_back(–tmp);
}
else if(op == '*')
{
st.back() *= tmp;
}
else
{
st.back() /= tmp;
}
}
else
{
op = s[i++];
}
}

// 提取结果
int ret = 0;
for(auto x : st)
{
ret += x;
}
return ret;
}
};

十五、83. 删除排序链表中的重复元素

代码如下（示例）：

class Solution {
public:
ListNode* deleteDuplicates(ListNode* head)
{
if (head == nullptr) return nullptr;
ListNode* cur = head;
while (cur->next) // 看看下个节点……
{
if (cur->next->val == cur->val)
{ // 和我一样，删！
cur->next = cur->next->next;
}
else
{ // 和我不一样，移动到下个节点
cur = cur->next;
}
}
return head;
}
};

class Solution {
public:
ListNode* deleteDuplicates(ListNode* head)
{
if(head == nullptr) return nullptr;
ListNode* cur = head;
while(cur->next != nullptr)
{
if(cur->next->val == cur->val)
{
cur->next = cur->next->next;
}
else
{
cur = cur->next;
}
}
return head;
}
};

十六、226. 翻转二叉树

代码如下（示例）：

class Solution {
public:
TreeNode* invertTree(TreeNode* root)
{
if (root == nullptr) return nullptr;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);

root->left = right;
root->right = left;
return root;
}
};

十七、169. 多数元素

代码如下（示例）：

class Solution {
public:
// 摩尔投票 ： 武林大会
int majorityElement(vector<int>& nums)
{
// 1. 初始化：候选元素为第一个元素，初始净票数为1
int consistant = nums[0]; // 候选元素（多数元素的候选）
int times = 1; // 净票数（候选元素的剩余票数）

// 2. 从第二个元素开始遍历，核心是「抵消」逻辑
for(int i = 1; i < nums.size(); i++)
{
// 情况1：当前元素 == 候选元素 → 净票数+1（同阵营，票数增加）
if(consistant == nums[i])
times++;
else
{
// 情况2：净票数为0 → 候选元素被抵消完，更换为当前元素，重置票数为1
if(times == 0)
consistant = nums[i];
// 情况3：净票数≠0 → 不同阵营，净票数-1（互相抵消）
else
times—;
}
}
// 3. 遍历结束，候选元素就是多数元素
return consistant;
}
};

// 简洁版本 武林大会(摩尔投票)
class Solution {
public:
int majorityElement(vector<int>& nums)
{
int resultnums = nums[0];
int count = 0;

for(int i = 0 ; i < nums.size() ; i++)
{
if(resultnums == nums[i])
{
count++;
}
else
{
if(count == 0) //换人
{
resultnums = nums[i];
}
else
{
count—;
}
}
}
return resultnums;
}
};

十八、139. 单词拆分

代码如下（示例）：

class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
// 优化⼀：将字典⾥⾯的单词存在哈希表⾥⾯
unordered_set<string> hash;
for (auto& s : wordDict)
hash.insert(s);
int n = s.size();
vector<bool> dp(n + 1);
dp[0] = true; // 保证后续填表是正确的
s = ' ' + s; // 使原始字符串的下标统⼀ +1
for (int i = 1; i <= n; i++) // 填 dp[i]
{
for (int j = i; j >= 1; j—) // 最后⼀个单词的起始位置
{
if (dp[j – 1] && hash.count(s.substr(j, i – j + 1))) {
dp[i] = true;
break; // 优化⼆
}
}
}
return dp[n];
}
};

class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict)
{
int n = s.size();
vector<bool> dp(n + 1);
dp[0] = true; // 初始化1
s = ' ' + s; // 初始化2

unordered_set<string> hash;
for(auto x : wordDict)
{
hash.insert(x);
}

for(int i = 1 ; i <= n ; i++)
{
for(int j = i ; j >= 1 ; j—)
{
if(dp[j – 1] && hash.count(s.substr(j , i – j + 1)))
{
dp[i] = true;
break;
}
}
}
return dp[n];
}
};

十九、283. 移动零

代码如下（示例）：

class Solution {
public:
void moveZeroes(vector<int>& nums)
{
// [0 , dest] [dest + 1 , cur – 1] [cur , n – 1]
// 非0区域 0区域 待处理
int cur = 0 , dest = –1 , n = nums.size();
while(cur < n)
{
if(nums[cur] != 0)
{
swap(nums[dest + 1] , nums[cur]);
cur++;
dest++;
}
else
{
cur++;
}
}
}
};

二十、718. 最长重复子数组

代码如下（示例）：

class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2)
{
// 动态规划
int m = nums1.size() , n = nums2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));

int ret = 0;
for(int i = 1 ; i <= m ; i++)
{
for(int j = 1 ; j <= n ; j++)
{
if(nums1[i – 1] == nums2[j – 1])
{
dp[i][j] = dp[i – 1][j – 1] + 1;
ret = max(ret , dp[i][j]);
}
}
}
return ret;
}
};

总结

这篇文章是作者搜集大量面经和资料这里出来的。感谢你的支持 作者wkm是一名中国矿业大学(北京) 大一的新生，希望得到你的关注 如果可以的话，记得一键三联！