1. 項(xiàng)目概述一份為C選手量身定制的算法精進(jìn)地圖如果你是一名正在用C刷LeetCode的開發(fā)者無論是為了面試沖刺還是為了系統(tǒng)性提升算法能力你大概率都經(jīng)歷過這樣的迷茫題庫里兩千多道題從何刷起是跟著官方列表順序還是看哪個(gè)“熱題100”榜單刷完一道題除了“AC”的短暫快感似乎并沒有形成深刻的理解和體系化的記憶。更讓人頭疼的是很多題解雖然提供了答案但背后的解題思想、代碼優(yōu)化技巧、以及如何將這道題的經(jīng)驗(yàn)遷移到其他問題上往往語焉不詳。這份筆記正是為了解決這些問題而生。它不是簡單的題目答案合集而是一份以C為核心實(shí)現(xiàn)語言以構(gòu)建完整算法知識體系為目標(biāo)經(jīng)過精心排序和深度解析的刷題路線圖。其核心價(jià)值在于“順序”和“詳解”。順序決定了你學(xué)習(xí)路徑的效率避免在知識孤島間跳躍詳解則確保你每刷一題都能吃透其背后的思想、寫出一段高效優(yōu)雅的C代碼并建立起與其他題目的聯(lián)系。我會持續(xù)更新這份筆記力求覆蓋核心算法與數(shù)據(jù)結(jié)構(gòu)讓你用最少的時(shí)間獲得最扎實(shí)的成長。2. 刷題順序設(shè)計(jì)的核心邏輯與路線圖盲目刷題是效率最低的學(xué)習(xí)方式。一個(gè)科學(xué)的順序應(yīng)該符合認(rèn)知規(guī)律即由淺入深、由點(diǎn)及面、前后關(guān)聯(lián)。我設(shè)計(jì)的這個(gè)順序主要基于以下幾個(gè)原則2.1 原則一數(shù)據(jù)結(jié)構(gòu)先行算法隨后這是構(gòu)建大廈的基石。你必須先熟悉“磚瓦”數(shù)據(jù)結(jié)構(gòu)的特性才能學(xué)會如何用它們“蓋房子”設(shè)計(jì)算法。因此路線會從最基礎(chǔ)的數(shù)組、字符串、鏈表開始逐步過渡到棧、隊(duì)列、哈希表再到復(fù)雜的樹、圖最后是高級數(shù)據(jù)結(jié)構(gòu)如堆、并查集、前綴樹等。在每個(gè)數(shù)據(jù)結(jié)構(gòu)模塊內(nèi)再融入相關(guān)的算法思想。2.2 原則二同類型題目集中突破這是形成肌肉記憶和思維模式的關(guān)鍵。將相同解法或相同數(shù)據(jù)結(jié)構(gòu)的題目放在一起連續(xù)練習(xí)能讓你快速掌握這類問題的“套路”。例如在“鏈表”模塊我會把涉及虛擬頭節(jié)點(diǎn)、快慢指針、反轉(zhuǎn)鏈表、合并鏈表的題目集中講解讓你一次吃透。2.3 原則三難度螺旋式上升在每個(gè)小模塊內(nèi)題目難度會從Easy到Medium偶爾穿插Hard。這保證了學(xué)習(xí)的平滑性。你不會在還沒掌握基礎(chǔ)遍歷時(shí)就去挑戰(zhàn)復(fù)雜的樹形DP。整個(gè)大路線也是從基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)到基礎(chǔ)算法排序、二分、雙指針再到高級算法回溯、動(dòng)規(guī)、貪心、圖論。2.4 原則四強(qiáng)調(diào)前后關(guān)聯(lián)與知識遷移在講解一道題時(shí)我會明確指出它和之前哪道題的思想一脈相承或者它能為后面哪類難題打下基礎(chǔ)。例如學(xué)會了“兩數(shù)之和”哈希表那么“三數(shù)之和”排序雙指針的解法雖然不同但你可以對比思考為何此處不用哈希表從而加深對算法適用場景的理解。注意這份順序并非LeetCode題號的順序也不同于任何單一的“熱題”列表。它是基于我個(gè)人和眾多上岸者的經(jīng)驗(yàn)重新組織的一個(gè)學(xué)習(xí)路徑。你可以把它看作一門精心編排的“算法課程”大綱?；谝陨显瓌t我規(guī)劃的初始核心路線圖如下第一階段編程基礎(chǔ)與線性結(jié)構(gòu)目標(biāo)熟悉C STL基礎(chǔ)容器操作掌握數(shù)組、字符串、鏈表的常見處理方法。核心題目類型數(shù)組基本操作、字符串處理、鏈表增刪改查、雙指針技巧快慢指針、左右指針。第二階段基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與簡單算法目標(biāo)掌握棧、隊(duì)列、哈希表的應(yīng)用理解遞歸入門二叉樹。核心題目類型棧實(shí)現(xiàn)表達(dá)式求值/括號匹配、隊(duì)列應(yīng)用、哈希表解決查找問題、二叉樹遍歷遞歸/迭代。第三階段中級算法思想目標(biāo)攻克排序、二分查找、滑動(dòng)窗口、回溯算法、基礎(chǔ)動(dòng)態(tài)規(guī)劃。核心題目類型各種排序算法的應(yīng)用場景、二分查找的變體、滑動(dòng)窗口解決子串/子數(shù)組問題、排列組合類回溯、經(jīng)典一維/二維DP問題。第四階段高級數(shù)據(jù)結(jié)構(gòu)與復(fù)雜算法目標(biāo)掌握堆、并查集、圖論算法、復(fù)雜動(dòng)態(tài)規(guī)劃與貪心策略。核心題目類型堆解決TopK問題、并查集處理連通性、圖的DFS/BFS及最短路徑、背包問題、區(qū)間DP、貪心選擇證明。這個(gè)路線是動(dòng)態(tài)的我會在每個(gè)階段的詳解中插入必須掌握的經(jīng)典題目和具有代表性的新題。3. C刷題詳解的核心方法論不止于AC刷題的目標(biāo)不是提交通過而是“掌握”。對于每一道入選的題目我的詳解筆記會包含以下幾個(gè)層次這也是你自查是否真正掌握一道題的標(biāo)準(zhǔn)3.1 題意理解與邊界條件分析這是所有步驟的基礎(chǔ)卻最容易被忽視。我會帶你仔細(xì)審題識別出所有可能的邊界情況空輸入、單個(gè)元素、極大/極小值、負(fù)數(shù)等并在思路分析階段就考慮進(jìn)去。例如鏈表題目常需考慮頭節(jié)點(diǎn)被修改或刪除的情況這通常引入“虛擬頭節(jié)點(diǎn)”技巧。3.2 多解法對比與時(shí)空復(fù)雜度分析一道題往往有多種解法。我會從最直觀的暴力法開始分析其缺點(diǎn)然后逐步優(yōu)化引出更高效的算法。對于每一種解法都會明確給出時(shí)間復(fù)雜度和空間復(fù)雜度并解釋為什么。這能訓(xùn)練你評估算法優(yōu)劣的能力。示例對于“兩數(shù)之和”我們會對比暴力O(n2)和哈希表O(n)解法并討論為何哈希表在此處更優(yōu)頻繁查找。3.3 C實(shí)現(xiàn)細(xì)節(jié)與STL技巧這是本筆記的特色所在。我會提供可直接運(yùn)行的C代碼并重點(diǎn)講解其中的關(guān)鍵點(diǎn)容器選擇為什么用vector而不是deque用unordered_map還是map迭代器與索引在遍歷時(shí)何種情況下用索引訪問更安全清晰何種情況下用迭代器或范圍for循環(huán)更現(xiàn)代函數(shù)參數(shù)傳遞何時(shí)用值傳遞、引用傳遞、常量引用const 這直接影響效率。內(nèi)存與拷貝注意不必要的臨時(shí)對象拷貝特別是在遞歸或循環(huán)中。STL算法應(yīng)用巧妙使用sort,lower_bound,next_permutation等算法能極大簡化代碼。3.4 代碼注釋與可讀性提供的代碼將包含關(guān)鍵步驟的注釋說明“為什么這么做”。良好的變量命名和代碼結(jié)構(gòu)本身就是面試的加分項(xiàng)。3.5 關(guān)聯(lián)題目與舉一反三在題目最后我會列出與之強(qiáng)相關(guān)的題目編號并簡要說明關(guān)聯(lián)點(diǎn)。鼓勵(lì)你立即去嘗試鞏固剛學(xué)到的模式。4. 第一階段詳解數(shù)組、字符串與鏈表實(shí)戰(zhàn)入門讓我們正式進(jìn)入第一階段的實(shí)戰(zhàn)。這是培養(yǎng)代碼感覺和掌握基礎(chǔ)操作的關(guān)鍵時(shí)期。4.1 數(shù)組篇從簡單操作到雙指針?biāo)枷霐?shù)組是連續(xù)的內(nèi)存空間支持隨機(jī)訪問。LeetCode上很多題目本質(zhì)是數(shù)組操作。經(jīng)典入門27. 移除元素題意原地移除數(shù)組中所有值等于val的元素返回新數(shù)組長度。核心解法快慢指針雙指針。這是必須掌握的經(jīng)典范式。C詳解class Solution { public: int removeElement(vectorint nums, int val) { int slowIndex 0; // 慢指針指向下一個(gè)待填充的位置即新數(shù)組的末尾 for (int fastIndex 0; fastIndex nums.size(); fastIndex) { // 快指針遍歷原數(shù)組 if (nums[fastIndex] ! val) { // 當(dāng)快指針找到不需要?jiǎng)h除的元素時(shí) nums[slowIndex] nums[fastIndex]; // 將其賦值給慢指針位置 slowIndex; // 慢指針向前移動(dòng)新數(shù)組長度1 } // 如果等于val快指針繼續(xù)走慢指針不動(dòng)相當(dāng)于“跳過”了這個(gè)元素 } return slowIndex; // 慢指針最終的位置就是新數(shù)組的長度 } };為什么是O(n)時(shí)間復(fù)雜度快指針遍歷一次數(shù)組每個(gè)元素只被處理一次。關(guān)聯(lián)題目26.刪除有序數(shù)組中的重復(fù)項(xiàng)快慢指針變體283.移動(dòng)零本質(zhì)相同。雙指針進(jìn)階977. 有序數(shù)組的平方題意非遞減順序排序的整數(shù)數(shù)組返回每個(gè)數(shù)字平方后按非遞減順序排序的新數(shù)組。核心解法數(shù)組本身有序但平方后最大值在兩端。使用左右指針向中間遍歷比較平方值從后向前填充新數(shù)組。C實(shí)現(xiàn)要點(diǎn)vectorint sortedSquares(vectorint nums) { int n nums.size(); vectorint result(n); // 預(yù)先分配好空間避免push_back int left 0, right n - 1, pos n - 1; // pos指向結(jié)果數(shù)組當(dāng)前待填充的位置從后往前 while (left right) { // 注意等號要處理最后一個(gè)元素 int leftSquare nums[left] * nums[left]; int rightSquare nums[right] * nums[right]; if (leftSquare rightSquare) { result[pos--] leftSquare; left; } else { result[pos--] rightSquare; right--; } } return result; }心得對于需要反向填充或從兩端向中間收斂的問題左右指針是利器。預(yù)先分配vector大小比動(dòng)態(tài)push_back在性能上更優(yōu)。4.2 字符串篇理解不可變性與常用操作在C中string是可變的這比某些語言更方便。重點(diǎn)掌握子串、翻轉(zhuǎn)、匹配等操作。經(jīng)典例題344. 反轉(zhuǎn)字符串題意原地反轉(zhuǎn)字符串必須使用O(1)額外空間。解法左右指針交換。C細(xì)節(jié)使用swap函數(shù)或直接使用異或操作進(jìn)行交換。注意循環(huán)條件是left right。void reverseString(vectorchar s) { for (int i 0, j s.size() - 1; i j; i, j--) { swap(s[i], s[j]); // 標(biāo)準(zhǔn)庫swap // 或者手動(dòng)交換: char temp s[i]; s[i] s[j]; s[j] temp; } }核心挑戰(zhàn)151. 翻轉(zhuǎn)字符串里的單詞題意翻轉(zhuǎn)字符串中單詞的順序并去除多余空格。解題思路這是一道綜合題?？梢苑譃槿饺コ嘤嗫崭袷褂每炻羔樤厝コ孜埠椭虚g多余空格類似數(shù)組移除元素。反轉(zhuǎn)整個(gè)字符串。反轉(zhuǎn)每個(gè)單詞在反轉(zhuǎn)后的字符串中找到每個(gè)單詞的起止位置分別進(jìn)行反轉(zhuǎn)。C實(shí)現(xiàn)關(guān)鍵函數(shù)void removeExtraSpaces(string s) { int slow 0; // 慢指針 for (int fast 0; fast s.size(); fast) { if (s[fast] ! ) { // 遇到非空格就處理即刪除所有空格 if (slow ! 0) s[slow] ; // 在單詞前手動(dòng)添加空格第一個(gè)單詞除外 while (fast s.size() s[fast] ! ) { s[slow] s[fast]; // 拷貝整個(gè)單詞 } } } s.resize(slow); // slow的大小即為去除多余空格后的大小 }關(guān)聯(lián)題目劍指 Offer 58 - II. 左旋轉(zhuǎn)字符串局部反轉(zhuǎn)整體反轉(zhuǎn)技巧。4.3 鏈表篇掌握指針操作與虛擬頭節(jié)點(diǎn)鏈表題目是面試高頻點(diǎn)核心是理解指針引用的指向關(guān)系。建議在紙上畫圖分析?；A(chǔ)操作203. 移除鏈表元素題意刪除鏈表中所有滿足node.val val的節(jié)點(diǎn)。難點(diǎn)頭節(jié)點(diǎn)可能被刪除。這是引入虛擬頭節(jié)點(diǎn)dummy node的經(jīng)典場景。C詳解ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead new ListNode(0); // 創(chuàng)建一個(gè)虛擬頭節(jié)點(diǎn)其next指向真實(shí)頭節(jié)點(diǎn) dummyHead-next head; ListNode* cur dummyHead; // 當(dāng)前檢查的節(jié)點(diǎn)從虛擬頭開始 while (cur-next ! nullptr) { if (cur-next-val val) { // 找到需要?jiǎng)h除的節(jié)點(diǎn) ListNode* tmp cur-next; // 保存待刪除節(jié)點(diǎn) cur-next cur-next-next; // 跳過該節(jié)點(diǎn) delete tmp; // C需要手動(dòng)釋放內(nèi)存面試中需注意 } else { cur cur-next; // 否則當(dāng)前節(jié)點(diǎn)向后移動(dòng) } } head dummyHead-next; // 新的頭節(jié)點(diǎn)可能是原來的下一個(gè)節(jié)點(diǎn) delete dummyHead; // 刪除虛擬頭節(jié)點(diǎn) return head; }重要心得使用虛擬頭節(jié)點(diǎn)可以統(tǒng)一刪除邏輯無需單獨(dú)處理頭節(jié)點(diǎn)。在C中操作鏈表時(shí)一定要注意內(nèi)存管理如果刪除了節(jié)點(diǎn)要用delete釋放除非題目說明不需要。快慢指針應(yīng)用142. 環(huán)形鏈表 II題意判斷鏈表是否有環(huán)并返回環(huán)的入口節(jié)點(diǎn)。Floyd判圈算法這是必須掌握的數(shù)學(xué)結(jié)論。設(shè)置快指針每次兩步和慢指針每次一步。如果快指針遇到nullptr則無環(huán)。如果有環(huán)快慢指針必在環(huán)內(nèi)某點(diǎn)相遇。此時(shí)將其中一個(gè)指針移回鏈表頭然后兩個(gè)指針都每次走一步再次相遇的點(diǎn)即為環(huán)的入口。C代碼框架ListNode *detectCycle(ListNode *head) { ListNode* fast head; ListNode* slow head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { // 相遇有環(huán) ListNode* index1 head; ListNode* index2 fast; // 或slow while (index1 ! index2) { index1 index1-next; index2 index2-next; } return index1; // 環(huán)的入口 } } return nullptr; // 無環(huán) }為什么可行這涉及到數(shù)學(xué)推導(dǎo)。設(shè)頭到入口距離為a入口到相遇點(diǎn)距離為b相遇點(diǎn)再到入口距離為c。第一次相遇時(shí)慢指針走了ab快指針走了an(bc)b。由于快指針?biāo)俣仁锹羔槂杀犊傻胊 (n-1)(bc)c。這個(gè)等式意味著從head走a步和從相遇點(diǎn)走c步再繞n-1圈會到達(dá)同一點(diǎn)入口。所以第二次相遇點(diǎn)就是入口。第一階段的核心是建立對基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的熟練度并初步掌握雙指針這一強(qiáng)大工具。務(wù)必做到每道題都能手寫無誤并理解其所有變種。5. 第二階段詳解哈希表、棧、隊(duì)列與二叉樹基礎(chǔ)掌握了線性結(jié)構(gòu)后我們進(jìn)入更抽象的數(shù)據(jù)結(jié)構(gòu)。它們能幫你解決更復(fù)雜的問題。5.1 哈希表以空間換時(shí)間的利器C中常用unordered_set集合和unordered_map映射。其查找、插入的平均時(shí)間復(fù)雜度為O(1)。經(jīng)典入門1. 兩數(shù)之和題意在數(shù)組中找出和為目標(biāo)值的兩個(gè)數(shù)返回其索引。暴力法兩層循環(huán)O(n2)。哈希表優(yōu)化在遍歷數(shù)組時(shí)對于當(dāng)前元素nums[i]我們檢查target - nums[i]是否在之前遍歷過的元素集合中。為了同時(shí)保存值和索引我們使用unordered_mapint, intkey是數(shù)值value是對應(yīng)索引。C實(shí)現(xiàn)vectorint twoSum(vectorint nums, int target) { unordered_mapint, int hashmap; // value - index for (int i 0; i nums.size(); i) { auto it hashmap.find(target - nums[i]); if (it ! hashmap.end()) { return {it-second, i}; // 找到返回之前存的索引和當(dāng)前索引 } hashmap[nums[i]] i; // 沒找到將當(dāng)前值存入哈希表 } return {}; // 題目保證有解這里為了完整性返回空 }思考為什么邊遍歷邊存而不是先全部存入因?yàn)橐苊馔粋€(gè)元素被使用兩次。例如target6, nums[3]如果先全存進(jìn)去就會找到自己。哈希集合應(yīng)用202. 快樂數(shù)題意判斷一個(gè)數(shù)是否是快樂數(shù)各位平方和最終變?yōu)?。關(guān)鍵如果不是快樂數(shù)平方和會進(jìn)入一個(gè)循環(huán)。如何檢測循環(huán)——哈希集合。C思路計(jì)算平方和如果等于1則返回true如果這個(gè)和已經(jīng)在集合中出現(xiàn)過說明進(jìn)入了循環(huán)返回false否則將和加入集合并繼續(xù)。bool isHappy(int n) { unordered_setint seen; while (n ! 1 !seen.count(n)) { seen.insert(n); n getNext(n); // 計(jì)算下一個(gè)平方和 } return n 1; } int getNext(int n) { int sum 0; while (n 0) { int digit n % 10; sum digit * digit; n / 10; } return sum; }5.2 棧與隊(duì)列理解后進(jìn)先出與先進(jìn)先出棧非常適合處理對稱性、遞歸轉(zhuǎn)迭代、路徑回溯等問題。隊(duì)列則用于BFS廣度優(yōu)先搜索。棧的經(jīng)典應(yīng)用20. 有效的括號題意判斷一個(gè)只包含括號的字符串是否有效。解法遍歷字符串遇到左括號就壓棧遇到右括號就檢查棧頂是否匹配的左括號匹配則彈出不匹配或?？談t無效。最后?？詹庞行А實(shí)現(xiàn)技巧使用unordered_map來映射右括號到左括號使代碼更簡潔。bool isValid(string s) { stackchar st; unordered_mapchar, char pairs {{), (}, {], [}, {}, {}}; for (char ch : s) { if (pairs.count(ch)) { // 當(dāng)前字符是右括號 if (st.empty() || st.top() ! pairs[ch]) { return false; } st.pop(); // 匹配成功彈出棧頂左括號 } else { // 當(dāng)前字符是左括號 st.push(ch); } } return st.empty(); // 最后棧必須為空 }隊(duì)列與BFS入門102. 二叉樹的層序遍歷題意按層返回二叉樹節(jié)點(diǎn)的值。BFS標(biāo)準(zhǔn)模板使用隊(duì)列。將根節(jié)點(diǎn)入隊(duì)然后循環(huán)隊(duì)列不空時(shí)記錄當(dāng)前隊(duì)列大小即本層節(jié)點(diǎn)數(shù)循環(huán)處理該大小的所有節(jié)點(diǎn)出隊(duì)、記錄值、將其左右子節(jié)點(diǎn)入隊(duì)。C代碼vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (!root) return result; queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); // 關(guān)鍵記錄當(dāng)前層的節(jié)點(diǎn)數(shù) vectorint level; for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } result.push_back(level); } return result; }心得levelSize的獲取必須在for循環(huán)之外因?yàn)閝.size()在循環(huán)中是變化的。這是BFS層序遍歷的固定寫法務(wù)必熟記。5.3 二叉樹基礎(chǔ)遞歸與迭代遍歷二叉樹是理解遞歸和后續(xù)復(fù)雜樹形DP的基礎(chǔ)。必須熟練掌握三種深度優(yōu)先遍歷前序、中序、后序的遞歸和迭代寫法。遞歸遍歷以前序?yàn)槔齰oid preorder(TreeNode* root, vectorint res) { if (!root) return; res.push_back(root-val); // 前序根左右 preorder(root-left, res); preorder(root-right, res); }遞歸非常直觀但需要理解函數(shù)調(diào)用棧。面試時(shí)可能會要求寫迭代法。迭代遍歷使用棧模擬遞歸前序迭代由于訪問順序是“根左右”我們可以先將根節(jié)點(diǎn)壓棧然后循環(huán)棧不空出棧訪問然后先右后左壓棧保證出棧時(shí)是左先于右。vectorint preorderTraversal(TreeNode* root) { vectorint result; if (!root) return result; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); result.push_back(node-val); if (node-right) st.push(node-right); // 右先入棧 if (node-left) st.push(node-left); // 左后入棧 } return result; }中序迭代中序是“左根右”需要借助指針來幫助訪問。思路是指針指向當(dāng)前節(jié)點(diǎn)只要節(jié)點(diǎn)不為空就壓棧并向左走cur cur-left節(jié)點(diǎn)為空時(shí)彈出棧頂此時(shí)棧頂是最左側(cè)的節(jié)點(diǎn)訪問它然后指針指向其右子樹。vectorint inorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* st; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { if (cur ! nullptr) { // 指針來訪問節(jié)點(diǎn)訪問到最底層 st.push(cur); // 將訪問的節(jié)點(diǎn)放進(jìn)棧 cur cur-left; // 左 } else { cur st.top(); st.pop(); // 從棧里彈出的數(shù)據(jù)就是要處理的數(shù)據(jù) result.push_back(cur-val); // 中 cur cur-right; // 右 } } return result; }后序迭代后序是“左右根”可以看作是“根右左”的前序遍歷的逆序。所以可以按照類似前序但“先左后右”的順序遍歷最后反轉(zhuǎn)結(jié)果。vectorint postorderTraversal(TreeNode* root) { vectorint result; if (!root) return result; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); result.push_back(node-val); if (node-left) st.push(node-left); // 相對于前序這里順序調(diào)換 if (node-right) st.push(node-right); } reverse(result.begin(), result.end()); // 將結(jié)果反轉(zhuǎn) return result; }掌握二叉樹的遍歷是解決所有樹問題的基礎(chǔ)。很多問題例如求深度、找路徑、判斷對稱等都是遍歷的變體。6. 第三階段詳解回溯、動(dòng)規(guī)與貪心算法精講這是算法學(xué)習(xí)的核心難點(diǎn)也是面試中的重頭戲。理解其思想比背誦模板更重要。6.1 回溯算法枚舉所有可能性的藝術(shù)回溯本質(zhì)是深度優(yōu)先搜索DFS用于解決組合、排列、分割、子集等問題。其核心是“嘗試-回溯”的遞歸過程。模板與核心思想遞歸函數(shù)通常叫backtracking參數(shù)包含當(dāng)前路徑path、當(dāng)前選擇位置startIndex等。終止條件當(dāng)滿足題目要求如路徑長度等于k時(shí)將當(dāng)前路徑加入結(jié)果集。遍歷選擇在當(dāng)前層遍歷所有可能的選擇。做出選擇將選擇加入路徑。遞歸進(jìn)入下一層。撤銷選擇回溯將剛才加入路徑的選擇移除恢復(fù)到之前的狀態(tài)以進(jìn)行下一次嘗試。經(jīng)典例題77. 組合題意從1到n中任選k個(gè)數(shù)的所有組合。C詳解class Solution { private: vectorvectorint result; vectorint path; void backtracking(int n, int k, int startIndex) { if (path.size() k) { // 終止條件路徑長度等于k result.push_back(path); return; } // 遍歷選擇從startIndex開始到 n - (k - path.size()) 1 進(jìn)行剪枝 for (int i startIndex; i n - (k - path.size()) 1; i) { path.push_back(i); // 做出選擇 backtracking(n, k, i 1); // 遞歸下一層從i1開始避免重復(fù) path.pop_back(); // 撤銷選擇回溯 } } public: vectorvectorint combine(int n, int k) { result.clear(); path.clear(); backtracking(n, k, 1); return result; } };關(guān)鍵點(diǎn)startIndex控制下一層遞歸的起始位置保證組合內(nèi)元素不重復(fù)且有序避免出現(xiàn)[2,1]這樣的重復(fù)組合。剪枝優(yōu)化循環(huán)條件i n - (k - path.size()) 1。當(dāng)前還需要k - path.size()個(gè)元素從i開始最多還能選n - i 1個(gè)元素。如果n - i 1 k - path.size()即剩下的元素不夠了就沒必要繼續(xù)了。這是回溯算法性能優(yōu)化的關(guān)鍵。排列問題46. 全排列與組合的區(qū)別排列關(guān)注順序[1,2]和[2,1]是不同的。因此不需要startIndex但需要used數(shù)組記錄哪些元素已經(jīng)被使用過。C實(shí)現(xiàn)void backtrack(vectorint nums, vectorbool used) { if (path.size() nums.size()) { result.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; // 當(dāng)前數(shù)字已使用跳過 used[i] true; path.push_back(nums[i]); backtrack(nums, used); path.pop_back(); used[i] false; } }6.2 動(dòng)態(tài)規(guī)劃從記憶化搜索到狀態(tài)轉(zhuǎn)移動(dòng)態(tài)規(guī)劃是解決具有重疊子問題和最優(yōu)子結(jié)構(gòu)問題的強(qiáng)大工具。其核心是定義狀態(tài)和狀態(tài)轉(zhuǎn)移方程。解題步驟確定dp數(shù)組及下標(biāo)的含義。確定遞推公式狀態(tài)轉(zhuǎn)移方程。dp數(shù)組如何初始化。確定遍歷順序。舉例推導(dǎo)dp數(shù)組用于驗(yàn)證和調(diào)試。經(jīng)典入門70. 爬樓梯題意每次可以爬1或2階到n階有多少種方法。思路dp[i]爬到第i階樓梯的方法數(shù)。要想到達(dá)第i階可以從第i-1階爬1步上來也可以從第i-2階爬2步上來。所以dp[i] dp[i-1] dp[i-2]。初始化dp[1]1,dp[2]2或dp[0]1作為起點(diǎn)。C實(shí)現(xiàn)空間優(yōu)化版int climbStairs(int n) { if (n 2) return n; int dp_i_2 1; // dp[i-2] int dp_i_1 2; // dp[i-1] int dp_i; for (int i 3; i n; i) { dp_i dp_i_1 dp_i_2; dp_i_2 dp_i_1; dp_i_1 dp_i; } return dp_i_1; // 循環(huán)結(jié)束時(shí)dp_i_1就是dp[n] }關(guān)聯(lián)這就是斐波那契數(shù)列。很多簡單DP問題都是斐波那契的變體。背包問題基礎(chǔ)416. 分割等和子集0-1背包題意判斷數(shù)組是否能分成兩個(gè)和相等的子集。轉(zhuǎn)化為背包問題數(shù)組總和為sum目標(biāo)就是找一些數(shù)其和為target sum/2。每個(gè)數(shù)只能選一次這就是0-1背包。DP定義dp[j]容量為j的背包能裝的最大價(jià)值這里價(jià)值重量即數(shù)字本身。但本題是“能否裝滿”所以可以定義dp[j]為容量為j的背包能否恰好裝滿布爾值。狀態(tài)轉(zhuǎn)移對于當(dāng)前數(shù)字nums[i]如果j nums[i]那么dp[j] dp[j] || dp[j - nums[i]]。即不選nums[i]保持dp[j]或選nums[i]看j-nums[i]能否裝滿。C實(shí)現(xiàn)bool canPartition(vectorint nums) { int sum accumulate(nums.begin(), nums.end(), 0); if (sum % 2 ! 0) return false; // 和為奇數(shù)不可能平分 int target sum / 2; vectorbool dp(target 1, false); dp[0] true; // 容量為0的背包不裝任何東西就是滿的 for (int num : nums) { for (int j target; j num; j--) { // 必須倒序遍歷保證每個(gè)物品只使用一次 dp[j] dp[j] || dp[j - num]; } } return dp[target]; }關(guān)鍵心得0-1背包的一維DP數(shù)組實(shí)現(xiàn)內(nèi)層循環(huán)必須倒序遍歷容量。這是因?yàn)閐p[j]依賴于上一輪i-1的dp[j-num]。正序遍歷會覆蓋掉上一輪的值導(dǎo)致一個(gè)物品被重復(fù)使用變成完全背包。6.3 貪心算法局部最優(yōu)與全局最優(yōu)貪心算法的核心是每一步都做出當(dāng)前看起來最優(yōu)的選擇希望導(dǎo)致全局最優(yōu)解。它不像動(dòng)規(guī)有固定的公式更考驗(yàn)對問題性質(zhì)的洞察和證明。簡單貪心455. 分發(fā)餅干題意每個(gè)孩子有胃口值g[i]每塊餅干有尺寸s[j]一塊餅干最多滿足一個(gè)胃口值小于等于它的孩子。求最多滿足的孩子數(shù)。貪心策略為了不浪費(fèi)餅干大餅干優(yōu)先滿足胃口大的孩子或者小餅干優(yōu)先滿足胃口小的孩子。這里采用“小餅干喂飽小胃口”。步驟將g和s排序。用指針i遍歷孩子指針j遍歷餅干。如果s[j] g[i]則滿足兩個(gè)指針都后移否則只移動(dòng)餅干指針j嘗試更大的餅干。C實(shí)現(xiàn)int findContentChildren(vectorint g, vectorint 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; // 滿足一個(gè)孩子 } j; // 無論是否滿足餅干都被嘗試過了 } return i; // i就是被滿足的孩子數(shù)量 }為什么貪心有效可以反證如果最優(yōu)解中有一塊小餅干滿足了一個(gè)大胃口的孩子那么交換一下用這塊小餅干去滿足一個(gè)更小的胃口如果存在不會使結(jié)果變差。所以排序后貪心匹配可以得到最優(yōu)解。貪心算法通常需要證明但在面試中能清晰闡述“為什么這樣貪心”的思路往往比嚴(yán)格證明更重要。對于更復(fù)雜的貪心問題如“區(qū)間調(diào)度”、“跳躍游戲”需要多做練習(xí)來培養(yǎng)直覺。7. 常見問題與排查技巧實(shí)錄在刷題和面試過程中一些常見錯(cuò)誤和調(diào)試技巧能幫你節(jié)省大量時(shí)間。7.1 編譯與語法錯(cuò)誤vector下標(biāo)越界這是最常見的運(yùn)行時(shí)錯(cuò)誤。訪問前務(wù)必檢查索引i是否滿足0 i vec.size()。在循環(huán)中注意邊界條件。空指針訪問對于指針或可能為nullptr的節(jié)點(diǎn)如TreeNode*,ListNode*在訪問其成員-val,-next前必須判空。使用未初始化的變量局部變量不會自動(dòng)初始化使用前請賦值。特別是int,bool等基本類型。函數(shù)返回值確保所有控制路徑都有返回值。編譯器可能會報(bào)錯(cuò)“control reaches end of non-void function”。7.2 邏輯與算法錯(cuò)誤無限遞歸遞歸函數(shù)沒有正確的終止條件或終止條件永遠(yuǎn)達(dá)不到。檢查遞歸基base case是否正確遞歸參數(shù)是否向基 case 收斂。死循環(huán)while或for循環(huán)的終止條件寫錯(cuò)導(dǎo)致循環(huán)變量不更新或更新錯(cuò)誤。在循環(huán)開始和結(jié)束時(shí)打印關(guān)鍵變量值有助于調(diào)試。狀態(tài)未回溯在回溯算法中忘記在遞歸返回后pop_back()或重置used數(shù)組導(dǎo)致狀態(tài)污染。DP數(shù)組初始化錯(cuò)誤dp[0]或邊界條件的初始化至關(guān)重要。例如在背包問題中dp[0]0和dp[0]1代表完全不同的含義。務(wù)必結(jié)合題意和遞推公式推導(dǎo)初始化值。整數(shù)溢出當(dāng)題目涉及大數(shù)運(yùn)算如階乘、指數(shù)或使用int進(jìn)行累加時(shí)注意結(jié)果可能超出int范圍約±21億?？紤]使用long long。7.3 調(diào)試與性能優(yōu)化技巧打印調(diào)試法在關(guān)鍵位置如循環(huán)開始/結(jié)束、遞歸入口/出口打印變量狀態(tài)。對于復(fù)雜數(shù)據(jù)結(jié)構(gòu)鏈表、樹可以編寫簡單的打印函數(shù)。小數(shù)據(jù)測試不要一上來就用復(fù)雜用例。先用題目給的示例甚至自己構(gòu)造更小的、邊界的情況空輸入、單個(gè)元素進(jìn)行測試。對比暴力法如果你的優(yōu)化算法結(jié)果不對可以寫一個(gè)簡單但正確的暴力解法如雙重循環(huán)在小數(shù)據(jù)上對比結(jié)果定位錯(cuò)誤。復(fù)雜度分析提交前預(yù)估算法的時(shí)間和空間復(fù)雜度。如果超時(shí)TLE考慮是否存在更優(yōu)算法如用哈希表O(n)替代暴力O(n2)或者遞歸/回溯中是否可以進(jìn)行剪枝。利用STL特性unordered_map的[]運(yùn)算符在key不存在時(shí)會插入默認(rèn)值而find方法不會。根據(jù)場景選擇使用避免意外插入。容器選擇頻繁在頭部插入/刪除用deque或list隨機(jī)訪問用vector查找用unordered_set/map無序遍歷或set/map有序遍歷。7.4 面試實(shí)戰(zhàn)技巧先溝通再動(dòng)筆拿到題目先和面試官確認(rèn)理解是否正確闡述你的初步思路暴力法、可能的優(yōu)化方向獲得反饋后再開始寫代碼。邊寫邊講寫代碼時(shí)解釋你在做什么為什么這么做。這展示了你的溝通能力和思維過程?？紤]邊界寫完代碼主動(dòng)提出測試一些邊界情況空、單元素、極大值、負(fù)數(shù)等。分析復(fù)雜度代碼完成后主動(dòng)分析時(shí)間復(fù)雜度和空間復(fù)雜度。代碼風(fēng)格使用有意義的變量名適當(dāng)添加注釋保持代碼整潔。在C中注意const的正確使用以及指針/引用的選擇。刷題是一個(gè)持續(xù)積累和反思的過程。這份筆記會隨著我的學(xué)習(xí)和實(shí)踐不斷更新補(bǔ)充更多經(jīng)典的題目和更深入的解析。記住目標(biāo)不是刷完所有題而是通過每一道題掌握一類方法構(gòu)建起自己的算法知識網(wǎng)絡(luò)。當(dāng)你拿到一個(gè)新題能快速將其歸類到某個(gè)已知的模型或模式中時(shí)你就真正入門了。