【算法总结篇】 笔面试常见题目

综述：
💞目的：本系列是个人整理为了秋招算法的，整理期间苛求每个知识点，平衡理解简易度与深入程度。
🥰来源：材料主要源于网上知识点进行的，每个代码参考热门大佬博客和leetcode平台，其中也可能含有一些的个人思考。
🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！
🌈【C++】秋招&实习面经汇总篇

---

---

😊点此到文末惊喜↩︎

---

编码平台格式

ACM模式

输入部分

1. 注意事项
   • 开头加上using i64 = long long：标准规定int 至少 16 位，所以在不同的编译器下，int可能位数不足出现整形溢出问题，可以使用直接使用long long代替整数值。
   • 奇数判断 (n & 1) == 1：因为奇数的二进制尾数为1，二进制速度快。
2. 基础输入要点
   • 引用库需要自己加上对应的库，如#include <algorithm>
   • 输入使用while (cin >> a ){ 算法主体 }
   • 输出使用cout，注意删除自己的测试输出，不能使用return，否则会一直报错语法错误
   • 输入示例：

   #include <vector> 
   #include <iostream> 
   using namespqce std;
   int main() {long n = 0;	// 表示n轮输入cin >> n;while (n--) { int c = 0;	// 每轮输入的整数个数cin >> c;vector<long> vec(c, 0);for (int i = 0; i < vec.size(); ++i)cin >> vec[i];
   }
   

3. 二维数组的初始化

   vector<vector<int>> dp(rows, vector<int>(cols, 0));// 注意要进行初始化
   for (int i = 0; i < rows; ++i) {for (int j = 0; j < cols; ++j) {cin >> dp[i][j];// 不能使用push_back()进行处理
   }
   

4. 输入一行以回车结尾的数字

   vector<int> vec;
   int tmp = 0;
   do {// 不能使用while(){}，因为会丢失第一个输入cin >> tmp;vec.push_back(tmp);
   } while (cin.get() != '\n');
   

算法部分

1. 先对输入部分进行健壮性检查：尽量将代码进行划分，然后对每个部分进行健壮性检查。
2. 含有小数的计算要注意使用double
3. 如果要使用匿名函数，要注意
   • 外界值的捕获
   • 结尾要有;
   • 如果有返回值，一定要有return
4. 一定要充分理解题意，构思后再将题中要点进行梳理
5. 线性表的遍历要先进行属性限制，避免溢出

vector<int> vec;
for (int i = 0; i < vec.size(); ++i) {if ((i+1 < vec.size() && vec[i+1] == val) ||(i-1 >= 0 && vec[i-1] == val)) {return true;}

6. 通过必然约束进行求解更好
   • 若A + B = C，则B = C - A
7. 返回值类型为bool的函数，在函数最后的所有返回分支都要有返回值
8. 一定要考虑0值和边界等特殊情况

输出部分

1. 输出要使用endl进行换行cout << val << endl;
2. 价格通常要输出小数后两位数
   • 注意使用double，如果空间不足再使用float

   double val = 2.34535;
   printf("%.2f\n", val);
   

笔试基础

基本代码范式

1. 尝试性求解：先尝试进行一个简单的逻辑推导，然后进行三个小测试进行编写。
2. 基本逻辑范式

   bool function(){// 1.健壮性检查if (函数形参不符合情况) {doing();return false;}// 2.初始化(构建初始状态)：给工作变量赋初值，符合要求的第一次循环条件int initial_value = 0;// 会被算法初始化的也应该赋初值// 4.算法逻辑（状态转化规则）while (工作变量符合算法循环条件) {// 注意考虑最后不足算法增量的部分doing();// 对结果序列操作的函数工作变量的迭代;// 注意工作变量在使用完成后已经被污染}// 5.收尾处理不足最后一次算法增量的部分return true;
   }
   

3. 递归逻辑范式

   void Recursion(vector<int> &vec,...){// 递归出口if (结束条件) return ;// 递归体Doing();
   }
   

基本算法框架

1. 快慢指针
   • 作用：可用于线性结构的条件遍历处理，如链表、数组等
   • 优点：可以将两次循环降维成条件筛选+一次循环

   // 示例：删除数组中的元素
   int RemoveElement(vector<int>& nums, int val) {// 健壮性检查if (nums.empty()) return -1;// 初始化操作int slow = 0;		// 慢指针负责更新处理int fast = slow;	// 快指针负责拓展选择// 算法部分while(fast < nums.size()){	if(nums[fast] != val){	// 快指针负责条件判断nums[slow] = nums[fast];++slow;++fast;}++fast;}return slow;
   }
   // 示例：环形链表的入口
   

2. 滑动窗口
   • 右边界指针负责拓展，左边界指针负责收缩

   // 使用O(n)时找到满足条件的区间长度最值(示例：和的最小区间长度)
   auto sliding_windows = [](vector<int> &vec, int target)->int{int res = INT_MAX;int sum = 0;int fast = 0;int slow = 0;while (fast < vec.size()) {// 拓展窗口：记录值和窗口大小sum += vec[fast];++fast;// 收缩临界条件while (sum  >= target) {res = min(res, fast - slow);// key：记录值// 收缩窗口sum -= vec[slow];++slow;}}return res == INT_MAX? 0:res;
   };
   

3. 二叉树遍历算法
   • 广度优先遍历
   • 深度优先遍历

   // 二叉树的基本数据结构
   struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int v) : val(v), left(nullptr), right(nullptr){}
   };
   // 深度优先的递归遍历
   // 中序遍历
   void Traversal(TreeNode *root) {if (root == nullptr) return ;Traversal(root->left);  // 左Doing(root->val);       // 中Traversal(root->right); // 右
   }
   // 深度优先的非递归遍历
   vector<int> Traversal(TreeNode* root) {// 初始化vector<int> result;		// 结果容器stack<TreeNode*> st;	// 深度的栈if (root != NULL) 		// 根非空则入栈st.push(root);// 遍历源容器while (!st.empty()) {TreeNode* node = st.top();	//   if (node != NULL) {st.pop();// 算法变化的部分，遍历的逆序// 中st.push(node);                          st.push(NULL);// 右if (node->right) st.push(node->right); // 左if (node->left) st.push(node->left);    } else {// 对值节点的处理st.pop();// 弹出空值结点node = st.top();st.pop();// 结点处理result.emplace_back(node->val);}}return result;
   }
   // 广度优先的非递归遍历
   vector<vector<int>> Traversal(TreeNode* root) {// 初始化vector<vector<int>> result;	// 结果容器queue<TreeNode*> que;		// 广度的队列if(root != nullptr)			// 根非空则入列 que.push(root);// 算法while (!que.empty()) {		// 队列非空vector<int> vec;		// 结果存放TreeNode* node; 		// 过程记录int size = que.size();	// 初始化：记录每层要遍历的根节点数量for (int i = 0; i < size; i++) {	// que.size()会变化// 处理结点node = que.front();	// 记录队首结点que.pop();			// 弹出队首结点if (node->left) que.push(node->left);	// 不需要node->left != nullptrif (node->right) que.push(node->right);// doing：处理结点vec.emplace_back(node->val);}// 将每层筛选元素压入结果数组中result.emplace_back(vec);}// 输出return result;
   }
   

4. 回溯算法
   • 组合问题
     • 有重复元素的组合
     • 无重复元素的组合
   • 排列问题
     • 有重复元素的全排列
     • 无重复元素的全排列

// 组合问题
// 无重复元素的组合
class Solution {
public:vector<vector<int>> combine(vector<int>vec, int k) {result.clear(); // 可以不写path.clear();   // 可以不写BackTracking(vec, 0,  k);return result;}
private:// 回溯核心算法vector<vector<int>> result; // 存放符合条件结果的集合vector<int> path; // 用来存放符合条件结果void Backtracking(vector<int> &vec, int start, int target) {// 递归出口：满足条件则加入结果集中if (path.size() == target) {result.push_back(path);	return ;}// 回溯算法for (int i = start; i < vec.size(); ++i) {// 剪枝条件if (i > vec.size() - (target-path.size()))    continue;path.push_back(vec[i]); 	// 做出选择Backtracking(vec, i + 1, target);// 递归path.pop_back(); 			// 撤销选择}}
};// 有重复元素的组合
class Solution {
public:vector<vector<int>> combine(vector<int> vec, int k) {result.clear(); // 可以不写path.clear();   // 可以不写sort(vec.begin(), vec.end());BackTracking(vec, 0,  k);return result;}
};
private:// 回溯核心算法vector<vector<int>> result; // 存放符合条件结果的集合vector<int> path; // 用来存放符合条件结果void BackTracking(vector<int> &vec, int start, int target) {// 递归出口：满足条件则加入结果集中if (path.size() == target) {result.push_back(path);	return ;}// 回溯算法for (int i = start; i < vec.size(); i++) {// 剪枝：重复选择只选一次，需要配合sort使用if (i > start && vec[i] == vec[i - 1]) continue;// 回溯步骤path.push_back(vec[i]); 	// 做出选择BackTracking(vec, i + 1, target);// 递归path.pop_back(); 			// 撤销选择}}
};// 无重复元素的全排列
class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
private:vector<vector<int>> result;vector<int> path;void backtracking (vector<int>& nums, vector<bool>& used) {// 此时说明找到了一组if (path.size() == nums.size()) {result.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {if (used[i] == true) continue; // path里已经收录的元素，直接跳过// 增加选择used[i] = true;path.push_back(nums[i]);// 回溯backtracking(nums, used);// 撤销选择path.pop_back();used[i] = false;}}
};// 有重复元素的全排列
class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {// 重复计数unordered_map<int, int> umap;for (auto i : nums) ++umap[i];backtrace(umap, 0, nums.size());return res;}
private:vector<vector<int> > res;vector<int> path;void backtrace(unordered_map<int, int> &umap, int k, int total) {if (k == total) {res.push_back(path);return;}for (auto& p : umap) {	// 每轮递归结束会进入循环if (p.second == 0) continue;--p.second;path.push_back(p.first);backtrace(umap, k + 1, n);++p.second;path.pop_back();}}
};

5. 动态规划算法

   // dp的推导
   // - dp[j]为容量为j的背包所背的最大价值
   // - 每次物品有两个选择
   // 	- 放入则背包减去重量并增加价值 dp[j - weight[i]] + value[i]
   // 	- 不放入则仍为 dp[j]
   // 最终递推公式为dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
   int main() {// 子功能部分auto bag_problem = [](vector<int> &weight, vector<int> &value, int bag_weight)->int{vector<int> dp(bag_weight + 1, 0);for (int i = 0; i < weight.size(); ++i)	{// 倒叙保证物品只添加一次，顺序会导致所用数据是刚更新的// 而不是上一层滚动的for (int j = bag_weight; j >= weight[i]; --j) {dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);}}return dp[bag_weight];};// 逻辑部分vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bag_weight = 4;cout << bag_problem(weight, value, bag_weight);
   }
   

$<algorithm>常用函数模板$

1. 前提：需要包含#include<algorithm>头文件
2. 常见功能函数使用示例

   #include <iostream>
   #include <algorithm>
   #include <vector>
   using namespace std;
   int main() {vector<int> vec{1, 2, 3, 4, 5};// max和min函数int min_val = min(a, b); // 返回a和b中较小的值int max_val = max(a, b); // 返回a和b中较大的值// sort函数：对容器进行自定义的排序sort(vec.begin(), vec.end());   // 默认为升序排序sort(vec.begin(), vec.end(), [](int a, int b){return a < b; // 可以进行自定义}); // 降序排序// find函数：返回容器中指定值的迭代器，如果没有则返回end()auto it = find(vec.begin(), vec.end(), 3);if (it != vec.end()) cout << "找到了";// remove函数：删除范围内的指定值remove(vec.begisn(), vec.end(), 3);// replace函数：将容器中的所有a值替换成b值replace(v.begin(), v.end(), 3, 10); // 将所有3替换成10// reverse函数：反转vector中的元素reverse(vec.begin(), vec.end());// count函数：计算在一个范围内某个值的出现次数int n = count(vec.begin(), vec.end(), 3);// 注意若为字符使用'3'// swap函数：交换两个变量的值swap(a, b);// 使用lower_bound函数查找第一个大于等于3的元素位置auto it = lower_bound(vec.begin(), vec.end(), 3);cout << it - vec.begin() << endl;
   }
   

面试基础

面试常见手撕题目

1. 快速排序

   void QuickSort(vector<int> &vec, int left, int right) {// 功能性函数：划分auto partition = [](vector<int> &vec, int left, int right)->int{ int pivot = vec[left];	// 定义第一个为枢纽while (left < right) {// 从右向前找比枢纽值小的放在左边while (left < right && vec[right] >= pivot) --right;vec[left] = vec[right];// 从左向后找比枢纽值大的放在右边while (left < right && vec[left] <= pivot ) ++left;vec[right] = vec[left];}// 填入枢纽值vec[left] = pivot;return left;};// 递归出口（需要使用大于等于）if (left >= right) return ;// [left, right]中left=right，表示区间有序// 递归体int pivot_index = partition(vec, left, right);QuickSort(vec, left, pivot_index-1);QuickSort(vec, pivot_index+1, right);
   }
   

2. 合并两个有序链表
   • 合并k个有序链表：使用合并两个有序链表作为基础进行归并算法

   ListNode* MergeList(ListNode* list1, ListNode* list2) {// 健壮性检查if (list1 == nullptr || list2 == nullptr) return (list1 != nullptr) ? list1 : list2;// 初始化TreeNode *vhead = ListNode(-1);TreeNode *cur = vhead;// 算法while (list1 != nullptr && list2 != nullptr) {if (list1.val < list2.val) {cur.next = list1;list1 = list1.next;} else {cur.next = list2;list2 = list2.next;}cur = cur.next;}// 收尾cur.next = (list1 != nullptr) ? list1 : list2;return vhead;
   }
   

3. 求第k大数（含有重复数）

   #include <algorithm>
   #include <vector>
   #include <algorithm>
   using namespqce std;int KthLargeElement(vector<int> &vec, int k) {// 健壮性检查if (k <= 0 || k > vec.size())return INT_MIN;// 初始化sort(vec.begin(), vec.end(), [](int a, int b){return a > b;});int count = 1;// 算法部分for (int i = 1; i < vec.size(); ++i) {// key：相邻遍历的方式if (vec[i] != vec[i-1]) ++count;if (count == k) break;}// 收尾return vec[i];
   }
   

基本操作

1. 去重

   #include <iostream>
   #include <vector>
   #include <unordered_set>
   using namespace std;
   int main() {// 基本去重vector<int> vec = { 1, 2, 3, 1, 3 };// 使用set去重的天然特性，然后再赋值给原容器unordered_set<int> uset(vec.begin(), vec.end());vec = vector<int>(uset.begin(), uset.end());// key
   }
   

2. 遍历相邻元素

   int sum = 0;
   for (int i = 1; i < vec.size(); ++i) {sum += vec[i] - vec[i-1];
   }
   

3. 不重用标记
   • 使用对应的bool数组进行标记

   vector<int> vec = {1, 2, 3, 4, 5};
   vector<bool> used(vec.size(), false);
   

4. 字符串处理

   // 1. 字符转换成字符串 / 字符串追加字符
   char c = 'c';
   string s = "";
   // - 调用append函数
   s.append(1, c);
   // - 使用 += 
   s += c;// 2. 将`int/float/double`转换成字符串
   int i = 110;
   string s = "";
   s += to_string(i);// 3. 将字符串转换成int
   string str = "123";
   int num = stoi(str);// 4. 字符串截取
   string str = "Hello, World!";
   string sub_str = str.substr(7, 5);	// 从第7个开始截取后面5个字符(从0开始计数)
   

5. 进制转换

   // 注意需要包含的头文件
   #include <iostream>
   using namespace std;
   // itoa()：将 10进制数 转换为 2-36进制字符串
   int num = 100;
   char str[25];
   itoa(num, str, 2);// 转换成2~36进制的字符串// strtol()：将 2-36进制字符串 转化为 long型的10进制数
   char str[] = "12345";
   char *endptr; // 如果*endptr=='\n'，表示转换失败
   long  num;
   num = strtol(str, &endptr, 2);// 进制的输入
   cin >> oct>> num;
   cin >> num;
   cin >> hex >> num;
   // 进制的输出
   cout << oct <<num<<endl;	// 八进制
   cout << num <<endl;			// 十进制	
   cout << hex <<num<< endl; 	// 十六进制
   // 二进制
   char s[10]; 		//自定义二进制数的位数，输出位数是实际所需位数
   itoa(num,s,2);		//转成字符串，进制为2
   cout << s <<endl;	// 二进制
   

6. 删除链表next结点

   auto delete_node = [](TreeNode *cur){if (cur != nullptr) {ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;	// key：避免内存泄漏}
   };
   

7. 字符串切割

   // 将以'/'为分界的字符串放入vector<string>中
   // 问题：首字符是指定字符会裁剪出空字符串
   auto sub_str = []( string &s, vector<string> &res){s.push_back('/');	// 统一化处理int fast = 0;int slow = 0;while (fast <= s.size()) {if (s[fast] == '/'){string tmp(s.begin()+slow, s.begin()+fast);	// 不用substrres.emplace_back(tmp);slow = fast;slow++;}++fast;}s.pop_back();		// 还原字符串
   };
   

8. 取整操作

   #include <math.h>
   // float、double、long double类型。
   int num = floor(浮点数);// 向下取整
   int num = ceil(浮点数);	// 向上取整
   int num = round(浮点数);// 四舍五入
   

项目基础

设计模式

1. 消息队列（生产者消费者模式）

   #include <iostream> 
   #include <condition_variable>
   #include <mutex>
   #include <queue>
   #include <string>
   #include <thread>
   using namespace std;class MessageQueue {public:MessageQueue() {}// 生产者放入消息队列中void PushMsq(string msg) {unique_lock<mutex> lock(mtx_);// 1.上锁：保证{}范围内的互斥访问que_.push(msg);	// 2.生产：向消息队列中添加消息 cv_.notify_one();// 3.唤醒：唤醒在该条件变量上等待队列优先级最高的一个线程// m_cv.notify_all()会唤醒所有线程，但是会造成资源争用，要谨慎使用}// 消费者从消息队列中取出信息string PopMsq() {unique_lock<mutex> lock(mtx_);// 1. 上锁// 2. 队列为空则等待：如果队列为空，等待生产者添加消息while (que_.empty()) {cv_.wait(lock);// 释放lock锁并阻塞等待}// 3. 消费：取出消息并返回string msg = que_.front();que_.pop();return msg;}private:// 记住这个顺序：先加智能锁，然后压入队列，最后唤醒条件变量上的线程mutex mtx_;				// 互斥锁：保证消息队列和条件变量的互斥访问queue<string> que_;		// 消息队列：生产者和消费者的缓冲区condition_variable cv_;	// 条件变量：保证生产者和消费者的同步
   };
   // 定义生产者线程函数
   void producer(MessageQueue& mq) {for (int i = 0; i < 10; ++i) {string msg = "message " + to_string(i);mq.PushMsq(msg);this_thread::sleep_for(chrono::milliseconds(100)); // 生产者线程休眠一段时间}
   }
   // 定义消费者线程函数
   void consumer(int id, MessageQueue& mq) {for (int i = 0; i < 5; ++i) {string msg = mq.PopMsq();cout << "consumer " << id << " get message: " << msg << std::endl;this_thread::sleep_for(chrono::milliseconds(200)); // 消费者线程休眠一段时间}
   }
   // 测试生产者消费者模型
   int main() {MessageQueue msq;// 线程的创建：参数为（函数指针，函数形参）thread t1(producer, ref(msq));thread t2(consumer, 1, ref(msq));thread t3(consumer, 2, ref(msq));thread t4(consumer, 3, ref(msq));// .join()执行完当前线程再向下执行t1.join();t2.join();t3.join();t4.join();return 0;
   }
   

2. 线程安全的单例模式

   // 饿汉式
   class SinglePatter {public:static SinglePatter& GetInstance() {static SinglePatter instance;return instance;}private:SinglePatter(){};SinglePatter(SinglePatter &) = delete;SinglePatter& operator=(const SinglePatter &) = delete;
   };// 懒汉式
   class SinglePatter {public: static SinglePatter *GetInstance() {unique_lock<mutex> lock(mtx);if (instance == nullptr) {instance = new SinglePatter();}return instance;}private:static SinglePatter *instance;static mutex mtx;SinglePatter(){};SinglePatter(SinglePatter &) = delete;SinglePatter& operator=(const SinglePatter &) = delete;};

高并发相关

1. 写一个自旋锁

   // 自旋锁
   int xchg(volatile int *addr, int new_val) {int res;asm volatile( // 将lock xchg换位cmpxhg是否就是CAS锁"lock xchg %0, %1":"+m"(*addr),"=a"(res):"1"(new_val):"cc");return res;
   }int locked = 0;
   void lock(){while (xchg(&locked, 1));
   }
   void unlock(){xchg(&locked, 0);
   }
   

场景题目

智力题

1. 数学归纳法（动态规划核心公式的推导）
   • 推导前三个或者五个简单的输入和输出，从而假设递进关系式
   • 再使用两个进行验证
2. 组合排列问题

待解决问题

1. 功能性函数auto封装导致的代码优雅性问题，字节二面上下左右走格子中，使用回溯增加复杂性，但是代码优雅易于理解。

2. 匿名函数只是一个对数据的单纯的逻辑处理，不应该有健壮性检查和返回值，数据的初始化部分应该由实参传输，除内部工作变量外，其他变量应该由外部提供。