復(fù)習(xí)C/C刷到第31到40題這個區(qū)間恰好是整個五十題練習(xí)冊里最容易產(chǎn)生“錯覺”的一段字符串、查找、排序看著都眼熟真下手寫代碼邊界條件、指針操作、內(nèi)存釋放卻處處是坑。這一批十道題覆蓋字符串反轉(zhuǎn)、回文判斷、二分查找、鏈表反轉(zhuǎn)、快速排序、斐波那契數(shù)列、字符統(tǒng)計(jì)、動態(tài)二維數(shù)組、括號匹配和最大公約數(shù)幾乎把C/C復(fù)習(xí)最值得練的考點(diǎn)都過了一遍。這篇我按題目分組來寫每道題都給出題目描述、參考實(shí)現(xiàn)、復(fù)雜度分析以及我實(shí)際跑碼時(shí)踩過的坑。適合正在準(zhǔn)備期末、考研復(fù)試或者求職筆試的讀者也適合工作中想把C/C基礎(chǔ)快速撿起來的人。如果你已經(jīng)刷完前面1到30題這一批正好幫你把“感覺會了”變成“真正能寫對”。1. 字符串雙題熱身31題與32題的指針功底1.1 31題不調(diào)用庫函數(shù)實(shí)現(xiàn)字符串反轉(zhuǎn)題目描述實(shí)現(xiàn)一個函數(shù)void reverseString(char s[])把以\0結(jié)尾的字符串原地反轉(zhuǎn)。要求空間復(fù)雜度 O(1)不允許調(diào)用strrev這類現(xiàn)成庫函數(shù)。輸入示例s hello處理后s olleh。這道題考的是雙指針和字符數(shù)組的底層理解。思路很直白left從開頭走right從最后一個字符走兩邊交換直到兩個指針相遇。但“找最后一個字符”這一步新手最容易翻車。void reverseString(char s[]) { if (s nullptr) return; // 空指針直接返回別去解引用 int left 0; int right 0; while (s[right] ! \0) right; // 先找到字符串末尾 right--; // 關(guān)鍵退到最后一個有效字符 while (left right) { char tmp s[left]; s[left] s[right]; s[right] tmp; left; right--; } }我當(dāng)初第一次寫這道題就是忘了right--結(jié)果把\0當(dāng)成有效字符換到了開頭字符串直接被截?cái)?。這個細(xì)節(jié)看著小考場上能卡掉不少人。如果題目沒限制庫函數(shù)用strlen(s) - 1來定位右指針當(dāng)然更省事但這道題既然是練手我建議連strlen也自己寫一遍順便加深對“C風(fēng)格字符串以\0結(jié)尾”這個本質(zhì)的記憶。C 里如果傳入的是std::string同樣思路可以寫成void reverseString(std::string s) { int left 0, right (int)s.size() - 1; while (left right) { std::swap(s[left], s[right]); left; right--; } }復(fù)雜度很干凈時(shí)間 O(n)空間 O(1)。常見變形是把字符串按單詞反轉(zhuǎn)那個要先把整個串反轉(zhuǎn)再逐單詞反轉(zhuǎn)屬于這道題的加強(qiáng)版復(fù)習(xí)時(shí)值得順帶想想。1.2 32題回文判斷邊界條件別偷懶題目描述給定一個字符串判斷它是不是回文?；匚木褪钦x和反著讀一樣比如abcba、abccba。輸入示例abcba返回truehello返回false空串返回true。bool isPalindrome(const char* s) { if (s nullptr) return false; int left 0; int right 0; while (s[right] ! \0) right; right--; while (left right) { if (s[left] ! s[right]) return false; left; right--; } return true; }空串和單字符天然是回文循環(huán)里left right的判斷天然覆蓋了這兩種情況但前提是你別在循環(huán)前面手寫一個if (strlen(s) 0) return false之類的錯誤判斷。邊界題就怕“想當(dāng)然”。這道題的常見升級版是忽略大小寫并且忽略所有非字母數(shù)字字符再判斷回文。很多面試官喜歡在這里追加條件完整寫法是這樣的bool isPalindromeExtended(const std::string s) { int left 0, right (int)s.size() - 1; while (left right) { while (left right !isalnum(s[left])) left; while (left right !isalnum(s[right])) right--; if (tolower(s[left]) ! tolower(s[right])) return false; left; right--; } return true; }加粗提醒isalnum和tolower都在cctype里判斷字符時(shí)要先做 unsigned char 轉(zhuǎn)換再傳進(jìn)去否則對于擴(kuò)展 ASCII 字符可能存在未定義行為這點(diǎn)和后面第 37 題的坑同源。這道題還有個兄弟題型判斷一個int是否為回文數(shù)。做法是把數(shù)字反轉(zhuǎn)一半就和原數(shù)比較避免整個反轉(zhuǎn)溢出。思路相通我建議一題兩練順手把數(shù)字拆解的%、/操作也復(fù)習(xí)了。2. 查找與數(shù)學(xué)題的隱藏考點(diǎn)33題二分查找和40題公約數(shù)2.1 33題二分查找的三個邊界細(xì)節(jié)題目描述給定一個按升序排列的整型數(shù)組和一個目標(biāo)值target返回target在數(shù)組中的下標(biāo)找不到返回 -1。輸入示例arr [1, 3, 5, 7, 9], target 5返回 2。int binarySearch(int arr[], int n, int target) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; // 防止 left right 溢出 if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }二分查找看起來是幾行代碼實(shí)際上有三處細(xì)節(jié)直接決定生死第一循環(huán)條件必須用left right。它表達(dá)的是“target 當(dāng)前可能在 [left, right] 這個閉區(qū)間內(nèi)”。有人改成left right就會漏掉left right時(shí)的最后一個元素。第二mid的寫法要用left (right - left) / 2而不是(left right) / 2。兩個很大的 int 相加可能溢出成負(fù)數(shù)經(jīng)典線上事故。第三區(qū)間收縮用mid 1和mid - 1不能偷懶寫成left mid或right mid否則當(dāng)區(qū)間只剩兩個元素時(shí)會無限循環(huán)。解釋一下為什么不變量這么重要你只要保證“target 一定在 [left, right] 中且區(qū)間長度每次嚴(yán)格遞減”整個算法就不會寫錯。一旦寫出left mid這種代碼區(qū)間不變小死循環(huán)就來敲門了。面試常在這道題后面追一題如果數(shù)組里有重復(fù)元素要求返回第一個等于 target 的下標(biāo)。這時(shí)可以改成right收斂條件為arr[mid] target ? right mid : left mid 1循環(huán)結(jié)束后檢查arr[left]。把基礎(chǔ)二分和這個變體一起練復(fù)習(xí)效率最高。復(fù)雜度時(shí)間 O(log n)空間 O(1)。2.2 40題輾轉(zhuǎn)相除法與最小公倍數(shù)的溢出陷阱題目描述輸入兩個正整數(shù) a 和 b輸出它們的最大公約數(shù)GCD和最小公倍數(shù)LCM。輸入示例a 12, b 18GCD 6LCM 36。教科書算法是輾轉(zhuǎn)相除法核心公式gcd(a, b) gcd(b, a % b)寫成循環(huán)很干凈int gcd(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return a; } int lcm(int a, int b) { return a / gcd(a, b) * b; // 注意先除后乘 }遞歸版本同樣常見面試時(shí)寫遞歸更省事int gcdRecursive(int a, int b) { return b 0 ? a : gcdRecursive(b, a % b); }真正值得記的坑在lcm里為什么用a / gcd(a, b) * b而不是a * b / gcd(a, b)因?yàn)閮蓚€ int 直接相乘很容易溢出 32 位范圍。舉個例子a 2000000000、b 1999999999先乘a * b直接溢出成負(fù)數(shù)先除再乘則大概率在安全范圍內(nèi)。這個“先除后乘”的小習(xí)慣筆試時(shí)能救你一命。順帶一提C17 標(biāo)準(zhǔn)庫提供了std::gcd和std::lcm在numeric里工程上直接用沒問題。但復(fù)習(xí)階段我建議手寫因?yàn)槊嬖嚬傧肟吹氖悄憷斫庠矶皇潜?API。復(fù)雜度 O(log min(a, b))空間 O(1)。3. 鏈表與棧34題反轉(zhuǎn)鏈表的指針陷阱和39題括號匹配3.1 34題鏈表反轉(zhuǎn)的迭代與遞歸雙解法題目描述給定單鏈表頭節(jié)點(diǎn)head反轉(zhuǎn)整個鏈表返回新頭節(jié)點(diǎn)。要求不能改鏈表節(jié)點(diǎn)的值只能改指針。struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; // 迭代法三個指針逐步改向 ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr ! nullptr) { ListNode* next curr-next; // 必須先保存下一個節(jié)點(diǎn) curr-next prev; // 當(dāng)前節(jié)點(diǎn)指向前一個 prev curr; // prev 前進(jìn) curr next; // curr 前進(jìn) } return prev; // 最后 prev 就是新頭節(jié)點(diǎn) }迭代法的靈魂是那三行賦值順序保存next→ 改next→ 移動prev→ 移動curr。我見過不下三個人把next的保存放在curr-next prev之后鏈表當(dāng)場斷成一截程序直接崩潰。這個順序不是死記而是邏輯必然——你先斷了curr-next后面就沒法找到原來的下一個節(jié)點(diǎn)了。遞歸版本的思路略有不同它假設(shè)“后半個鏈表已經(jīng)被反轉(zhuǎn)好”把當(dāng)前節(jié)點(diǎn)接到尾巴上ListNode* reverseListRecursive(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* newHead reverseListRecursive(head-next); head-next-next head; // 讓下一個節(jié)點(diǎn)指向自己 head-next nullptr; // 斷開原來的正向指針 return newHead; }這個遞歸我第一次看的時(shí)候想了半天為什么反過來之后head-next-next是安全的因?yàn)閔ead-next在遞歸深入時(shí)還是原鏈表的下一個節(jié)點(diǎn)反轉(zhuǎn)后它變成了新鏈表的尾部而head恰好要接在這個尾部之后。想通了這層遞歸就徹底看懂了。復(fù)雜度上迭代法時(shí)間 O(n)、空間 O(1)遞歸法時(shí)間 O(n)、空間 O(n)遞歸棧。面試手寫推薦迭代法工程上也更穩(wěn)。這題后續(xù)常追問“反轉(zhuǎn)鏈表前 k 個節(jié)點(diǎn)”建議練習(xí)時(shí)順便把指針操作的套路吃透。3.2 39題括號匹配與棧的使用邊界題目描述給定一個只包含(、)、[、]、{、}的字符串判斷它的括號是否合法。輸入示例()[]{}返回true([)]返回false(]返回false(返回false。棧的經(jīng)典應(yīng)用。遇到左括號就入棧遇到右括號就彈棧頂比對#include stack #include string bool isValid(const std::string s) { std::stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; // 沒有左括號可以配 char top st.top(); if ((c ) top ! () || (c ] top ! [) || (c } top ! {)) { return false; // 類型不匹配 } st.pop(); } } return st.empty(); // 循環(huán)結(jié)束還有左括號剩余 }這道題的三個邊界條件我列出順序筆試時(shí)按這個順序自查遇到右括號時(shí)棧為空說明多了一個右括號直接false。棧頂元素和當(dāng)前右括號類型對不上比如([)]這屬于“數(shù)量對但交叉錯位”必須查類型。循環(huán)結(jié)束后棧不為空說明有多余的左括號比如(((返回false。工程上這套邏輯是編譯器語法解析、表達(dá)式求值、IDE 代碼縮進(jìn)的基礎(chǔ)。理解了這道題后面再學(xué)計(jì)算器實(shí)現(xiàn)里的中綴轉(zhuǎn)后綴就會順很多。復(fù)雜度穩(wěn)定時(shí)間 O(n)空間 O(n)最壞情況全是左括號。4. 排序與遞歸的復(fù)雜度對比35題快排和36題斐波那契4.1 35題手寫快速排序時(shí)選對分劃方式題目描述對一個整型數(shù)組實(shí)現(xiàn)快速排序升序輸出?？焖倥判虻膶懛ㄔ诮炭茣镉泻脦追N我推薦復(fù)習(xí)時(shí)用 Lomuto 分劃法因?yàn)榇a最不容易寫錯int partition(int arr[], int low, int high) { int pivot arr[high]; // 選右端點(diǎn)作為基準(zhǔn) int i low - 1; // i 是最后一個 pivot 的位置 for (int j low; j high; j) { if (arr[j] pivot) { i; std::swap(arr[i], arr[j]); } } std::swap(arr[i 1], arr[high]); // 基準(zhǔn)歸位 return i 1; // 返回基準(zhǔn)最終位置 } void quickSort(int arr[], int low, int high) { if (low high) { int p partition(arr, low, high); quickSort(arr, low, p - 1); quickSort(arr, p 1, high); } }理解 Lomuto 的關(guān)鍵是i這個指針?biāo)肋h(yuǎn)指向“已經(jīng)掃描過的部分里最后一個小于等于 pivot 的元素”。j從頭掃到尾只要發(fā)現(xiàn)arr[j] pivot就把它換到i1的位置。掃描結(jié)束i1就是 pivot 該待的地方。為什么推薦 Lomuto 而不是教科書里那種“左右雙指針、一個從右往左找小、一個從左往右找大”的寫法因?yàn)槟欠N寫法雖然實(shí)際運(yùn)行更快但邊界條件極其容易寫串——我見過太多人把a(bǔ)rr[i] pivot和arr[j] pivot的等號處理反導(dǎo)致死循環(huán)。Lomuto 幾個分支清清楚楚考試時(shí)寧可慢一點(diǎn)也要寫對?？焖倥判虻膹?fù)雜度要背清楚平均 O(n log n)最壞 O(n^2)發(fā)生在每次基準(zhǔn)都恰好選中最大或最小元素比如對已排序數(shù)組固定選右端點(diǎn)。工程上會加隨機(jī)選基準(zhǔn)或者三數(shù)取中來規(guī)避?？臻g復(fù)雜度 O(log n)遞歸棧。還有一個特性不穩(wěn)定排序這點(diǎn)面試喜歡追問。4.2 36題斐波那契數(shù)列是遞歸性能的典型教材題目描述求斐波那契數(shù)列第 n 項(xiàng)F(0) 0, F(1) 1, F(n) F(n-1) F(n-2)。輸入示例n 10輸出 55。這道題的三種寫法正好可以對照“遞歸的性能陷阱”// 寫法一樸素遞歸指數(shù)級復(fù)雜度n50 就卡死 long long fibRecursive(int n) { if (n 1) return n; return fibRecursive(n - 1) fibRecursive(n - 2); } // 寫法二迭代滾動數(shù)組時(shí)間 O(n)、空間 O(1) long long fibIterative(int n) { if (n 1) return n; long long a 0, b 1; for (int i 2; i n; i) { long long c a b; a b; b c; } return b; } // 寫法三記憶化遞歸時(shí)間 O(n)、空間 O(n) long long fibMemo(int n, std::vectorlong long memo) { if (n 1) return n; if (memo[n] ! -1) return memo[n]; memo[n] fibMemo(n - 1, memo) fibMemo(n - 2, memo); return memo[n]; }樸素遞歸慢的原因值得展開它會把fib(n-1)和fib(n-2)當(dāng)成兩個獨(dú)立問題遞歸求解于是fib(1)被重復(fù)計(jì)算了幾萬次。計(jì)算量以 1.618 的 n 次方增長n 50的時(shí)候要算大約 200 億次實(shí)際跑起來按分鐘計(jì)。迭代寫法把每個子問題只算一遍這就是“重疊子問題”和動態(tài)規(guī)劃思想的雛形。還有一個實(shí)際細(xì)節(jié)long long也扛不住很大的 n。fib(93)大約 1.22e19已經(jīng)逼近long long最大值 9.22e18實(shí)際上fib(94)就會溢出。所以考試時(shí)如果 n 可能到 100題目一般會要求“輸出對某個大數(shù)取?！被蛘吣愀纱嘤胾nsigned long long并小心驗(yàn)證范圍。練習(xí)題里通常限制 n 60用long long沒問題但要知道這個邊界在哪。5. 數(shù)組與內(nèi)存細(xì)節(jié)37題字符統(tǒng)計(jì)和38題動態(tài)二維數(shù)組5.1 37題字符頻率統(tǒng)計(jì)的下標(biāo)陷阱題目描述給定一個字符串統(tǒng)計(jì)每個字符出現(xiàn)的次數(shù)按字符從小到大輸出出現(xiàn)次數(shù)大于 0 的項(xiàng)。輸入示例s hello輸出e: 1, h: 1, l: 2, o: 1。最簡單高效的辦法是用數(shù)組當(dāng)哈希表ASCII 字符一共 256 個一個int count[256]足夠#include iostream #include string void countCharacters(const std::string s) { int count[256] {0}; for (char c : s) { count[(unsigned char)c]; // 必須強(qiáng)轉(zhuǎn) unsigned char } for (int i 0; i 256; i) { if (count[i] 0) { std::cout (char)i : count[i] std::endl; } } }這題最大的坑在count[(unsigned char)c]。C 的char是有符號還是無符號由編譯器決定很多平臺上它是 signed取值范圍 -128 到 127。如果字符串里有一個字節(jié)值大于 127 的字符直接count[c]就會用負(fù)數(shù)下標(biāo)訪問數(shù)組越界讀內(nèi)存結(jié)果完全不可預(yù)期。我見過有人在處理帶重音符號的文本時(shí)程序突然輸出一堆亂碼排查半天才發(fā)現(xiàn)是這個負(fù)下標(biāo)問題。另一個擴(kuò)展點(diǎn)是如果字符串里包含中文UTF-8 多字節(jié)編碼按char統(tǒng)計(jì)就失去意義了因?yàn)橐粋€漢字由三到四個字節(jié)組成每個字節(jié)單獨(dú)統(tǒng)計(jì)沒有任何語義。這時(shí)候要用std::unordered_mapstd::string, int按“碼點(diǎn)”或者按字節(jié)序列統(tǒng)計(jì)。練習(xí)題通常限 ASCII但要心里有數(shù)。復(fù)雜度時(shí)間 O(n)空間 O(1)固定 256 大小。這題還有個常見變體是找出現(xiàn)次數(shù)最多的字符只需要在統(tǒng)計(jì)時(shí)維護(hù)一個maxIndex就行。5.2 38題動態(tài)二維數(shù)組的申請與釋放題目描述輸入行數(shù) n 和列數(shù) m動態(tài)申請一個 int 類型的 n 行 m 列二維數(shù)組填入數(shù)據(jù)后輸出最后正確釋放內(nèi)存。動態(tài)二維數(shù)組在 C 里的經(jīng)典做法是指針數(shù)組int** createMatrix(int n, int m) { int** mat new int*[n]; // 先申請 n 個行指針 for (int i 0; i n; i) { mat[i] new int[m]; // 每行再申請 m 個 int } return mat; } void freeMatrix(int** mat, int n) { if (mat nullptr) return; for (int i 0; i n; i) { delete[] mat[i]; // 先釋放每一行的數(shù)組 } delete[] mat; // 再釋放行指針數(shù)組 }這里要背熟兩條鐵律第一new[]必須配delete[]new配delete絕對不能混用。釋放了錯誤的對象行為未定義不報(bào)錯才是運(yùn)氣好。第二釋放順序不能亂——先釋放每行的mat[i]最后釋放mat本身。如果反著來你會先丟了行指針數(shù)組后面每一行都找不著直接內(nèi)存泄露。工程上我更推薦另一種布局開一塊連續(xù)的一維數(shù)組來代替二維數(shù)組int* data new int[n * m]; // 訪問第 i 行第 j 列data[i * m j] delete[] data;這種做法的好處我提三個一是緩存局部性好遍歷時(shí)按連續(xù)地址訪問快得多二是申請和釋放都只做一次代碼不容易出錯三是不會有“每行指針散落各處”的內(nèi)存碎片問題。做數(shù)值計(jì)算的項(xiàng)目基本都這么干。練習(xí)題如果沒限定必須是int**可以主動用連續(xù)數(shù)組方案面試時(shí)反而顯得有工程經(jīng)驗(yàn)。排查內(nèi)存錯誤我建議用 AddressSanitizer編譯時(shí)加-fsanitizeaddress越界和泄漏會在運(yùn)行時(shí)直接報(bào)出來比用valgrind在 Windows 折騰配置要省心得多。6. 十道題復(fù)盤考點(diǎn)地圖與復(fù)習(xí)順序十道題刷完先別急著翻下一批。我建議用一張表把知識點(diǎn)和易錯點(diǎn)過一遍這比反復(fù)抄代碼有效題號核心考點(diǎn)時(shí)間復(fù)雜度高頻易錯點(diǎn)31字符串、雙指針O(n)把\0當(dāng)有效字符交換32字符串、邊界判斷O(n)忽略大小寫/非字母數(shù)字條件漏寫33二分查找、區(qū)間不變量O(log n)mid 溢出、left mid死循環(huán)34鏈表、指針操作O(n)改指針前沒保存next35分治、遞歸、不穩(wěn)定排序O(n log n) 平均分劃邊界寫錯、基準(zhǔn)退化36遞歸 vs 迭代、動態(tài)規(guī)劃O(n) 迭代樸素遞歸重復(fù)計(jì)算、long long 溢出37哈希思想、類型轉(zhuǎn)換O(n)signed char 負(fù)下標(biāo)越界38動態(tài)內(nèi)存、new/deleteO(n)釋放順序錯、漏釋放行39棧、括號類型匹配O(n)遇到右括號時(shí)?？瘴磁袛?0輾轉(zhuǎn)相除法、溢出O(log min(a,b))LCM 先乘后除溢出我個人復(fù)習(xí)時(shí)的順序是這樣的先把 31、32、40 當(dāng)熱身題要求自己五分鐘內(nèi)無錯寫出來然后攻 33、36、37 這三道“模板題”重點(diǎn)背邊界寫法和復(fù)雜度最后啃 34、35、38、39 這四道數(shù)據(jù)結(jié)構(gòu)題每道題至少手寫兩遍。兩遍之間隔兩周避免短期記憶的假象。實(shí)操上還有一個笨但有用的方法把每道題改一個條件再寫一遍。比如 32 題改成忽略大小寫33 題改成返回第一個等于 target 的下標(biāo)39 題改成同時(shí)支持和的尖括號。這樣一變你對原題的理解立刻暴露無遺比對著答案抄十遍都管用。這一批題目真正的價(jià)值不在于“會做”而在于“想明白為什么這么做”。鏈表斷鏈的瞬間、二分死循環(huán)的調(diào)試、字符負(fù)下標(biāo)的詭異越界——這些體驗(yàn)都是紙面刷題給不了的。把代碼親自跑通、把錯誤親眼看到第 41 到 50 題再往下走就會輕松很多。