聊一個(gè)每年都會(huì)被反復(fù)問(wèn)起的話題C開(kāi)發(fā)崗的校招筆試到底怎么準(zhǔn)備。尤其是網(wǎng)易這種大廠的正式批題量和難度都不是隨便刷幾十道LeetCode就能應(yīng)付的它既要考察你對(duì)C語(yǔ)言本身的掌握深度又要看你在有限時(shí)間里的工程思維和代碼實(shí)現(xiàn)能力。這篇東西我結(jié)合近兩年校招筆試的常見(jiàn)風(fēng)格以網(wǎng)易2023校招筆試C開(kāi)發(fā)工程師正式第二批為切入點(diǎn)把筆試前中后最值得關(guān)注的東西拆開(kāi)講一遍包括考點(diǎn)分布、高頻知識(shí)點(diǎn)、算法套路、環(huán)境配置和復(fù)盤(pán)方法希望能給準(zhǔn)備C校招的同學(xué)一條相對(duì)清晰的路線。這篇文章適合誰(shuí)看一種是已經(jīng)投了簡(jiǎn)歷、正在刷題準(zhǔn)備筆試的應(yīng)屆生另一種是剛學(xué)完C基礎(chǔ)、想了解大廠筆試到底考什么的學(xué)生。不管你屬于哪一類按我這個(gè)思路去準(zhǔn)備至少不會(huì)在筆試現(xiàn)場(chǎng)發(fā)懵。1. 筆試之前先把崗位和考察方向摸清楚1.1 網(wǎng)易C開(kāi)發(fā)崗位到底在招什么樣的人網(wǎng)易的C開(kāi)發(fā)崗位并不是一個(gè)籠統(tǒng)的“后臺(tái)開(kāi)發(fā)”它覆蓋的方向很多游戲引擎、客戶端、服務(wù)端、云音樂(lè)底層、云信通信、大數(shù)據(jù)中間件等。不同方向?qū)的側(cè)重點(diǎn)差別很大但筆試階段基本是一套通用C卷子這意味著你不需要猜測(cè)具體是哪個(gè)組出的題只需要把C語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)算法這兩個(gè)基本面打扎實(shí)。從筆試的角度看網(wǎng)易這類大廠考察的核心其實(shí)是三件事第一你是否真正理解C的對(duì)象模型、內(nèi)存管理、模板和STL的實(shí)現(xiàn)機(jī)制而不是只停留在“會(huì)用”的層面第二你是否具備扎實(shí)的算法功底能在限時(shí)內(nèi)把一道中等偏難度的題寫(xiě)出來(lái)并保證正確性第三代碼風(fēng)格和邊界處理能力很多同學(xué)思路是對(duì)的但一寫(xiě)代碼就漏邊界條件這類人往往會(huì)被卡在筆試篩選中。我自己帶過(guò)不少實(shí)習(xí)生也看過(guò)很多校招簡(jiǎn)歷一個(gè)很直觀的感受是C崗位的筆試篩選篩掉的往往不是不會(huì)寫(xiě)算法的人而是“以為自己會(huì)C、但實(shí)際上說(shuō)不出底層原理”的人。所以準(zhǔn)備筆試前建議先給自己做個(gè)摸底問(wèn)幾個(gè)問(wèn)題虛函數(shù)表是怎么分布的vector擴(kuò)容的拷貝/移動(dòng)語(yǔ)義是怎么觸發(fā)的std::function和函數(shù)指針的區(qū)別是什么如果答不上來(lái)那就說(shuō)明你的C復(fù)習(xí)還停留在語(yǔ)法層面筆試選擇題會(huì)很吃虧。1.2 校招筆試的常見(jiàn)流程與平臺(tái)細(xì)節(jié)網(wǎng)易校招筆試通常采用?？途W(wǎng)或賽碼網(wǎng)這類在線評(píng)測(cè)平臺(tái)筆試時(shí)間一般安排在工作日晚上的19:00到21:00左右持續(xù)120分鐘。題型分布大致是單選題15~20道、多選題5~10道、編程題2~3道部分批次還可能包含簡(jiǎn)答題或設(shè)計(jì)題。這里有一個(gè)容易被忽略的點(diǎn)在線OJ環(huán)境和本地IDE是有差異的。你本機(jī)用VS Code寫(xiě)得好好的代碼粘貼到OJ上可能因?yàn)轭^文件缺失、輸入輸出格式不對(duì)而編譯失敗。所以筆試前一定要去?？途W(wǎng)熟悉一下它的代碼編輯器尤其是“本地通過(guò)、提交不過(guò)”這個(gè)問(wèn)題——絕大多數(shù)都是因?yàn)閙ain函數(shù)返回值、輸入循環(huán)讀入方式、或者輸出多了空格換行這些細(xì)節(jié)。提示網(wǎng)易筆試的編程題通常允許使用C14或C17標(biāo)準(zhǔn)支持STL但不同批次的編譯器版本可能不同。考試前記得看考試須知如果支持C17就直接用結(jié)構(gòu)化綁定、std::optional這些特性如果不確定版本就老老實(shí)實(shí)寫(xiě)C11兼容代碼。筆試開(kāi)始前還有幾個(gè)實(shí)操細(xì)節(jié)需要提前確認(rèn)身份證/學(xué)生證放在手邊網(wǎng)絡(luò)穩(wěn)定準(zhǔn)備一個(gè)本地調(diào)試環(huán)境以備在線編輯器不好用的情況。另外建議準(zhǔn)備一個(gè)自己的代碼模板比如快讀快寫(xiě)模板、常用頭文件集合、并查集模板、最短路模板這個(gè)在筆試前整理好能幫你節(jié)省不少時(shí)間。2. 試卷結(jié)構(gòu)與高頻考點(diǎn)拆解2.1 選擇題C基礎(chǔ)、八股文和易錯(cuò)點(diǎn)網(wǎng)易筆試的選擇題部分覆蓋面很廣但C相關(guān)題目主要集中在以下幾個(gè)方向虛函數(shù)和多態(tài)、const和constexpr、static關(guān)鍵字、智能指針、左值右值與移動(dòng)語(yǔ)義、類型轉(zhuǎn)換、內(nèi)存對(duì)齊、STL容器底層實(shí)現(xiàn)和迭代器失效問(wèn)題。這些題目表面上考的是語(yǔ)法細(xì)節(jié)但背后考的是語(yǔ)言機(jī)制。比如它問(wèn)你“下面哪一個(gè)不會(huì)引起vector迭代器失效”這時(shí)候你如果只靠背結(jié)論換一個(gè)問(wèn)法就容易懵。更好的復(fù)習(xí)方式是把每一個(gè)易錯(cuò)點(diǎn)都往“為什么”方向深挖一層vector在插入元素導(dǎo)致重新分配時(shí)所有迭代器都會(huì)失效但如果只是erase掉中間某個(gè)元素那被刪元素之后的迭代器會(huì)失效之前的不會(huì)。這個(gè)結(jié)論不是靠背而是因?yàn)関ector底層是連續(xù)內(nèi)存上的動(dòng)態(tài)數(shù)組理解了內(nèi)存模型你就能推導(dǎo)出所有迭代器失效場(chǎng)景。為什么這里強(qiáng)調(diào)“理解底層”而不是“背誦”因?yàn)樾Ｕ泄P試題有一個(gè)特點(diǎn)同樣的知識(shí)點(diǎn)它一定會(huì)換一個(gè)說(shuō)法來(lái)考你甚至?xí)褍蓚€(gè)知識(shí)點(diǎn)混在一起出題。比如“const char* p”和“char* const p”的區(qū)別、或者“在C11以后為什么建議用nullptr而不是NULL”這些如果只是背結(jié)論到了考場(chǎng)上換個(gè)包裝照樣錯(cuò)。我做了一個(gè)高頻選擇題考點(diǎn)的整理供大家對(duì)照自查知識(shí)點(diǎn)常見(jiàn)考法易錯(cuò)點(diǎn)虛函數(shù)與多態(tài)構(gòu)造函數(shù)/析構(gòu)函數(shù)能否為虛函數(shù)構(gòu)造函數(shù)不能是虛函數(shù)析構(gòu)函數(shù)建議聲明為虛函數(shù)內(nèi)存對(duì)齊結(jié)構(gòu)體sizeof計(jì)算對(duì)齊規(guī)則、pragma pack的影響左值右值std::move和移動(dòng)構(gòu)造的使用場(chǎng)景move之后原對(duì)象處于“有效但未指定”狀態(tài)智能指針shared_ptr循環(huán)引用能否導(dǎo)致內(nèi)存泄漏循環(huán)引用必須用weak_ptr打破類型轉(zhuǎn)換static_cast/dynamic_cast/const_cast/reinterpret_cast的區(qū)別dynamic_cast要求多態(tài)類型且運(yùn)行時(shí)安全檢查STL容器map底層紅黑樹(shù)unordered_map底層哈希表有序性和復(fù)雜度差異動(dòng)態(tài)內(nèi)存new/delete與malloc/free的差異new會(huì)調(diào)用構(gòu)造函數(shù)delete會(huì)調(diào)用析構(gòu)函數(shù)2.2 編程題算法、STL與工程落地網(wǎng)易筆試的編程題一般2~3道通常是一道簡(jiǎn)單/中等題、一道中等偏難題、一道綜合題。簡(jiǎn)單那題往往就是字符串處理或模擬中等題可能是動(dòng)態(tài)規(guī)劃、貪心、二分、圖論中的一種綜合題則可能把多個(gè)知識(shí)點(diǎn)串在一起比如“字符串哈希雙指針”的組合。你需要特別注意的一點(diǎn)是筆試編程題只要求你提交一個(gè)可以運(yùn)行的完整程序并不要求你封裝成一個(gè)類。這和LeetCode上的做題方式有明顯的差異——LeetCode已經(jīng)幫你把輸入輸出處理好了你只需要寫(xiě)核心函數(shù)但校招筆試通常要求你自己處理輸入如果輸入讀取方式不對(duì)即使算法正確也會(huì)掛。舉例來(lái)說(shuō)假設(shè)題目要求讀取多行每行兩個(gè)整數(shù)遇到EOF結(jié)束正確寫(xiě)法是#include bits/stdc.h using namespace std; int main() { int a, b; while (cin a b) { cout a b endl; } return 0; }看起來(lái)簡(jiǎn)單但如果你寫(xiě)成固定讀一次或沒(méi)有處理EOF在線評(píng)測(cè)就會(huì)判你超時(shí)或答案錯(cuò)誤。此外筆試編程題對(duì)復(fù)雜度的要求往往會(huì)在描述中明確給出比如“n 10^5”時(shí)你的算法必須達(dá)到O(n log n)或O(n)如果是O(n^2)基本就超時(shí)。所以筆試前一定要養(yǎng)成先看數(shù)據(jù)范圍的習(xí)慣數(shù)據(jù)范圍直接決定了算法選型這比上來(lái)就寫(xiě)代碼重要得多。2.3 筆試題的難度與時(shí)間分配建議以正式第二批的難度來(lái)估算選擇題的閱讀量其實(shí)不小很多同學(xué)會(huì)陷在某個(gè)多選題里反復(fù)糾結(jié)最后編程題時(shí)間不夠。我的建議是選擇題每道控制在1.5分鐘以內(nèi)遇到拿不準(zhǔn)的先標(biāo)記跳過(guò)不要浪費(fèi)超過(guò)2分鐘編程題按“先易后難”的順序做。先把有把握的編程題做出來(lái)、提交并且通過(guò)自測(cè)再回頭啃不會(huì)的選擇題。這里的邏輯是編程題在總分中的占比通常更高而且兩題之間的分值差距可能很大首先把能拿的分?jǐn)?shù)拿到手這是筆試時(shí)間管理最重要的原則。時(shí)間分配參考表題型建議用時(shí)策略單選/多選題40~50分鐘不會(huì)的先跳過(guò)不要戀戰(zhàn)編程題第1題20分鐘通過(guò)全部用例再提交編程題第2題30分鐘先暴力再優(yōu)化拿部分分編程題第3題20~30分鐘寫(xiě)不出正解也要寫(xiě)暴力/特判檢查10分鐘檢查編譯環(huán)境、輸入輸出格式有一種很典型的丟分場(chǎng)景編程題寫(xiě)完了但沒(méi)測(cè)試極端邊界比如數(shù)組長(zhǎng)度為0、輸入負(fù)數(shù)、字符串為空的情況。筆試結(jié)束考官不會(huì)給你任何反饋所以提交前務(wù)必自己構(gòu)造幾個(gè)邊界用例去跑一遍。3. C核心知識(shí)點(diǎn)系統(tǒng)復(fù)習(xí)3.1 constexpr的作用與版本演化熱詞里有一個(gè)“constexpr哪個(gè)C版本引入的”這個(gè)問(wèn)題本身也是筆試選擇題的高頻考點(diǎn)。constexpr是在C11中引入的關(guān)鍵字它的核心價(jià)值是讓表達(dá)式在編譯期就能被求值從而把一部分運(yùn)行期計(jì)算轉(zhuǎn)移到編譯期提升程序運(yùn)行效率。C11剛引入constexpr時(shí)限制很多函數(shù)體只能有一條return語(yǔ)句循環(huán)、分支都不能用。C14大幅放寬了限制允許在constexpr函數(shù)中使用局部變量、循環(huán)和分支。C17之后constexpr變得更加強(qiáng)大甚至可以在構(gòu)造函數(shù)中使用從而構(gòu)造constexpr對(duì)象。到了C20constexpr函數(shù)中可以出現(xiàn)try-catch和某些形式的動(dòng)態(tài)內(nèi)存分配但校招筆試問(wèn)到這一層的不多記住C11引入、C14放寬、C17支持constexpr構(gòu)造函數(shù)這幾個(gè)里程碑就夠用了。舉個(gè)例子筆試中可能會(huì)出現(xiàn)這樣的題目判斷以下代碼能否編譯通過(guò)。constexpr int square(int x) { return x * x; } constexpr int val square(5);C11和C14都能編譯因?yàn)楹瘮?shù)體只有一條return語(yǔ)句。但如果把square改成多行循環(huán)寫(xiě)法constexpr int sum(int n) { int s 0; for (int i 1; i n; i) { s i; } return s; }這段代碼在C11標(biāo)準(zhǔn)下編譯不過(guò)在C14標(biāo)準(zhǔn)下可以。這就是常考的點(diǎn)。答案是C14在編譯期求值能力上做了大升級(jí)。做題時(shí)如果題目沒(méi)有明確說(shuō)明標(biāo)準(zhǔn)版本筆試環(huán)境通常默認(rèn)支持C14或C17按較新標(biāo)準(zhǔn)理解即可。3.2 多線程、ABA問(wèn)題與并發(fā)安全“ABA問(wèn)題C”是另一個(gè)非常典型的高頻考點(diǎn)。ABA問(wèn)題發(fā)生在無(wú)鎖編程的CASCompare-And-Swap操作中。簡(jiǎn)單來(lái)說(shuō)線程1從內(nèi)存位置X讀取到值A(chǔ)然后被調(diào)度掛起線程2把X從A改成B又改回A線程1恢復(fù)運(yùn)行后執(zhí)行CAS發(fā)現(xiàn)X還是A于是判斷“沒(méi)人動(dòng)過(guò)”CAS成功——但實(shí)際上這個(gè)位置已經(jīng)被線程2修改過(guò)兩次了。為什么這是一個(gè)問(wèn)題因?yàn)镃AS比較的只是“值是否相等”它無(wú)法判斷“這個(gè)值是不是被修改過(guò)后又變回了原樣”。在需要基于狀態(tài)流轉(zhuǎn)做決策的場(chǎng)合ABA問(wèn)題會(huì)導(dǎo)致邏輯錯(cuò)誤。比如一個(gè)用CAS實(shí)現(xiàn)的棧如果棧頂節(jié)點(diǎn)被彈出又壓入一個(gè)地址相同的節(jié)點(diǎn)另一個(gè)線程可能誤判棧沒(méi)有變化。解決辦法最常用的是版本號(hào)/標(biāo)記法也就是在要保護(hù)的變量旁邊加一個(gè)遞增的版本號(hào)每次修改都同時(shí)更新版本號(hào)CAS時(shí)不僅比較值還比較版本號(hào)struct Node { int data; }; std::atomicint version{0}; std::atomicNode* ptr{nullptr}; void update(Node* new_node) { Node* old ptr.load(); int old_ver version.load(); // 需要同時(shí)比較ptr和version // 在C中可以用atomicstd::pair...或指針標(biāo)記打包實(shí)現(xiàn) }筆試?yán)镆话悴粫?huì)讓你完整實(shí)現(xiàn)一個(gè)無(wú)鎖容器更多是考概念A(yù)BA是什么、為什么危險(xiǎn)、常見(jiàn)解決方案是什么。應(yīng)對(duì)策略是把“Compare-And-Swap、值相同不代表沒(méi)變過(guò)、版本號(hào)方案”這三句話講清楚。在校招面試中多線程的考察還會(huì)延伸到std::thread、std::mutex、std::atomic、條件變量、死鎖的四個(gè)必要條件等。筆試選擇題可能考到的點(diǎn)包括unique_lock和lock_guard的區(qū)別atomic為什么能保證原子性內(nèi)存序memory_order的含義。這些不需要你寫(xiě)出完整的并發(fā)代碼但概念要能辨析清楚。3.3 設(shè)計(jì)模式與C實(shí)現(xiàn)“C設(shè)計(jì)模式”搜索熱度一直很高網(wǎng)易筆試雖然很少直接考“請(qǐng)用代碼實(shí)現(xiàn)單例模式”但選擇題中經(jīng)常出現(xiàn)設(shè)計(jì)模式相關(guān)的判斷比如“下面哪種設(shè)計(jì)模式用于在不改變類的前提下擴(kuò)展功能”選項(xiàng)里混著模板方法、策略、裝飾器、適配器這些容易混淆。備考建議是至少把單例、工廠、觀察者、策略、裝飾器這五種的類圖和應(yīng)用場(chǎng)景吃透。單例模式必須能手寫(xiě)包括兩個(gè)版本// 懶漢式線程安全版本C11之后 class Singleton { public: static Singleton getInstance() { static Singleton instance; return instance; } Singleton(const Singleton) delete; Singleton operator(const Singleton) delete; private: Singleton() {} };C11之后局部靜態(tài)變量的初始化是線程安全的所以不需要自己加鎖這個(gè)寫(xiě)法既簡(jiǎn)潔又安全筆試/面試中寫(xiě)這個(gè)版本基本不會(huì)錯(cuò)。工廠模式在游戲開(kāi)發(fā)中應(yīng)用很廣網(wǎng)易游戲方向的崗位尤其喜歡考。簡(jiǎn)單工廠的本質(zhì)是“用一個(gè)工廠類根據(jù)參數(shù)決定創(chuàng)建哪種產(chǎn)品”工廠方法的本質(zhì)是“把創(chuàng)建邏輯延遲到子類”抽象工廠則是“創(chuàng)建一族相關(guān)產(chǎn)品”。選擇題里?？嫉木褪沁@幾個(gè)概念的區(qū)分。3.4 C面試必背的“八股文”清單“C八股文”這個(gè)詞在熱詞里出現(xiàn)頻率很高其實(shí)它指的就是那些校招面試中反復(fù)出現(xiàn)的基礎(chǔ)題。準(zhǔn)備筆試同樣需要這些知識(shí)因?yàn)檫x擇題就是八股文的選擇題版。我按自己的經(jīng)驗(yàn)整理了一個(gè)最短清單八股文問(wèn)題必考點(diǎn)虛函數(shù)是怎么實(shí)現(xiàn)的虛表指針、虛函數(shù)表、動(dòng)態(tài)綁定vector底層機(jī)制動(dòng)態(tài)數(shù)組、倍增擴(kuò)容、迭代器失效智能指針有哪些unique_ptr/shared_ptr/weak_ptr、引用計(jì)數(shù)深拷貝淺拷貝默認(rèn)拷貝構(gòu)造函數(shù)是淺拷貝、需要深拷貝時(shí)自實(shí)現(xiàn)new和malloc區(qū)別構(gòu)造/析構(gòu)、類型安全、重載、失敗處理多態(tài)條件繼承、虛函數(shù)重寫(xiě)、基類指針/引用調(diào)用STL六大組件容器、算法、迭代器、仿函數(shù)、適配器、配置器map和unordered_map區(qū)別紅黑樹(shù) vs 哈希表、有序性、復(fù)雜度靜態(tài)庫(kù)和動(dòng)態(tài)庫(kù)區(qū)別編譯期鏈接 vs 運(yùn)行期加載、體積與發(fā)布回調(diào)函數(shù)函數(shù)指針、std::function、std::bind、lambda這些不是背一遍就完事每一條最好都能在十分鐘內(nèi)講清楚。筆試的選擇題往往就是從這些角度切入的只是用選擇和判斷的方式考察罷了。4. 編程題里讓人上分的算法套路4.1 快速冪高頻且短小精悍熱詞里“快速冪算法C”搜索量很高這確實(shí)是一個(gè)筆試/面試都?？嫉乃惴ǘ绦?、經(jīng)典、能考察位運(yùn)算和分治思維?？焖賰绲暮诵氖嵌謨缢枷氚阎笖?shù)b拆解成二進(jìn)制形式從最低位開(kāi)始處理同時(shí)不斷把底數(shù)平方。long long fastPow(long long a, long long b, long long mod) { long long ans 1 % mod; a % mod; while (b 0) { if (b 1) { ans ans * a % mod; } a a * a % mod; b 1; } return ans; }為什么這個(gè)算法是O(log b)因?yàn)槊垦h(huán)一次指數(shù)b的二進(jìn)制位右移一位循環(huán)次數(shù)等于b的二進(jìn)制位數(shù)。筆試?yán)锶绻}目要求計(jì)算a的b次方對(duì)p取模且b的范圍達(dá)到10^18那么直接for循環(huán)乘法是絕對(duì)超時(shí)的必須用快速冪。這里有一個(gè)筆試很容易踩的坑a和b的類型必須給足如果a, b, mod都是inta * a這一步就可能溢出。所以建議在實(shí)現(xiàn)時(shí)直接把參數(shù)定義成long long模數(shù)傳給函數(shù)后再取一次余保證乘法不越界。注意筆試中所有可能進(jìn)行乘法的中間變量一律用long long。這是一個(gè)成本極低但收益極高的習(xí)慣很多人的題本來(lái)思路完全正確就是因?yàn)闆](méi)用long long爆int導(dǎo)致只過(guò)了一半用例。4.2 排序算法筆試中不一定直接考但經(jīng)常作為前置步驟“冒泡排序算法C”是熱詞里的常客但說(shuō)實(shí)話筆試編程題直接讓你手寫(xiě)冒泡排序的概率極低更多是把排序作為整個(gè)算法流程中的一環(huán)。比如題目要求“按優(yōu)先級(jí)從高到低輸出任務(wù)相同優(yōu)先級(jí)的按編號(hào)升序”這就需要在排序時(shí)寫(xiě)自定義比較函數(shù)。不過(guò)這不代表不用掌握排序算法的內(nèi)部實(shí)現(xiàn)。選擇題時(shí)?？寂判蛩惴ǖ姆€(wěn)定性、時(shí)間復(fù)雜度和適用場(chǎng)景。冒泡排序是穩(wěn)定排序選擇排序是不穩(wěn)定排序快速排序最壞情況下退化成O(n^2)歸并排序是穩(wěn)定且O(n log n)。這些結(jié)論要記牢。手寫(xiě)一份能過(guò)的快速排序代碼如下void quickSort(vectorint nums, int left, int right) { if (left right) return; int i left, j right; int pivot nums[(left right) / 2]; while (i j) { while (nums[i] pivot) i; while (nums[j] pivot) --j; if (i j) { swap(nums[i], nums[j]); i; --j; } } quickSort(nums, left, j); quickSort(nums, i, right); }筆試中如果你需要排序直接調(diào)用std::sort就好但在自定義比較時(shí)要注意嚴(yán)格弱排序。比較函數(shù)中如果出現(xiàn)相等元素返回true的情況會(huì)導(dǎo)致sort出現(xiàn)未定義行為程序可能直接崩潰。這是筆試中一個(gè)非常隱蔽的坑我之前就因?yàn)閷?xiě)了一個(gè)不滿足嚴(yán)格弱排序的比較函數(shù)在本地怎么跑都正常OJ上卻反復(fù)出問(wèn)題。4.3 單調(diào)棧吃透“下一個(gè)更大元素”這一整類題熱詞中“單調(diào)棧算法C”上榜說(shuō)明很多人在校招準(zhǔn)備階段被這類題卡過(guò)。單調(diào)棧的典型應(yīng)用場(chǎng)景是在一個(gè)數(shù)組中找每個(gè)元素左邊/右邊第一個(gè)比它大/小的元素。它能把這類問(wèn)題的復(fù)雜度從O(n^2)優(yōu)化到O(n)。核心思路很簡(jiǎn)單維護(hù)一個(gè)棧讓棧內(nèi)元素保持單調(diào)遞增或遞減。以“找每個(gè)元素右邊第一個(gè)比它大的元素”為例從左到右遍歷數(shù)組當(dāng)當(dāng)前元素大于棧頂元素時(shí)棧頂元素右側(cè)第一個(gè)比它大的元素就是當(dāng)前元素彈出并記錄答案。筆試中單調(diào)棧的變種很多但骨架基本一致。比如“柱狀圖中最大的矩形”、“接雨水”、“每日溫度”這些題背后都是單調(diào)棧。建議備考時(shí)把這幾個(gè)題各寫(xiě)一遍總結(jié)出模板vectorint nextGreater(vectorint nums) { int n nums.size(); vectorint ans(n, -1); stackint st; for (int i 0; i n; i) { while (!st.empty() nums[st.top()] nums[i]) { ans[st.top()] nums[i]; st.pop(); } st.push(i); } return ans; }要注意的是棧里存的是下標(biāo)而不是值因?yàn)槲覀儾粌H需要知道右側(cè)最大值還需要知道它的位置這在很多變種題里是拿分的關(guān)鍵。單調(diào)棧題目一旦理解了單調(diào)性維護(hù)的本質(zhì)其實(shí)不怎么需要死記硬背見(jiàn)到“下一個(gè)更大/更小”就反射性地想到單調(diào)棧。4.4 字符串與數(shù)組的初始化、讀取和轉(zhuǎn)換“C字符串?dāng)?shù)組初始化”、“C字符串轉(zhuǎn)數(shù)組”、“C string庫(kù)”這些搜索詞反映出很多人在字符串處理上基礎(chǔ)不牢。校招筆試的編程題里面字符串處理是當(dāng)之無(wú)愧的第一大題型基本上每場(chǎng)考試都會(huì)出現(xiàn)至少一道。先區(qū)分兩個(gè)基本概念C風(fēng)格字符串和std::string。C風(fēng)格字符串是以\0結(jié)尾的字符數(shù)組比如char str[] hello它的長(zhǎng)度是6而非5因?yàn)槟┪惨沤Y(jié)束符。std::string是C標(biāo)準(zhǔn)庫(kù)中的字符串類底層是一個(gè)動(dòng)態(tài)管理的字符數(shù)組用戶可以把它當(dāng)成一個(gè)封裝好的容器來(lái)用。題目中常見(jiàn)的需求是把一個(gè)字符串按分隔符拆成若干子串。C標(biāo)準(zhǔn)庫(kù)沒(méi)有現(xiàn)成的split函數(shù)所以筆試前建議自己封裝一個(gè)vectorstring split(const string s, char delim) { vectorstring res; string cur; for (char c : s) { if (c delim) { res.push_back(cur); cur.clear(); } else { cur.push_back(c); } } res.push_back(cur); // 不要忘了最后一截 return res; }這個(gè)函數(shù)雖然簡(jiǎn)單但筆試現(xiàn)場(chǎng)臨時(shí)寫(xiě)容易漏掉最后一截子串。用一個(gè)小時(shí)提前封裝好考試時(shí)直接調(diào)用心里會(huì)踏實(shí)很多。字符串轉(zhuǎn)數(shù)字可以用stoi、stol、stoll數(shù)字轉(zhuǎn)字符串用to_string。但有一個(gè)坑是stoi在字符串無(wú)法轉(zhuǎn)換時(shí)會(huì)拋出std::invalid_argument或std::out_of_range異常如果不捕獲就會(huì)導(dǎo)致程序崩潰OJ直接判RE。所以在筆試編程題中如果發(fā)現(xiàn)輸入數(shù)據(jù)可能不符合預(yù)期格式要么做好異常捕獲要么自己手動(dòng)逐字符轉(zhuǎn)換不要依賴stoi的默認(rèn)行為。C字符串?dāng)?shù)組初始化這塊也是一個(gè)經(jīng)典易錯(cuò)點(diǎn)。C11開(kāi)始支持花括號(hào)初始化數(shù)組vectorstring names {alice, bob, charlie};而C風(fēng)格字符串?dāng)?shù)組則是const char* names[] {alice, bob, charlie};這兩個(gè)寫(xiě)法在筆試選擇題中經(jīng)常出現(xiàn)。注意vector版本可以直接用names.size()獲取大小C風(fēng)格版本需要自己用sizeof(names)/sizeof(names[0])計(jì)算如果是在函數(shù)參數(shù)傳遞的場(chǎng)景sizeof會(huì)退化成指針大小這就是經(jīng)典筆試判斷題。5. 從筆試到實(shí)戰(zhàn)環(huán)境配置與代碼習(xí)慣5.1 本機(jī)搭建C開(kāi)發(fā)調(diào)試環(huán)境筆試準(zhǔn)備階段本地環(huán)境是否順手直接影響刷題效率。“vscode配置c/c環(huán)境”、“c/c構(gòu)建”、“microsoft visual c redistributable”這些熱詞反映了大家在環(huán)境搭建上的痛點(diǎn)。我自己的建議是如果是準(zhǔn)備校招筆試不要花太多時(shí)間折騰過(guò)于復(fù)雜的IDE用VS Code GCC/Clang就足夠。核心步驟就三步裝編譯器、裝VS Code擴(kuò)展、配置tasks.json和launch.json。編譯器這里有兩種選擇Windows上推薦MinGW-w64的g或微軟的MSVC。這兩種對(duì)應(yīng)了不同的工具鏈語(yǔ)法基本一致但鏈接庫(kù)的路徑、調(diào)試器的配置方式不同。如果你的代碼只在OJ上跑用MinGW-w64就夠它輕量、啟動(dòng)快、兼容性好。如果你還要在本地跑Windows原生圖形程序或者用微軟的調(diào)試工具那就裝Visual Studio Community。這里還要提醒一個(gè)基礎(chǔ)知識(shí)很多同學(xué)把“Microsoft Visual C Redistributable”和“Visual C編譯器”搞混。Redistributable只是運(yùn)行時(shí)庫(kù)它本身不包含編譯器裝它只是為了運(yùn)行依賴MSVC運(yùn)行時(shí)庫(kù)的程序。筆試環(huán)境一般不需要你安裝運(yùn)行庫(kù)但本地用MSVC編譯出來(lái)的程序換到別的機(jī)器上跑時(shí)目標(biāo)機(jī)器可能需要對(duì)應(yīng)版本的Redistributable。這個(gè)知識(shí)點(diǎn)雖然不直接計(jì)入筆試分?jǐn)?shù)但面試聊到項(xiàng)目部署時(shí)可能會(huì)被問(wèn)到。VS Code配置C環(huán)境時(shí)最常見(jiàn)的錯(cuò)誤是tasks.json中的command路徑寫(xiě)錯(cuò)或者args中的編譯選項(xiàng)不一致。一個(gè)可用的最小配置片段如下{ tasks: [ { label: C Build, type: process, command: C:/mingw64/bin/g.exe, args: [ -g, ${file}, -o, ${fileDirname}/${fileBasenameNoExtension}.exe ], group: build } ] }配置完成后按CtrlShiftB編譯按F5調(diào)試調(diào)試器用gdb。實(shí)際刷題時(shí)我習(xí)慣直接用終端命令編譯運(yùn)行其實(shí)很多時(shí)候比VS Code的圖形界面更快g -stdc17 -O2 -Wall main.cpp -o main ./main input.txt output.txt這里我強(qiáng)烈建議刷題時(shí)養(yǎng)成用輸入輸出文件重定向的習(xí)慣。筆試平臺(tái)的代碼要自己處理輸入輸出所以平時(shí)就習(xí)慣從input.txt讀數(shù)據(jù)、把結(jié)果寫(xiě)到output.txt上考場(chǎng)時(shí)你才不會(huì)對(duì)cin a和while (cin a)這種讀取方式感到陌生。5.2 筆試中容易踩的編譯與內(nèi)存坑編程題寫(xiě)對(duì)了算法卻因?yàn)榫幾g細(xì)節(jié)掛掉是最冤的。我總結(jié)了幾個(gè)每年都有很多人踩的坑。第一個(gè)是頭文件問(wèn)題。筆試現(xiàn)場(chǎng)很多時(shí)候允許直接使用#include bits/stdc.h因?yàn)榕？秃唾惔a網(wǎng)都支持。但有些本地編譯器不支持這個(gè)頭文件所以建議在本地也統(tǒng)一使用它來(lái)刷題或者干脆把所有常用的頭文件單獨(dú)列出來(lái)避免代碼里只有一個(gè)萬(wàn)能頭而對(duì)自己使用的容器來(lái)源一無(wú)所知。第二個(gè)是main函數(shù)的返回值類型。標(biāo)準(zhǔn)寫(xiě)法是int main()不要寫(xiě)成void main()這在MSVC下允許但GCC會(huì)報(bào)警告在校招OJ環(huán)境下可能直接編譯失敗。另一個(gè)相關(guān)坑是忘記return 0雖然C標(biāo)準(zhǔn)允許main函數(shù)省略return但為了穩(wěn)妥還是加上。第三個(gè)是數(shù)組越界。STL的vector在越界訪問(wèn)時(shí)不一定報(bào)錯(cuò)它會(huì)給出一個(gè)“未定義行為”可能什么也不發(fā)生也可能直接崩潰。筆試中更穩(wěn)妥的做法是用at()替代operator[]因?yàn)閍t()會(huì)做邊界檢查并拋出異常。不過(guò)at()的性能比[]略低筆試一般不會(huì)卡這個(gè)性能差距保正確性更重要。第四個(gè)是int溢出。前面提到過(guò)乘法、累加、求斐波那契第n項(xiàng)這類操作非常容易溢出int。C標(biāo)準(zhǔn)中int通常為32位范圍是-2147483648到2147483647一旦溢出就是未定義行為OJ上表現(xiàn)出來(lái)是“答案錯(cuò)誤”而不是“編譯錯(cuò)誤”非常難排查。所以凡是可能涉及超過(guò)10^9的中間值建議直接定義成long long。5.3 用“小游戲”練手把C寫(xiě)順熱詞里赫然列著“c小游戲”、“c好玩的代碼”、“c愛(ài)心代碼”這些搜索熱度其實(shí)暴露了一個(gè)事實(shí)很多人在學(xué)C時(shí)感覺(jué)枯燥需要一些有趣的小項(xiàng)目來(lái)維持動(dòng)力。我非常推薦用控制臺(tái)小游戲作為筆試之外的調(diào)劑性練習(xí)。比如猜數(shù)字、掃雷、貪吃蛇、五子棋、2048這些都適合用純C實(shí)現(xiàn)代碼量不大但是能覆蓋數(shù)組、循環(huán)、函數(shù)、隨機(jī)數(shù)、輸入輸出處理這些筆試選擇題也會(huì)考的基礎(chǔ)點(diǎn)。拿猜數(shù)字來(lái)說(shuō)核心邏輯就是生成一個(gè)隨機(jī)數(shù)然后循環(huán)讀取用戶輸入并給出反饋。這里有一個(gè)筆試也常考的點(diǎn)C里生成隨機(jī)數(shù)應(yīng)該使用std::mt19937而不是rand()因?yàn)閞and()的隨機(jī)質(zhì)量不高且受實(shí)現(xiàn)限制。雖然筆試選擇題不一定會(huì)考到引擎選擇但用最新方式寫(xiě)代碼是體現(xiàn)你專業(yè)度的重要細(xì)節(jié)。#include iostream #include random int main() { std::mt19937 gen(std::random_device{}()); std::uniform_int_distributionint dist(1, 100); int target dist(gen); int guess; while (std::cin guess guess ! target) { if (guess target) { std::cout too big std::endl; } else { std::cout too small std::endl; } } std::cout bingo std::endl; return 0; }這種小項(xiàng)目做三五個(gè)之后你對(duì)字符串輸入、循環(huán)退出、類型轉(zhuǎn)換的熟練度會(huì)大幅提升。很多同學(xué)刷筆試真題刷到麻木不妨換個(gè)思路去做點(diǎn)小游戲練完再回頭看筆試選擇題會(huì)發(fā)現(xiàn)很多“語(yǔ)法題”其實(shí)就是小項(xiàng)目里踩過(guò)的坑。6. 考的不僅是C更是復(fù)盤(pán)能力6.1 筆試后的復(fù)盤(pán)方法筆試結(jié)束并不意味著這個(gè)環(huán)節(jié)就翻篇了。不管考得好不好我都建議當(dāng)天晚上就把整個(gè)考試過(guò)程復(fù)盤(pán)一遍因?yàn)樵诳紙?chǎng)上你記憶最深、題目還原度最高。過(guò)了24小時(shí)再回憶很多細(xì)節(jié)就模糊了。復(fù)盤(pán)的第一步是記錄題目和考點(diǎn)。筆試不像面試通常不會(huì)公布題目平臺(tái)也看不到具體答案但你可以在考后憑記憶把題目大致還原出來(lái)并標(biāo)注每道題考察的知識(shí)點(diǎn)和你的卡點(diǎn)。這個(gè)過(guò)程很有價(jià)值因?yàn)樗鼛湍闾釤挸隽俗约旱谋∪醐h(huán)節(jié)是選擇題八股文不會(huì)還是編程題超時(shí)還是因?yàn)檩斎胼敵隼速M(fèi)了大量時(shí)間第二步是總結(jié)經(jīng)驗(yàn)教訓(xùn)。比如“選擇題花了50分鐘導(dǎo)致編程題只剩半小時(shí)”這類時(shí)間管理問(wèn)題就要在下一次筆試前刻意訓(xùn)練。如果你發(fā)現(xiàn)自己在“字符串轉(zhuǎn)數(shù)組”這種基礎(chǔ)操作上還需要現(xiàn)場(chǎng)查API那就說(shuō)明基礎(chǔ)不牢需要從熱詞里列出的那些高頻知識(shí)點(diǎn)開(kāi)始補(bǔ)。第三步是把每一道沒(méi)做出來(lái)的編程題重新在本地代碼庫(kù)里實(shí)現(xiàn)一遍并且貼上“網(wǎng)易2023筆試復(fù)盤(pán)”這種標(biāo)簽。等到你積累了10場(chǎng)筆試的復(fù)盤(pán)內(nèi)容后會(huì)發(fā)現(xiàn)自己對(duì)網(wǎng)易這類公司的出題風(fēng)格已經(jīng)形成了肌肉記憶。6.2 常見(jiàn)學(xué)習(xí)與面試問(wèn)題速查筆試和面試其實(shí)是高度關(guān)聯(lián)的筆試過(guò)了還有一面、二面每一面都可能在筆試內(nèi)容的基礎(chǔ)上繼續(xù)深挖。我在校招季經(jīng)常被問(wèn)到的幾個(gè)問(wèn)題順帶放在這里供大家自查?！盀槭裁磛ector比list查找快”這個(gè)問(wèn)題的標(biāo)準(zhǔn)回答模板是因?yàn)関ector底層是連續(xù)內(nèi)存支持O(1)隨機(jī)訪問(wèn)CPU緩存命中率高list底層是雙向鏈表只能順序訪問(wèn)且每個(gè)節(jié)點(diǎn)存儲(chǔ)額外的前后指針緩存局部性差。簡(jiǎn)單來(lái)說(shuō)就是“連續(xù)內(nèi)存緩存友好”。“shared_ptr和unique_ptr的使用場(chǎng)景如何選擇”答案是優(yōu)先用unique_ptr因?yàn)殚_(kāi)銷更低、語(yǔ)義更清晰只有需要多個(gè)對(duì)象共享所有權(quán)的時(shí)候才用shared_ptr。這里還可以接一個(gè)經(jīng)典反問(wèn)“shared_ptr的引用計(jì)數(shù)本身是線程安全的但指向的對(duì)象不是你如何理解”能說(shuō)出來(lái)這一點(diǎn)面試官通常會(huì)眼前一亮?！癱onstexpr和const的區(qū)別是什么”const是運(yùn)行時(shí)到編譯期的常量約束constexpr強(qiáng)制編譯期求值。const可以修飾變量、函數(shù)返回值constexpr則可以修飾變量和函數(shù)。筆試中經(jīng)常用constexpr int N 100; int arr[N];來(lái)考察編譯期確定數(shù)組大小的概念。這些問(wèn)題的共同點(diǎn)是它們不要求你背誦標(biāo)準(zhǔn)答案而是要求你用“為什么”的思路把知識(shí)點(diǎn)串起來(lái)。準(zhǔn)備筆試的時(shí)候如果時(shí)間緊張先圍繞這些高頻問(wèn)題做深度理解比盲目刷題有用得多。另外筆試中如果遇到完全不會(huì)的局面也有一個(gè)保底策略寫(xiě)暴力解法拿部分分。網(wǎng)易筆試的判題規(guī)則一般按測(cè)試點(diǎn)給分暴力法至少能通過(guò)小數(shù)據(jù)用例能拿20%到40%的分?jǐn)?shù)。不要覺(jué)得暴力解法丟人校招筆試的目標(biāo)是“分?jǐn)?shù)最大化”不是“寫(xiě)出最優(yōu)解”。還有一個(gè)小習(xí)慣值得養(yǎng)成每次寫(xiě)完代碼停下來(lái)花30秒讀一遍自己的代碼檢查有沒(méi)有拼寫(xiě)錯(cuò)誤、變量名不一致、缺少頭文件。在線OJ只能告訴你“答案錯(cuò)誤”或者“編譯錯(cuò)誤”它不會(huì)像本地編譯器那樣給出友好的錯(cuò)誤提示。考前把代碼檢查清單固定下來(lái)很多低級(jí)錯(cuò)誤是可以完全避免的。C校招筆試這條路上真正拉開(kāi)差距的不是智商而是準(zhǔn)備的系統(tǒng)性和復(fù)盤(pán)的習(xí)慣。把C底層的對(duì)象模型、內(nèi)存模型和STL原理理解到位把常見(jiàn)算法模板練成肌肉記憶再加上充分的考后復(fù)盤(pán)網(wǎng)易這樣的大廠筆試并不會(huì)是邁不過(guò)去的坎。希望這份拆解能讓你少走一些彎路節(jié)省下來(lái)的時(shí)間不妨繼續(xù)去刷一道自己不太熟的題。