系列綜述：
💞目的：本系列是個人整理為了秋招面試的，整理期間苛求每個知識點，平衡理解簡易度與深入程度。
🥰來源：材料主要源于LeetCodeHot100進行的，每個知識點的修正和深入主要參考各平臺大佬的文章，其中也可能含有少量的個人實驗自證。
🤭結(jié)語：如果有幫到你的地方，就點個贊和關(guān)注一下唄，謝謝🎈🎄🌷！！！
🌈【C++】秋招&實習面經(jīng)匯總篇

---

---

😊點此到文末驚喜??

基本算法

1. 雙指針：適合線性表
2. 哈希法：適合去重和查找
3. while中記錄并自增，然后進行結(jié)點處理（滑動窗口模板中類似）
4. 鏈表基本模板

#include <iostream>
using namespace std;// 結(jié)點模板
template<typename T>
struct Node {T data;Node *next;Node() : next(nullptr) {}Node(const T &d) : data(d), next(nullptr) {}
};// 刪除 p 結(jié)點后面的元素
template<typename T>
void Remove(Node<T> *p) {// 確定兩邊安全性，然后刪除中間if (p == nullptr || p->next == nullptr) return;auto tmp = p->next->next;delete p->next;p->next = tmp;
}//在 p 結(jié)點后面插入元素
template<typename T>
void Insert(Node<T> *p, const T &data) {auto tmp = new Node<T>(data);tmp->next = p->next;p->next = tmp;
}//遍歷鏈表
template<typename T, typename V>
void Traverse(Node<T> *p, const V &vistor) {while(p != nullptr) {vistor(p);	// 函數(shù)指針，靈活處理p = p->next;}
}int main() {// 建立 鏈表結(jié)點auto p = new Node<int>(1);// 插入 鏈表結(jié)點Insert(p, 2);// 遍歷 鏈表求和int sum = 0;Traverse(p, [&sum](const Node<int> *p) -> void { sum += p->data; });// 刪除 鏈表Remove(p);return 0;
}

---

鏈表篇

160. 相交鏈表

1. 問題
   • 給你兩個單鏈表的頭節(jié)點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點。
   • 如果兩個鏈表不存在相交節(jié)點，返回 nullptr
2. 思路
   • 相差同移法：先求出長度差值，然后長的移動差值次，再同時移動
   • 哈希法：先將一個存入哈希表，另一個開始遍歷哈希表，第一個找到另一個即為第一個。
   • 交換遍歷法：pa走到頭后，從headB開始走。pb走到頭后，從headA開始走。這樣交替走路，兩個到相同結(jié)點的長度是一樣的
   

// 交換遍歷
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *pa = headA;ListNode *pb = headB;while (pa != pb) {(pa == nullptr) ? pa = headB : pa = pa->next;(pb == nullptr) ? pb = headA : pb = pb->next;}return pa;
}

3. 總結(jié)
   • 注意if-else的條件分支是否分離判斷
   • 查找和去重就思考哈希

234. 回文鏈表

1. 問題
   • 給你一個單鏈表的頭節(jié)點 head ，請你判斷該鏈表是否為回文鏈表。如果是，返回 true ；否則，返回 false 。最大值 。
   • 鏈表題目通常不能使用數(shù)組進行處理
2. 思路
   • 鏈表常用模板組合

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {if(head == null || head.next == null) return true;// 找中點 1=>1 123=>2 1234=>2ListNode A_end = mid(head);ListNode B_start = A_end.next;A_end.next = null;// 翻轉(zhuǎn)后半部分B_start = reverse(B_start);// 比對boolean res = compare(head, B_start);// 還原A_end.next = reverse(B_start);return res;}// 鏈表找中點，快慢指針法ListNode mid(ListNode head) {ListNode p = head;ListNode q = head;while(q.next != null && q.next.next != null) {p = p.next;q = q.next.next;}return p;}// 鏈表反轉(zhuǎn)模板ListNode reverse(ListNode head) { // 三人行模板ListNode pre = null;ListNode cur = head;while(cur != null) {ListNode temp = cur.next; // 松手先保存cur.next = pre;pre = cur; // 歸位cur = temp;}return pre;}// 鏈表比對模板(len(B) <= len(A))boolean compare(ListNode A, ListNode B) {while(B != null) {if(A.val != B.val) return false;A = A.next;B = B.next;}return true;}
}

141. 環(huán)形鏈表

1. 問題
   • 給你一個鏈表的頭節(jié)點 head ，判斷鏈表中是否有環(huán)。
2. 思路
   • 每次快指針移動兩步，慢指針移動一步，同時移動直到快慢指針相遇即可。

// 查找：使用hash存儲，然后遍歷環(huán)進行處理
bool hasCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while (true) {if (fast == nullptr || fast->next == nullptr) return false;fast = fast->next->next;slow = slow->next;if (fast == slow) break;}return true;}

3. 判斷環(huán)的長度：快慢指針相遇后繼續(xù)移動，直到第二次相遇。兩次相遇間的移動次數(shù)即為環(huán)的長度
4. 判斷環(huán)的入口：快慢指針相遇后，慢指針不動，另取一指針p指向鏈表頭結(jié)點，然后節(jié)點p和節(jié)點slow同時移動，每次移動一步，二者相遇時指向的節(jié)點即為環(huán)的入口節(jié)點。

142. 環(huán)形鏈表 II

1. 問題
   • 給定一個鏈表的頭節(jié)點 head ，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。
2. 思路
   • 判斷環(huán)的入口：快慢指針相遇后，慢指針不動，另取一指針p指向鏈表頭結(jié)點，然后節(jié)點p和節(jié)點slow同時移動，每次移動一步，二者相遇時指向的節(jié)點即為環(huán)的入口節(jié)點。

ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while (true) {if (fast == nullptr || fast->next == nullptr) return nullptr;fast = fast->next->next;slow = slow->next;if (fast == slow) break;}fast = head;while (slow != fast) {slow = slow->next;fast = fast->next;}return fast;
}

21. 合并兩個有序鏈表

1. 問題
   • 將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
2. 思路
   • 虛擬頭節(jié)點的使用

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode *vhead = new ListNode(-1, nullptr);ListNode *tail = vhead;while (list1 != nullptr && list2 != nullptr) {ListNode *p;if (list1->val < list2->val) {p = list1;list1 = list1->next;}else {p = list2;list2 = list2->next;}// 條件判斷中共同的部分，分離出來tail->next = p;tail = tail->next;} list1 == nullptr ? tail->next = list2 : tail->next = list1;return vhead->next;
}

19. 刪除鏈表的倒數(shù)第 N 個結(jié)點

1. 問題
   • 給你一個鏈表，刪除鏈表的倒數(shù)第 n 個結(jié)點，并且返回鏈表的頭結(jié)點。
2. 思路
   • 虛擬頭節(jié)點的使用
   • 刪除結(jié)點要使用保存其前一個結(jié)點的指針

ListNode* removeNthFromEnd(ListNode* head, int n) {if(n < 0 || head == nullptr)return nullptr;// 快慢指針拉開n個節(jié)點的距離ListNode *vHead = new ListNode(0);vHead->next = head;ListNode *slow = vHead;ListNode *fast = vHead;// 讓slow指向被刪除節(jié)點的前一個while(n--){fast = fast->next;}// 同步移動while(fast->next != nullptr){fast = fast->next;slow = slow->next;}// 刪除節(jié)點slow->next = slow->next->next;return vHead->next;
}

2. 兩數(shù)相加

1. 問題
   • 給你兩個 非空 的鏈表，表示兩個非負的整數(shù)。它們每位數(shù)字都是按照 逆序 的方式存儲的，并且每個節(jié)點只能存儲 一位 數(shù)字。
   • 請你將兩個數(shù)相加，并以相同形式返回一個表示和的鏈表。
     
2. 思路
   • 通過進位carry和補充虛擬結(jié)點，從而實現(xiàn)算法的統(tǒng)一處理

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {/* 定義一個新的鏈表用于存儲求和的結(jié)果 */ListNode* dummyHead = new ListNode(0);ListNode* cur = dummyHead;/* 定義一個變量用于保存進位 */int carry = 0;/* 因為不知道l1和l2的長短所以只要有一個沒有遍歷完就繼續(xù)遍歷 遍歷完的就不執(zhí)行 *//* * 第一次寫while(l1 || l2)會錯因為漏掉了最后一個進位《== 特別喲注意*/while(l1 || l2 || carry){/* 只要不為空就繼續(xù)求和 */if(l1 != NULL) carry += l1->val;if(l2 != NULL) carry += l2->val;/* 創(chuàng)建一個節(jié)點插入到新的鏈表并且值初始化為l1->val+l2->val的個位數(shù) */ListNode* tmp = new ListNode(carry%10);/* 插入結(jié)點tmp因為是從頭開始插入所以只需要每次更新cur */cur->next = tmp;cur = cur->next;/* 只要鏈表不為空就繼續(xù)遍歷下一個節(jié)點 */if(l1 != NULL) l1 = l1->next;if(l2 != NULL) l2 = l2->next;/* 獲取上個節(jié)點的進位值 加到下個節(jié)點的運算中 */carry /= 10;}/* 注意這里不返回dummyHead因為這里相當于一個虛擬頭節(jié)點 下一個才是正真的頭節(jié)點 */return dummyHead->next;}
};

3. 總結(jié)
   • 補充虛擬的，從而將算法進行統(tǒng)一化處理

24. 兩兩交換鏈表中的節(jié)點

1. 問題
   • 給你一個鏈表，兩兩交換其中相鄰的節(jié)點，并返回交換后鏈表的頭節(jié)點。你必須在不修改節(jié)點內(nèi)部的值的情況下完成本題（即，只能進行節(jié)點交換）
2. 思路
   • 每次確定兩個結(jié)點的前一個結(jié)點，并進行交互處理

ListNode* swapPairs(ListNode* head){// 帶安全檢查的交換結(jié)點auto swap_list = [](ListNode *prev){if (prev != nullptr && prev->next != nullptr && prev->next->next != nullptr) {ListNode *front = prev->next;ListNode *back = front->next;front->next = back->next;back->next = front;prev->next = back;}};if(head == nullptr)return nullptr;// 單鏈表插/刪，虛擬三件套ListNode* vHead = new ListNode(-1);vHead->next = head;					ListNode *cur = vHead;while(cur->next != nullptr && cur->next->next != nullptr){swap_list(cur);cur = cur->next->next;}return vHead->next;
}

3. 總結(jié)
   • 使用auto匿名函數(shù)封裝鏈表基本操作

25. K 個一組翻轉(zhuǎn)鏈表

1. 問題
   • 給你鏈表的頭節(jié)點 head ，每 k 個節(jié)點一組進行翻轉(zhuǎn)，請你返回修改后的鏈表。
2. 算法
   • 棧：可以用來處理逆序問題

ListNode* reverseKGroup(ListNode* head, int k) {stack<ListNode*> stk;ListNode* res=new ListNode;ListNode* p=res,*q;int i;while(head){for(i=0;head&&i<k;i++){//k個一組進棧stk.push(head);head=head->next;}if(i!=k)break;//不成一組跳出while(!stk.empty()){//逆序出棧p->next=stk.top();p=stk.top();stk.pop();}q=head;}p->next=q;//接上余下的點return res->next;
}

148. 排序鏈表

1. 問題
   • 給你鏈表的頭結(jié)點 head ，請將其按 升序 排列并返回 排序后的鏈表
2. 思路
   • 歸并

ListNode* sortList(ListNode* head) {ListNode dummyHead(0);dummyHead.next = head;auto p = head;int length = 0;while (p) {++length;p = p->next;}for (int size = 1; size < length; size <<= 1) {auto cur = dummyHead.next;auto tail = &dummyHead;while (cur) {auto left = cur;auto right = cut(left, size); // left->@->@ right->@->@->@...cur = cut(right, size); // left->@->@ right->@->@  cur->@->...tail->next = merge(left, right);while (tail->next) {tail = tail->next;}}}return dummyHead.next;
}
// 分離鏈表
ListNode* cut(ListNode* head, int n) {// p指向鏈表的第n個auto p = head;while (--n && p) {p = p->next;}if (p == nullptr) return nullptr;// 返回鏈表后的結(jié)點，并將該段鏈表分離auto next = p->next;p->next = nullptr;return next;
}
// 合并兩個有序鏈表
ListNode* merge(ListNode* l1, ListNode* l2) {ListNode dummyHead(0);auto p = &dummyHead;while (l1 && l2) {if (l1->val < l2->val) {p->next = l1;p = l1;l1 = l1->next;       } else {p->next = l2;p = l2;l2 = l2->next;}}p->next = (l1 ? l1 : l2);return dummyHead.next;
}

146. LRU 緩存

---

樹篇

基本概述

1. 二叉樹數(shù)據(jù)結(jié)構(gòu)

   struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   };
   

二叉樹深度優(yōu)先遍歷

1. 遞歸式

   // 前序遍歷
   void Traversal(TreeNode *root) {if (root == nullptr) return ;Doing(root->val);       // 中Traversal(root->left);  // 左Traversal(root->right); // 右
   }
   // 中序遍歷
   void Traversal(TreeNode *root) {if (root == nullptr) return ;Traversal(root->left);  // 左Doing(root->val);       // 中Traversal(root->right); // 右
   }
   // 后序遍歷
   void Traversal(TreeNode *root, vector<int> vec) {if (root == nullptr) return ;Traversal(root->left);  // 左Traversal(root->right); // 右vec.emplace_back(root->val);// 中
   }
   

2. 非遞歸：將前序、中序和后序統(tǒng)一化處理，將遍歷核心順序進行逆序轉(zhuǎn)化
   • 算法遍歷部分的逆序
   • 對于值節(jié)點的處理

   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.push_back(node->val);}}return result;
   }
   

二叉樹廣度優(yōu)先遍歷

1. 遞歸法

   // 遞歸參數(shù)，如果需要修改要進行引用傳遞
   void traversal(TreeNode* cur, vector<vector<int>>& result, int depth) {// 遞歸出口if (cur == nullptr) return;// 遞歸體if (result.size() == depth) // 擴容result.push_back(vector<int>());// 原地構(gòu)建數(shù)組result[depth].push_back(cur->val);// 順序壓入對應(yīng)深度的數(shù)組中order(cur->left, result, depth + 1);order(cur->right, result, depth + 1);
   }
   vector<vector<int>> levelOrder(TreeNode* root) {// 初始化：一般為遞歸形參vector<vector<int>> result;int depth = 0;// 遞歸調(diào)用traversal(root, result, depth);// 返回結(jié)果return result;
   }
   

2. 非遞歸法

vector<vector<int>> levelOrder(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);if (node->right) que.push(node->right);// doing：處理結(jié)點vec.push_back(node->val);}// 將每層篩選元素壓入結(jié)果數(shù)組中result.push_back(vec);}// 輸出return result;
}

226. 翻轉(zhuǎn)二叉樹

1. 給你一棵二叉樹的根節(jié)點 root ，翻轉(zhuǎn)這棵二叉樹，并返回其根節(jié)點。
2. 思路
   • 前序遍歷

void traversal(TreeNode *cur){// 結(jié)束條件if(cur == nullptr)return ;swap(cur->left, cur->right);if(cur->left)  traversal(cur->left);if(cur->right)  traversal(cur->right);
}

101. 對稱二叉樹

1. 給你一個二叉樹的根節(jié)點 root ， 檢查它是否軸對稱。
2. 思路
   • 單層條件嘗試

bool ismirror(TreeNode* t1,TreeNode* t2){if(t1==NULL&&t2==NULL)//都為空return true;if(t1==NULL||t2==NULL)//有一個為空return false;return (t1->val==t2->val)&&ismirror(t1->left,t2->right)&&ismirror(t1->right,t2->left);
}

543. 二叉樹的直徑

1. 問題
   • 給你一棵二叉樹的根節(jié)點，返回該樹的 直徑 。
   • 二叉樹的 直徑 是指樹中任意兩個節(jié)點之間最長路徑的 長度 。這條路徑可能經(jīng)過也可能不經(jīng)過根節(jié)點 root 。
2. 思路
   • 最長一定是以某個結(jié)點為根節(jié)點的子樹的左右子樹高度之和

int diameterOfBinaryTree(TreeNode* root)
{int distance = 0;dfs(root, distance);return distance;
}// distance等價于全局變量
int dfs(TreeNode *root, int &distance){if (root == nullptr)return 0;int left = dfs(root->left, distance);	// 左邊深度int right = dfs(root->right, distance);	// 右邊深度distance = max(left + right, distance);	// // 獲取當前樹的左子樹和右子樹深度的較大值，加 1 （本層深度）return max(left, right) + 1;	// 最大深度
}

108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

1. 問題
   • 給你一個整數(shù)數(shù)組 nums ，其中元素已經(jīng)按 升序 排列，請你將其轉(zhuǎn)換為一棵 高度平衡 二叉搜索樹。
   • 高度平衡 二叉樹是一棵滿足「每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。
2. 思路
   • 建根和劃分

TreeNode* Translate(vector<int>& nums, int left, int right) {if (left > right) return nullptr;// 建根int mid = left + ((right - left) / 2);TreeNode *root = new TreeNode(nums[mid]);// 劃分root->left = Translate(nums, left, mid-1);root->right = Translate(nums, mid+1, right);// 返回return root;
}

108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

1. 問題
   • 給你一個整數(shù)數(shù)組 nums ，其中元素已經(jīng)按 升序 排列，請你將其轉(zhuǎn)換為一棵 高度平衡 二叉搜索樹。
   • 高度平衡 二叉樹是一棵滿足「每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。
2. 思路
   • 建根和劃分

TreeNode* Translate(vector<int>& nums, int left, int right) {if (left > right) return nullptr;// 建根int mid = left + ((right - left) / 2);TreeNode *root = new TreeNode(nums[mid]);// 劃分root->left = Translate(nums, left, mid-1);root->right = Translate(nums, mid+1, right);// 返回return root;
}

98. 驗證二叉搜索樹

1. 問題
   • 給你一個二叉樹的根節(jié)點 root ，判斷其是否是一個有效的二叉搜索樹。對值不超過 1 的二叉樹。
2. 思路
   • 二叉樹的中序遍歷是遞增順序的
   • 判斷左小右大

// 中序遞增
long pre = MIN_                                                                                                                                                                                                                       ;
public boolean isValidBST(TreeNode root) {if (root == null) {return true;}// 訪問左子樹if (!isValidBST(root.left)) {return false;}// 訪問當前節(jié)點：如果當前節(jié)點小于等于中序遍歷的前一個節(jié)點，說明不滿足BST，返回 false；否則繼續(xù)遍歷。if (root.val <= pre) {	// 嚴格遞增return false;}pre = root.val;// 訪問右子樹return isValidBST(root.right);
}

樹相關(guān)題目

---

少年，我觀你骨骼清奇，穎悟絕倫，必成人中龍鳳。 不如點贊·收藏·關(guān)注一波

---

🚩點此跳轉(zhuǎn)到首行??

參考博客

1. 前綴和問題
2. 單調(diào)隊列
3. 快速鏈表quicklist
4. 《深入理解計算機系統(tǒng)》
5. 侯捷C++全系列視頻
6. 待定引用
7. 待定引用
8. 待定引用