綜述：
💞目的：本系列是個人整理為了秋招算法的，整理期間苛求每個知識點，平衡理解簡易度與深入程度。
🥰來源：材料主要源于網(wǎng)上知識點進行的，每個代碼參考熱門大佬博客和leetcode平臺，其中也可能含有一些的個人思考。
🤭結(jié)語：如果有幫到你的地方，就點個贊和關(guān)注一下唄，謝謝🎈🎄🌷！！！
🌈【C++】秋招&實習面經(jīng)匯總篇

---

---

😊點此到文末驚喜??

---

編碼平臺格式

ACM模式

輸入部分

1. 注意事項
   • 開頭加上using i64 = long long：標準規(guī)定int 至少 16 位，所以在不同的編譯器下，int可能位數(shù)不足出現(xiàn)整形溢出問題，可以使用直接使用long long代替整數(shù)值。
   • 奇數(shù)判斷 (n & 1) == 1：因為奇數(shù)的二進制尾數(shù)為1，二進制速度快。
2. 基礎(chǔ)輸入要點
   • 引用庫需要自己加上對應(yīng)的庫，如#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;	// 每輪輸入的整數(shù)個數(shù)cin >> c;vector<long> vec(c, 0);for (int i = 0; i < vec.size(); ++i)cin >> vec[i];
   }
   

3. 二維數(shù)組的初始化

   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. 輸入一行以回車結(jié)尾的數(shù)字

   vector<int> vec;
   int tmp = 0;
   do {// 不能使用while(){}，因為會丟失第一個輸入cin >> tmp;vec.push_back(tmp);
   } while (cin.get() != '\n');
   

算法部分

1. 先對輸入部分進行健壯性檢查：盡量將代碼進行劃分，然后對每個部分進行健壯性檢查。
2. 含有小數(shù)的計算要注意使用double
3. 如果要使用匿名函數(shù)，要注意
   • 外界值的捕獲
   • 結(jié)尾要有;
   • 如果有返回值，一定要有return
4. 一定要充分理解題意，構(gòu)思后再將題中要點進行梳理
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的函數(shù)，在函數(shù)最后的所有返回分支都要有返回值
8. 一定要考慮0值和邊界等特殊情況

輸出部分

1. 輸出要使用endl進行換行cout << val << endl;
2. 價格通常要輸出小數(shù)后兩位數(shù)
   • 注意使用double，如果空間不足再使用float

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

筆試基礎(chǔ)

基本代碼范式

1. 嘗試性求解：先嘗試進行一個簡單的邏輯推導，然后進行三個小測試進行編寫。
2. 基本邏輯范式

   bool function(){// 1.健壯性檢查if (函數(shù)形參不符合情況) {doing();return false;}// 2.初始化(構(gòu)建初始狀態(tài))：給工作變量賦初值，符合要求的第一次循環(huán)條件int initial_value = 0;// 會被算法初始化的也應(yīng)該賦初值// 4.算法邏輯（狀態(tài)轉(zhuǎn)化規(guī)則）while (工作變量符合算法循環(huán)條件) {// 注意考慮最后不足算法增量的部分doing();// 對結(jié)果序列操作的函數(shù)工作變量的迭代;// 注意工作變量在使用完成后已經(jīng)被污染}// 5.收尾處理不足最后一次算法增量的部分return true;
   }
   

3. 遞歸邏輯范式

   void Recursion(vector<int> &vec,...){// 遞歸出口if (結(jié)束條件) return ;// 遞歸體Doing();
   }
   

基本算法框架

1. 快慢指針
   • 作用：可用于線性結(jié)構(gòu)的條件遍歷處理，如鏈表、數(shù)組等
   • 優(yōu)點：可以將兩次循環(huán)降維成條件篩選+一次循環(huán)

   // 示例：刪除數(shù)組中的元素
   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;
   }
   // 示例：環(huán)形鏈表的入口
   

2. 滑動窗口
   • 右邊界指針負責拓展，左邊界指針負責收縮

   // 使用O(n)時找到滿足條件的區(qū)間長度最值(示例：和的最小區(qū)間長度)
   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. 二叉樹遍歷算法
   • 廣度優(yōu)先遍歷
   • 深度優(yōu)先遍歷

   // 二叉樹的基本數(shù)據(jù)結(jié)構(gòu)
   struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int v) : val(v), left(nullptr), right(nullptr){}
   };
   // 深度優(yōu)先的遞歸遍歷
   // 中序遍歷
   void Traversal(TreeNode *root) {if (root == nullptr) return ;Traversal(root->left);  // 左Doing(root->val);       // 中Traversal(root->right); // 右
   }
   // 深度優(yōu)先的非遞歸遍歷
   vector<int> Traversal(TreeNode* root) {// 初始化vector<int> result;		// 結(jié)果容器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 {// 對值節(jié)點的處理st.pop();// 彈出空值結(jié)點node = st.top();st.pop();// 結(jié)點處理result.emplace_back(node->val);}}return result;
   }
   // 廣度優(yōu)先的非遞歸遍歷
   vector<vector<int>> Traversal(TreeNode* root) {// 初始化vector<vector<int>> result;	// 結(jié)果容器queue<TreeNode*> que;		// 廣度的隊列if(root != nullptr)			// 根非空則入列 que.push(root);// 算法while (!que.empty()) {		// 隊列非空vector<int> vec;		// 結(jié)果存放TreeNode* node; 		// 過程記錄int size = que.size();	// 初始化：記錄每層要遍歷的根節(jié)點數(shù)量for (int i = 0; i < size; i++) {	// que.size()會變化// 處理結(jié)點node = que.front();	// 記錄隊首結(jié)點que.pop();			// 彈出隊首結(jié)點if (node->left) que.push(node->left);	// 不需要node->left != nullptrif (node->right) que.push(node->right);// doing：處理結(jié)點vec.emplace_back(node->val);}// 將每層篩選元素壓入結(jié)果數(shù)組中result.emplace_back(vec);}// 輸出return result;
   }
   

4. 回溯算法
   • 組合問題
     • 有重復(fù)元素的組合
     • 無重復(fù)元素的組合
   • 排列問題
     • 有重復(fù)元素的全排列
     • 無重復(fù)元素的全排列

// 組合問題
// 無重復(fù)元素的組合
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; // 存放符合條件結(jié)果的集合vector<int> path; // 用來存放符合條件結(jié)果void Backtracking(vector<int> &vec, int start, int target) {// 遞歸出口：滿足條件則加入結(jié)果集中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(); 			// 撤銷選擇}}
};// 有重復(fù)元素的組合
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; // 存放符合條件結(jié)果的集合vector<int> path; // 用來存放符合條件結(jié)果void BackTracking(vector<int> &vec, int start, int target) {// 遞歸出口：滿足條件則加入結(jié)果集中if (path.size() == target) {result.push_back(path);	return ;}// 回溯算法for (int i = start; i < vec.size(); i++) {// 剪枝：重復(fù)選擇只選一次，需要配合sort使用if (i > start && vec[i] == vec[i - 1]) continue;// 回溯步驟path.push_back(vec[i]); 	// 做出選擇BackTracking(vec, i + 1, target);// 遞歸path.pop_back(); 			// 撤銷選擇}}
};// 無重復(fù)元素的全排列
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里已經(jīng)收錄的元素，直接跳過// 增加選擇used[i] = true;path.push_back(nums[i]);// 回溯backtracking(nums, used);// 撤銷選擇path.pop_back();used[i] = false;}}
};// 有重復(fù)元素的全排列
class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {// 重復(fù)計數(shù)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) {	// 每輪遞歸結(jié)束會進入循環(huán)if (p.second == 0) continue;--p.second;path.push_back(p.first);backtrace(umap, k + 1, n);++p.second;path.pop_back();}}
};

5. 動態(tài)規(guī)劃算法

   // 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)	{// 倒敘保證物品只添加一次，順序會導致所用數(shù)據(jù)是剛更新的// 而不是上一層滾動的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>常用函數(shù)模板$

1. 前提：需要包含#include<algorithm>頭文件
2. 常見功能函數(shù)使用示例

   #include <iostream>
   #include <algorithm>
   #include <vector>
   using namespace std;
   int main() {vector<int> vec{1, 2, 3, 4, 5};// max和min函數(shù)int min_val = min(a, b); // 返回a和b中較小的值int max_val = max(a, b); // 返回a和b中較大的值// sort函數(shù)：對容器進行自定義的排序sort(vec.begin(), vec.end());   // 默認為升序排序sort(vec.begin(), vec.end(), [](int a, int b){return a < b; // 可以進行自定義}); // 降序排序// find函數(shù)：返回容器中指定值的迭代器，如果沒有則返回end()auto it = find(vec.begin(), vec.end(), 3);if (it != vec.end()) cout << "找到了";// remove函數(shù)：刪除范圍內(nèi)的指定值remove(vec.begisn(), vec.end(), 3);// replace函數(shù)：將容器中的所有a值替換成b值replace(v.begin(), v.end(), 3, 10); // 將所有3替換成10// reverse函數(shù)：反轉(zhuǎn)vector中的元素reverse(vec.begin(), vec.end());// count函數(shù)：計算在一個范圍內(nèi)某個值的出現(xiàn)次數(shù)int n = count(vec.begin(), vec.end(), 3);// 注意若為字符使用'3'// swap函數(shù)：交換兩個變量的值swap(a, b);// 使用lower_bound函數(shù)查找第一個大于等于3的元素位置auto it = lower_bound(vec.begin(), vec.end(), 3);cout << it - vec.begin() << endl;
   }
   

面試基礎(chǔ)

面試常見手撕題目

1. 快速排序

   void QuickSort(vector<int> &vec, int left, int right) {// 功能性函數(shù)：劃分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]中l(wèi)eft=right，表示區(qū)間有序// 遞歸體int pivot_index = partition(vec, left, right);QuickSort(vec, left, pivot_index-1);QuickSort(vec, pivot_index+1, right);
   }
   

2. 合并兩個有序鏈表
   • 合并k個有序鏈表：使用合并兩個有序鏈表作為基礎(chǔ)進行歸并算法

   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大數(shù)（含有重復(fù)數(shù)）

   #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. 不重用標記
   • 使用對應(yīng)的bool數(shù)組進行標記

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

4. 字符串處理

   // 1. 字符轉(zhuǎn)換成字符串 / 字符串追加字符
   char c = 'c';
   string s = "";
   // - 調(diào)用append函數(shù)
   s.append(1, c);
   // - 使用 += 
   s += c;// 2. 將`int/float/double`轉(zhuǎn)換成字符串
   int i = 110;
   string s = "";
   s += to_string(i);// 3. 將字符串轉(zhuǎn)換成int
   string str = "123";
   int num = stoi(str);// 4. 字符串截取
   string str = "Hello, World!";
   string sub_str = str.substr(7, 5);	// 從第7個開始截取后面5個字符(從0開始計數(shù))
   

5. 進制轉(zhuǎn)換

   // 注意需要包含的頭文件
   #include <iostream>
   using namespace std;
   // itoa()：將 10進制數(shù) 轉(zhuǎn)換為 2-36進制字符串
   int num = 100;
   char str[25];
   itoa(num, str, 2);// 轉(zhuǎn)換成2~36進制的字符串// strtol()：將 2-36進制字符串 轉(zhuǎn)化為 long型的10進制數(shù)
   char str[] = "12345";
   char *endptr; // 如果*endptr=='\n'，表示轉(zhuǎ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]; 		//自定義二進制數(shù)的位數(shù)，輸出位數(shù)是實際所需位數(shù)
   itoa(num,s,2);		//轉(zhuǎn)成字符串，進制為2
   cout << s <<endl;	// 二進制
   

6. 刪除鏈表next結(jié)點

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

7. 字符串切割

   // 將以'/'為分界的字符串放入vector<string>中
   // 問題：首字符是指定字符會裁剪出空字符串
   auto sub_str = []( string &s, vector<string> &res){s.push_back('/');	// 統(tǒng)一化處理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(浮點數(shù));// 向下取整
   int num = ceil(浮點數(shù));	// 向上取整
   int num = round(浮點數(shù));// 四舍五入
   

項目基礎(chǔ)

設(shè)計模式

1. 消息隊列（生產(chǎn)者消費者模式）

   #include <iostream> 
   #include <condition_variable>
   #include <mutex>
   #include <queue>
   #include <string>
   #include <thread>
   using namespace std;class MessageQueue {public:MessageQueue() {}// 生產(chǎn)者放入消息隊列中void PushMsq(string msg) {unique_lock<mutex> lock(mtx_);// 1.上鎖：保證{}范圍內(nèi)的互斥訪問que_.push(msg);	// 2.生產(chǎn)：向消息隊列中添加消息 cv_.notify_one();// 3.喚醒：喚醒在該條件變量上等待隊列優(yōu)先級最高的一個線程// m_cv.notify_all()會喚醒所有線程，但是會造成資源爭用，要謹慎使用}// 消費者從消息隊列中取出信息string PopMsq() {unique_lock<mutex> lock(mtx_);// 1. 上鎖// 2. 隊列為空則等待：如果隊列為空，等待生產(chǎn)者添加消息while (que_.empty()) {cv_.wait(lock);// 釋放lock鎖并阻塞等待}// 3. 消費：取出消息并返回string msg = que_.front();que_.pop();return msg;}private:// 記住這個順序：先加智能鎖，然后壓入隊列，最后喚醒條件變量上的線程mutex mtx_;				// 互斥鎖：保證消息隊列和條件變量的互斥訪問queue<string> que_;		// 消息隊列：生產(chǎn)者和消費者的緩沖區(qū)condition_variable cv_;	// 條件變量：保證生產(chǎn)者和消費者的同步
   };
   // 定義生產(chǎn)者線程函數(shù)
   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)); // 生產(chǎn)者線程休眠一段時間}
   }
   // 定義消費者線程函數(shù)
   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)); // 消費者線程休眠一段時間}
   }
   // 測試生產(chǎn)者消費者模型
   int main() {MessageQueue msq;// 線程的創(chuàng)建：參數(shù)為（函數(shù)指針，函數(shù)形參）thread t1(producer, ref(msq));thread t2(consumer, 1, ref(msq));thread t3(consumer, 2, ref(msq));thread t4(consumer, 3, ref(msq));// .join()執(zhí)行完當前線程再向下執(zhí)行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;};

高并發(fā)相關(guān)

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. 數(shù)學歸納法（動態(tài)規(guī)劃核心公式的推導）
   • 推導前三個或者五個簡單的輸入和輸出，從而假設(shè)遞進關(guān)系式
   • 再使用兩個進行驗證
2. 組合排列問題

待解決問題

1. 功能性函數(shù)auto封裝導致的代碼優(yōu)雅性問題，字節(jié)二面上下左右走格子中，使用回溯增加復(fù)雜性，但是代碼優(yōu)雅易于理解。

2. 匿名函數(shù)只是一個對數(shù)據(jù)的單純的邏輯處理，不應(yīng)該有健壯性檢查和返回值，數(shù)據(jù)的初始化部分應(yīng)該由實參傳輸，除內(nèi)部工作變量外，其他變量應(yīng)該由外部提供。