好久沒(méi)在論壇里正經(jīng)寫(xiě)點(diǎn)技術(shù)復(fù)盤(pán)了。前兩天整理網(wǎng)盤(pán)資料翻到一份2019年?？湍M考試第四場(chǎng)四模的編程題合集順手從頭到尾重刷了一遍。老實(shí)說(shuō)雖然是幾年前的題但里面的考點(diǎn)設(shè)計(jì)——數(shù)組處理、動(dòng)態(tài)規(guī)劃、字符串操作、貪心模擬——放到今天的筆試場(chǎng)上依然是主力題型甚至有不少大廠面試還在用同款思路換皮出題。這篇文章我就把這套題集的題型布局、核心考點(diǎn)、每道典型題的完整解法和考場(chǎng)上的踩坑記錄都拆開(kāi)聊聊適合正在準(zhǔn)備校招筆試、想刷牛客?？碱}找手感或者打算系統(tǒng)過(guò)一遍基礎(chǔ)算法的朋友參考。先說(shuō)結(jié)論2019牛客四模的編程題難度放在當(dāng)年屬于中等偏上但今天看來(lái)它的價(jià)值不在題目本身而在它覆蓋的考點(diǎn)組合和邊界條件設(shè)計(jì)非常能暴露代碼習(xí)慣上的毛病。如果你只想刷難題這套題可能不夠刺激但如果你想在筆試前做一次全面自檢它比隨機(jī)刷幾十道題都高效。1. 題目布局與考點(diǎn)分布四模到底考了什么先給沒(méi)參加過(guò)?？湍？嫉呐笥芽破找幌卤尘?。牛客?？际桥？途W(wǎng)定期組織的在線模擬筆試題目風(fēng)格對(duì)標(biāo)當(dāng)年互聯(lián)網(wǎng)公司的校招筆試題通常包含選擇題加編程題兩部分。2019年這第四場(chǎng)編程題一共幾道我記得不太精確了但從合集內(nèi)容看核心集中在六類(lèi)字符串處理與模擬數(shù)組操作與雙指針排序與貪心動(dòng)態(tài)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)律推導(dǎo)圖論或搜索的簡(jiǎn)單應(yīng)用這個(gè)考點(diǎn)分布其實(shí)很有講究。你看現(xiàn)在的筆試題目很少會(huì)單獨(dú)考某一個(gè)算法基本都是兩個(gè)知識(shí)點(diǎn)糅在一起比如“排序雙指針”“字符串模擬哈希表”。2019年四模已經(jīng)開(kāi)始有這種趨勢(shì)題目本身不算特別難但如果你只會(huì)背模板遇到變體就會(huì)卡殼。四模還有一個(gè)特色它對(duì)輸入輸出的邊界處理要求很高。比如字符串題會(huì)混入空字符串和超長(zhǎng)字符串?dāng)?shù)組題會(huì)刻意在數(shù)據(jù)范圍上做文章逼著你去考慮時(shí)間復(fù)雜度和整數(shù)溢出。這些設(shè)計(jì)放在今天依然是筆試的核心考察點(diǎn)——機(jī)器判題時(shí)差一個(gè)邊界條件就是0分和滿分的區(qū)別。我當(dāng)時(shí)刷這套題最大的感受是它特別像大廠的“篩人題”——不考偏題怪題考的是你有沒(méi)有扎實(shí)的基礎(chǔ)編碼能力。如果你能在90分鐘內(nèi)穩(wěn)定AC三道題說(shuō)明你的基本功是過(guò)關(guān)的如果只能AC一道那大概率不是算法思路的問(wèn)題而是代碼實(shí)現(xiàn)不夠干凈。1.1 題目難度梯度設(shè)計(jì)每道編程題的難度并不是平鋪的而是有明顯的階梯感。我重刷時(shí)給這套題做了一個(gè)粗略的難度分層按照題目的數(shù)據(jù)規(guī)模和算法要求劃分難度層級(jí)對(duì)應(yīng)題量典型特征考點(diǎn)關(guān)鍵詞入門(mén)送分題1-2道題干短數(shù)據(jù)范圍小直接模擬即可字符串、基礎(chǔ)數(shù)學(xué)中等拉開(kāi)差距題2-3道需要優(yōu)化思路O(n^2)會(huì)超時(shí)雙指針、貪心、排序壓軸篩選題1道綜合性強(qiáng)狀態(tài)設(shè)計(jì)與邊界細(xì)節(jié)多動(dòng)態(tài)規(guī)劃、記憶化搜索這個(gè)梯度設(shè)計(jì)其實(shí)很科學(xué)。入門(mén)題保證大部分人能AC不至于上來(lái)就心態(tài)崩中等題開(kāi)始區(qū)分有沒(méi)有刷題量壓軸題則是給真正準(zhǔn)備充分的人準(zhǔn)備的。模考分?jǐn)?shù)出來(lái)之后你會(huì)發(fā)現(xiàn)分?jǐn)?shù)分布基本呈正態(tài)分布大部分人卡在中等題上。我建議刷這套題時(shí)不要只關(guān)注AC數(shù)量而是關(guān)注自己卡在哪一層。如果能穩(wěn)定AC中等題筆試已經(jīng)有了基本的競(jìng)爭(zhēng)力壓軸題如果半小時(shí)內(nèi)沒(méi)思路果斷放棄去檢查前面的題性價(jià)比更高。1.2 ?？蚈J的判題機(jī)制與應(yīng)對(duì)策略做題之前先花一分鐘說(shuō)說(shuō)?？偷呐蓄}機(jī)制因?yàn)楹芏嗳嗽诒镜豂DE用標(biāo)準(zhǔn)輸入輸出沒(méi)問(wèn)題一提交就報(bào)錯(cuò)大概率就是沒(méi)搞懂判題環(huán)境的規(guī)則。?？偷木幊填}接口一般分為兩種核心代碼模式和ACM模式。核心代碼模式是LeetCode那種你只需要實(shí)現(xiàn)一個(gè)函數(shù)ACM模式是你需要自己處理輸入輸出從標(biāo)準(zhǔn)流讀取數(shù)據(jù)再打印結(jié)果。2019年四模的編程題是純ACM模式這在當(dāng)年是主流現(xiàn)在很多大廠筆試也在用這一點(diǎn)來(lái)篩選候選人的工程能力。別小看輸入輸出處理我見(jiàn)過(guò)不少人思路完全正確結(jié)果因?yàn)樽x取多行輸入時(shí)漏了空行處理直接整題0分。應(yīng)對(duì)ACM模式有幾個(gè)基本建議用sys.stdin.read()一次性讀入所有數(shù)據(jù)再split效率比逐行input()高很多尤其是數(shù)據(jù)量大的場(chǎng)景。輸出時(shí)統(tǒng)一用列表收集結(jié)果再一次性打印不要每算一個(gè)結(jié)果就print一次否則幾百個(gè)case時(shí)容易拖慢整體速度。注意題目給出的輸入范圍如果數(shù)字可能很大Python可以用原生的int但如果是C選手要用long long。這些細(xì)節(jié)聽(tīng)起來(lái)瑣碎但恰恰是筆試中最容易扣分的點(diǎn)。刷2019四模這類(lèi)ACM模式題集正好可以幫你把這些習(xí)慣養(yǎng)成本能。2. 核心考點(diǎn)拆解每種題型背后的通用套路做完整套題后我最大的體會(huì)是編程題考的不是你會(huì)不會(huì)某個(gè)算法而是你能不能在一道題干看似復(fù)雜的題里快速識(shí)別出它底層在考什么。四模的題目雖然都是三年前的但考點(diǎn)設(shè)計(jì)得相當(dāng)?shù)湫头浅Ｖ档弥饌€(gè)拆解。下面挑四個(gè)出現(xiàn)頻率最高的方向詳細(xì)說(shuō)說(shuō)。2.1 字符串處理與模擬先拆解再編碼字符串處理題幾乎每場(chǎng)模考都會(huì)出現(xiàn)四模也不例外。這類(lèi)題看著簡(jiǎn)單實(shí)際上是最容易翻車(chē)的題型因?yàn)樽址牟僮魈`活了——反轉(zhuǎn)、切片、大小寫(xiě)轉(zhuǎn)換、去重、模式匹配每一種都有不同的坑。我重刷時(shí)遇到的一道字符串題大意是給定一個(gè)由大小寫(xiě)字母組成的字符串要求統(tǒng)計(jì)連續(xù)相同字符的最大長(zhǎng)度并輸出這個(gè)長(zhǎng)度和對(duì)應(yīng)字符。題目描述非常直白但測(cè)試用例里有一個(gè)小陷阱字符串可能全部由同一個(gè)字符組成也可能只有一個(gè)字符甚至可能是空字符串。解題思路其實(shí)很常規(guī)一次線性掃描就能搞定def solve(s: str) - str: if not s: return 0 max_len 1 cur_len 1 max_char s[0] for i in range(1, len(s)): if s[i] s[i - 1]: cur_len 1 else: if cur_len max_len: max_len cur_len max_char s[i - 1] cur_len 1 if cur_len max_len: max_len cur_len max_char s[-1] return f{max_char} {max_len} print(solve(input().strip()))這個(gè)解法的時(shí)間復(fù)雜度是O(n)空間復(fù)雜度O(1)已經(jīng)是這道題的最優(yōu)解。但真正讓我想強(qiáng)調(diào)的是編碼之外的步驟——先拆解再編碼。我看到很多人一上來(lái)就寫(xiě)循環(huán)寫(xiě)著寫(xiě)著漏掉了“連續(xù)”這個(gè)條件或者最后忘記更新最大字符。實(shí)際上字符串模擬題最穩(wěn)的做法是先理清幾個(gè)關(guān)鍵點(diǎn)輸入會(huì)不會(huì)有空格需不需要strip字符比較是區(qū)分大小寫(xiě)還是不區(qū)分統(tǒng)計(jì)條件是“連續(xù)相同”還是“全局出現(xiàn)次數(shù)”輸出格式要求是什么空格位置對(duì)不對(duì)這些點(diǎn)想清楚再動(dòng)手編碼速度反而更快。因?yàn)槟M題考的不是算法高深程度而是嚴(yán)謹(jǐn)程度。你有多少邊界case沒(méi)考慮到系統(tǒng)就有多少測(cè)試用例等著你。2.2 動(dòng)態(tài)規(guī)劃狀態(tài)定義是靈魂四模的壓軸題幾乎每次都會(huì)落到動(dòng)態(tài)規(guī)劃上2019年這場(chǎng)也不例外。我印象中有一道題是兩個(gè)序列的匹配相關(guān)具體形式類(lèi)似“給定兩個(gè)字符串你可以替換、插入、刪除字符求最少操作次數(shù)讓它們相等”——沒(méi)錯(cuò)就是編輯距離的變體。編輯距離之類(lèi)的題難點(diǎn)不在于知道要用DP而在于狀態(tài)定義和轉(zhuǎn)移方程能不能一次寫(xiě)對(duì)。我見(jiàn)過(guò)太多人的狀態(tài)定義是對(duì)的但初始化寫(xiě)錯(cuò)導(dǎo)致答案全偏。標(biāo)準(zhǔn)的編輯距離DP是這么定義的dp[i][j]表示字符串a(chǎn)的前i個(gè)字符轉(zhuǎn)換到字符串b的前j個(gè)字符所需的最少操作次數(shù)。初始化時(shí)dp[i][0] i表示把a(bǔ)的前i個(gè)字符全部刪除dp[0][j] j表示從空串插入j個(gè)字符。轉(zhuǎn)移時(shí)如果a[i-1] b[j-1]則dp[i][j] dp[i-1][j-1]否則取三種操作的最小值加一。寫(xiě)成代碼就是這樣def min_distance(a: str, b: str) - int: m, n len(a), len(b) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if a[i - 1] b[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) 1 return dp[m][n]這段代碼看起來(lái)簡(jiǎn)單真正筆試時(shí)你可能會(huì)慌尤其在有時(shí)間壓力的情況下。我的心得是DP題寫(xiě)不出來(lái)時(shí)先不要急著動(dòng)代碼用一個(gè)小例子在草稿紙上把dp表畫(huà)出來(lái)。比如aabc、byabd把每個(gè)格子填一遍轉(zhuǎn)移方程自然就清楚了。還有一個(gè)容易忽略的坑dp[i][j]的更新依賴于dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]所以遍歷順序必須是i從小到大、j從小到大。有人圖省事用一維數(shù)組做空間壓縮如果沒(méi)處理好更新順序結(jié)果全錯(cuò)。筆試時(shí)如果空間不緊張直接用二維數(shù)組最穩(wěn)。2.3 排序與貪心先證明再動(dòng)手排序與貪心是筆試中性價(jià)比最高的一類(lèi)題——你不需要掌握復(fù)雜的數(shù)據(jù)結(jié)構(gòu)關(guān)鍵是能看出來(lái)“這題要先排序再按某種規(guī)則貪心”。但正因?yàn)樗悸房雌饋?lái)簡(jiǎn)單很多人反而不重視證明導(dǎo)致用錯(cuò)排序規(guī)則。四模里有一道區(qū)間類(lèi)題目大概意思是給定若干個(gè)會(huì)議的開(kāi)始時(shí)間和結(jié)束時(shí)間問(wèn)最多能參加多少個(gè)不重疊的會(huì)議。這就是經(jīng)典的“會(huì)議室問(wèn)題”或者“活動(dòng)選擇問(wèn)題”。正確解法是按會(huì)議結(jié)束時(shí)間從早到晚排序然后依次選擇結(jié)束最早且與已選會(huì)議不沖突的會(huì)議。def max_meetings(times): times.sort(keylambda x: x[1]) count 0 last_end 0 for start, end in times: if start last_end: count 1 last_end end return count為什么按結(jié)束時(shí)間排序而不是按開(kāi)始時(shí)間這個(gè)問(wèn)題的答案就是貪心算法正確性的核心。我當(dāng)年上課時(shí)老師用反證法證明過(guò)在所有可行方案中如果一個(gè)方案的第一場(chǎng)會(huì)議不是結(jié)束時(shí)間最早的你把它替換成結(jié)束時(shí)間最早的會(huì)議后面的剩余時(shí)間只會(huì)更多不會(huì)變少。所以按結(jié)束時(shí)間排序的貪心策略一定是最優(yōu)的。筆試時(shí)你不需要寫(xiě)出嚴(yán)格的數(shù)學(xué)證明但至少要能在腦中過(guò)一遍這個(gè)邏輯避免出現(xiàn)“感覺(jué)對(duì)了但實(shí)際是錯(cuò)的”的情況。我見(jiàn)過(guò)不少人把這道題按會(huì)議時(shí)長(zhǎng)排序答案看起來(lái)也有道理但用例一跑就暴露了問(wèn)題。貪心題最怕的就是“看起來(lái)對(duì)”的偽正確解法。2.4 雙指針與哈希表時(shí)間復(fù)雜度的博弈2019年四模的數(shù)組題有一個(gè)很有意思的特點(diǎn)——大部分題目暴力O(n^2)都能過(guò)一部分測(cè)試用例但想拿滿分必須優(yōu)化到O(n)或者O(nlog n)。這背后其實(shí)模擬了真實(shí)筆試的判分邏輯小數(shù)據(jù)給部分分大數(shù)據(jù)才給滿分。所以你需要掌握的不僅是能跑的解法還得是會(huì)根據(jù)數(shù)據(jù)范圍選解法的能力。有一道題是“給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值找出數(shù)組中兩個(gè)數(shù)之和等于目標(biāo)值的下標(biāo)”。這是LeetCode第一題“兩數(shù)之和”的原題。暴力雙重循環(huán)當(dāng)然能做但數(shù)據(jù)一大就超時(shí)。標(biāo)準(zhǔn)解法是用哈希表記錄已經(jīng)遍歷過(guò)的數(shù)字及下標(biāo)每遍歷到一個(gè)新數(shù)字就檢查“目標(biāo)值減去當(dāng)前數(shù)字”是否已存在于哈希表中。def two_sum(nums, target): seen {} for i, num in enumerate(nums): diff target - num if diff in seen: return [seen[diff], i] seen[num] i return []這個(gè)解法的時(shí)間復(fù)雜度從O(n^2)降到了O(n)核心思想就是用哈希表的O(1)查找換取暴力的O(n)遍歷。這個(gè)思想在很多“找配對(duì)”“找目標(biāo)”類(lèi)題目中都通用比如三數(shù)之和、四數(shù)之和、以及一些變形的子數(shù)組問(wèn)題。雙指針的思路也類(lèi)似。很多數(shù)組題如果數(shù)據(jù)本身有序你就可以用兩個(gè)指針從兩端向中間逼近省掉一層循環(huán)。比如經(jīng)典的“容器盛水”“三數(shù)之和”都是雙指針的典型應(yīng)用。我刷四模時(shí)的一個(gè)重要心得是遇到數(shù)組題先看有沒(méi)有序再看能不能用雙指針實(shí)在不行再上哈希表或者排序輔助。3. 實(shí)戰(zhàn)解析三道典型題從讀題到AC全流程前面講了考點(diǎn)和通用套路現(xiàn)在挑三道比較有代表性的題目我把從讀題、構(gòu)思、編碼到提交的全過(guò)程拆解一遍。這個(gè)過(guò)程比單獨(dú)的答案更有參考價(jià)值——因?yàn)樗故玖擞龅揭坏滥吧}時(shí)腦子里應(yīng)該怎么想。3.1 字符串壓縮一道“簡(jiǎn)單但不送分”的題題目大意給定一個(gè)只包含字母的字符串按照“字符連續(xù)出現(xiàn)次數(shù)”的規(guī)則進(jìn)行壓縮。比如aabcccccaaa壓縮后是a2b1c5a3。如果壓縮后的字符串長(zhǎng)度不小于原字符串則返回原字符串。這道題的數(shù)據(jù)范圍不大不需要特殊優(yōu)化線性掃描一遍即可def compress(s: str) - str: if not s: return res [] count 1 for i in range(1, len(s)): if s[i] s[i - 1]: count 1 else: res.append(s[i - 1] str(count)) count 1 res.append(s[-1] str(count)) compressed .join(res) return compressed if len(compressed) len(s) else s這道題的關(guān)鍵點(diǎn)在于“壓縮后長(zhǎng)度不小于原字符串則返回原字符串”這個(gè)附加條件。很多人算完壓縮結(jié)果后直接輸出了忘了這個(gè)比較邏輯。筆試中這種“規(guī)則里藏著的小條件”是最容易丟分的讀題時(shí)必須用筆劃出來(lái)。另一個(gè)小細(xì)節(jié)是a壓不壓縮按規(guī)則a壓縮后就是a1長(zhǎng)度是2大于原長(zhǎng)度1所以應(yīng)該返回原串a(chǎn)。這個(gè)點(diǎn)不測(cè)一下很容易漏但機(jī)器判題一定會(huì)測(cè)。復(fù)盤(pán)心得這類(lèi)題不需要什么高級(jí)算法純粹考細(xì)心程度。我重刷時(shí)給自己規(guī)定拿到題先寫(xiě)出“輸出規(guī)則的三要素”再動(dòng)手——條件是什么、長(zhǎng)度怎么算、何時(shí)用原串。把這三句話寫(xiě)在草稿紙上后面寫(xiě)代碼就是翻譯題。3.2 最長(zhǎng)無(wú)重復(fù)字符子串滑動(dòng)窗口的經(jīng)典應(yīng)用這道題在四模里應(yīng)該是以“尋找給定字符串中最長(zhǎng)不含重復(fù)字符的子串長(zhǎng)度”出現(xiàn)的。原題來(lái)自LeetCode第3題是滑動(dòng)窗口的經(jīng)典入門(mén)題。思路是這樣的用兩個(gè)指針left和right維護(hù)一個(gè)窗口窗口內(nèi)保證沒(méi)有重復(fù)字符。right不斷向右擴(kuò)展每次遇到一個(gè)新字符如果它已經(jīng)在窗口中出現(xiàn)過(guò)就把left移動(dòng)到該字符上次出現(xiàn)位置的下一個(gè)位置同時(shí)更新該字符的最新位置。def length_of_longest_substring(s: str) - int: pos {} left 0 max_len 0 for right, ch in enumerate(s): if ch in pos and pos[ch] left: left pos[ch] 1 pos[ch] right max_len max(max_len, right - left 1) return max_len這段代碼看起來(lái)很簡(jiǎn)單但有幾個(gè)細(xì)節(jié)值得展開(kāi)。注意pos[ch] left這個(gè)判斷pos字典里存的雖然是字符最近一次出現(xiàn)的位置但如果這個(gè)位置已經(jīng)在窗口左邊界之外說(shuō)明當(dāng)前窗口里并沒(méi)有這個(gè)重復(fù)字符不需要移動(dòng)left。很多人省略了這個(gè)判斷結(jié)果遇到abba這種字符串就出錯(cuò)——right走到最后一個(gè)a時(shí)pos[a]還是0但left已經(jīng)變成2了如果再直接用left pos[a] 1就會(huì)把left從2退回1窗口內(nèi)就會(huì)出現(xiàn)重復(fù)字符。這種邊界細(xì)節(jié)就是我反復(fù)強(qiáng)調(diào)的“模板背下來(lái)了不一定能AC”的原因。算法框架誰(shuí)都會(huì)寫(xiě)但邊界條件才是拉開(kāi)差距的地方。復(fù)盤(pán)心得滑動(dòng)窗口類(lèi)的題目記住一個(gè)口訣右指針負(fù)責(zé)擴(kuò)張左指針負(fù)責(zé)收縮窗口內(nèi)容用固定規(guī)則維護(hù)。每次遞歸或迭代時(shí)先問(wèn)自己四個(gè)問(wèn)題窗口里存什么什么時(shí)候應(yīng)該擴(kuò)大窗口什么時(shí)候應(yīng)該收縮窗口用什么數(shù)據(jù)結(jié)構(gòu)存窗口內(nèi)容最方便把這四個(gè)問(wèn)題想明白這類(lèi)題基本就不會(huì)卡殼了。3.3 跳躍游戲貪心策略的優(yōu)雅之處四模壓軸區(qū)有一道“給定一個(gè)非負(fù)整數(shù)數(shù)組每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度判斷能否從第一個(gè)位置跳到最后一個(gè)位置”的題目。這是LeetCode第55題“跳躍游戲”的變體也是一道很經(jīng)典的貪心題。初見(jiàn)這道題的人很容易想到遞歸或DFS從位置0出發(fā)嘗試所有跳躍步數(shù)看能不能到達(dá)終點(diǎn)。這種解法在小規(guī)模數(shù)據(jù)下可行但一旦數(shù)組變長(zhǎng)分支數(shù)量呈指數(shù)級(jí)增長(zhǎng)直接超時(shí)。正確的做法是用貪心def can_jump(nums) - bool: max_reach 0 for i, num in enumerate(nums): if i max_reach: return False max_reach max(max_reach, i num) return True這個(gè)解法的核心思想是我們不關(guān)心具體走哪條路只關(guān)心從起點(diǎn)出發(fā)當(dāng)前能到達(dá)的最遠(yuǎn)位置是哪里。遍歷過(guò)程中如果當(dāng)前位置已經(jīng)超出了最遠(yuǎn)可達(dá)范圍說(shuō)明前面沒(méi)有任何一個(gè)位置能跳到這直接返回False。否則不斷更新最大可達(dá)位置直到遍歷結(jié)束。這個(gè)貪心策略的正確性在于所有可達(dá)位置是連續(xù)的。如果某個(gè)位置可達(dá)那么它之前的所有位置一定可達(dá)。所以只要維護(hù)一個(gè)最大可達(dá)邊界不需要準(zhǔn)確知道每條路徑的細(xì)節(jié)。這里有個(gè)容易混淆的點(diǎn)它和動(dòng)態(tài)規(guī)劃的區(qū)別。如果是問(wèn)“跳到終點(diǎn)最少需要多少步”那就需要用BFS或者貪心配合計(jì)數(shù)LeetCode第45題但本題只問(wèn)“能不能到”所以用一個(gè)變量就夠了。做算法題時(shí)讀完題先問(wèn)“求什么”是可行解問(wèn)題還是最優(yōu)解問(wèn)題這決定了用哪種策略。復(fù)盤(pán)心得貪心題最難的地方不是寫(xiě)代碼而是判斷“這題能不能用貪心”。我做四模時(shí)的一個(gè)經(jīng)驗(yàn)是——如果題干里出現(xiàn)“最多”“最少”“能否”這類(lèi)字眼先想想貪心能不能做能構(gòu)造出反例再考慮DP。很多同學(xué)一看到這類(lèi)題就條件反射式地開(kāi)DP數(shù)組其實(shí)浪費(fèi)了大把時(shí)間。4. 考場(chǎng)實(shí)戰(zhàn)策略從讀題到提交的時(shí)間管理有一套好的解題思路還不夠筆試畢竟是限時(shí)游戲時(shí)間分配和心態(tài)管理同樣重要。我根據(jù)自己的筆試經(jīng)驗(yàn)結(jié)合刷四模的感受整理了一套實(shí)操性很強(qiáng)的考場(chǎng)時(shí)間管理方案。4.1 前5分鐘全局掃題建立優(yōu)先級(jí)拿到題目的前5分鐘不要急著寫(xiě)代碼先快速把所有編程題都看一遍。每道題只花30秒掃一下題干和數(shù)據(jù)范圍然后在草稿紙上標(biāo)注兩個(gè)信息預(yù)估難度和數(shù)據(jù)規(guī)模。預(yù)估難度根據(jù)你熟悉的考點(diǎn)來(lái)判斷比如看到“字符串、模擬”標(biāo)記為低難度看到“動(dòng)態(tài)規(guī)劃”標(biāo)記為高難度數(shù)據(jù)規(guī)模用來(lái)決定要不要考慮優(yōu)化比如n 10^5的數(shù)組題基本可以排除O(n^2)暴力解法。掃完這遍之后快速確定做題順序。我的經(jīng)驗(yàn)是先做你最有把握、代碼量最小的題哪怕它不是最簡(jiǎn)單的——先拿分穩(wěn)住心態(tài)。再做“需要一點(diǎn)思考但方向明確”的題這類(lèi)題通常每題耗時(shí)10-15分鐘。最后啃最難的綜合題如果15分鐘內(nèi)沒(méi)有有效思路直接跳過(guò)把時(shí)間留給檢查。這個(gè)策略的核心原則是分?jǐn)?shù)最大化而不是“把所有題都做完”。筆試不是考試排名AC幾道題就是幾道題。死磕一道題導(dǎo)致后面所有題都白卷是最虧的。4.2 寫(xiě)代碼時(shí)保持“防御式編程”所謂“防御式編程”就是默認(rèn)輸入可能是臟的默認(rèn)邊界情況會(huì)發(fā)生默認(rèn)系統(tǒng)會(huì)有陷阱。具體到?？偷腁CM模式有幾個(gè)習(xí)慣建議刻進(jìn)肌肉記憶讀取字符串后用.strip()去掉末尾換行符除非你明確知道保留空格有意義。如果題目要求處理多組數(shù)據(jù)務(wù)必用while True加try包住讀取邏輯捕獲EOFError退出。數(shù)組的下標(biāo)越界比內(nèi)存溢出更常見(jiàn)凡是涉及i 1、i - 1、二維數(shù)組的行列索引一律先手動(dòng)模擬一遍臨界值。變量命名用能看懂的名字不要用a1、a2這種毫無(wú)信息量的縮寫(xiě)——考場(chǎng)上你肯定不想在Debug時(shí)還得回憶哪個(gè)變量是干嘛的。這些習(xí)慣不需要刻意練習(xí)刷題時(shí)每次提交前都自查一遍慢慢就會(huì)變成條件反射。4.3 多個(gè)測(cè)試用例不要只看樣例過(guò)了就提交我見(jiàn)過(guò)太多人寫(xiě)完全部樣例通過(guò)就立刻提交結(jié)果0分。這里說(shuō)的樣例指的是題面給的那一兩個(gè)輸入輸出示例。這些樣例通常很簡(jiǎn)單覆蓋不到邊界條件。正確的做法是在本地自己多構(gòu)造幾個(gè)邊界用例打一遍對(duì)于字符串題測(cè)試空字符串、單個(gè)字符、全部相同字符、全部不同字符。對(duì)于數(shù)組題測(cè)試數(shù)組長(zhǎng)度為1、所有數(shù)字相同、數(shù)組倒序、最大極值輸入。對(duì)于動(dòng)態(tài)規(guī)劃題在紙上手動(dòng)跑一個(gè)n3的簡(jiǎn)單用例驗(yàn)證狀態(tài)轉(zhuǎn)移表是否正確。這些額外測(cè)試每個(gè)大約花1-2分鐘但能幫你攔截掉一大半的提交錯(cuò)誤。我最后一次刷四模前給自己立了一個(gè)規(guī)定提交前至少造4個(gè)邊界用例跑一遍沒(méi)有邊界用例的提交統(tǒng)統(tǒng)視為“裸奔”。5. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄刷這套題的時(shí)候我也遇到了不少典型問(wèn)題這里挑幾個(gè)有代表性的記錄下來(lái)都是實(shí)戰(zhàn)中總結(jié)出來(lái)的不是教科書(shū)上那種“理論上可能發(fā)生”的問(wèn)題。5.1 本地運(yùn)行正確提交后卻異常這大概是?？蜕献畛Ｒ?jiàn)的求助帖標(biāo)題。原因通常有這么幾類(lèi)第一輸入輸出格式問(wèn)題。本地你可能直接用一個(gè)寫(xiě)死的字符串測(cè)試但線上輸入是多行或者末尾有空格、空行。解決辦法是統(tǒng)一使用sys.stdin.read()讀取處理或者保證每次input()后都調(diào)用.strip()。四模的字符串題經(jīng)常在輸入末尾藏一個(gè)\r\nWindows和Linux的換行差異也會(huì)導(dǎo)致類(lèi)似的詭異報(bào)錯(cuò)。第二全局變量污染。如果你用Python寫(xiě)多組測(cè)試用例且代碼中有全局變量或默認(rèn)參數(shù)很容易在多個(gè)用例之間互相影響。解決辦法是盡量把邏輯封裝到函數(shù)里每個(gè)測(cè)試用例調(diào)用一次函數(shù)確保局部變量不會(huì)殘留。第三遞歸深度超過(guò)限制。如果用了DFS類(lèi)解法且數(shù)據(jù)規(guī)模較大Python默認(rèn)的遞歸深度限制約1000層可能會(huì)觸發(fā)RecursionError。這通常需要改成迭代式或顯式棧寫(xiě)法。5.2 程序超時(shí)需要優(yōu)化?？偷呐蓄}系統(tǒng)有明確的時(shí)間限制一般是1到2秒。如果你的算法在大數(shù)據(jù)下超時(shí)優(yōu)先檢查這幾個(gè)點(diǎn)是不是用了Python內(nèi)置的list.index()在循環(huán)里查找元素這個(gè)操作是O(n)的循環(huán)套一遍就是O(n^2)。是不是用str做大量拼接操作Python的字符串不可變每次都會(huì)生成新對(duì)象。要改成list收集再用.join()。是不是能用雙指針或哈希表把O(n^2)降為O(n log n)或O(n)四模的數(shù)組題幾乎都是這個(gè)套路。我用一個(gè)實(shí)際例子說(shuō)明有一道數(shù)組題我最初用的是暴力兩重循環(huán)在小數(shù)據(jù)下測(cè)試通過(guò)但提交后提示超時(shí)。后來(lái)改成哈希表時(shí)間復(fù)雜度從O(n^2)降到O(n)成績(jī)直接從超時(shí)變AC。這個(gè)案例很典型——暴力解法值20分優(yōu)化算法值100分。5.3 答案錯(cuò)誤邊界條件和四舍五入答案錯(cuò)誤和超時(shí)相比更難排查因?yàn)橄到y(tǒng)不會(huì)告訴你錯(cuò)在哪個(gè)用例。我的排查順序是先檢查數(shù)值范圍題目給的n上限是10^9時(shí)用int沒(méi)問(wèn)題但如果你把中間結(jié)果存成浮點(diǎn)數(shù)就可能精度丟失。尤其是涉及除法、開(kāi)方時(shí)能用整數(shù)運(yùn)算就別用浮點(diǎn)。再檢查邊界下標(biāo)動(dòng)態(tài)規(guī)劃數(shù)組開(kāi)的是(n1)還是n遍歷時(shí)range(1, n1)還是range(n)差一個(gè)單位整個(gè)表就全錯(cuò)了。再檢查輸出格式要求輸出保留兩位小數(shù)你是用了format(x, .2f)還是直接print(x)要求輸出空格分隔你最后是不是多打印了一個(gè)空格這幾個(gè)點(diǎn)都是我自己踩過(guò)的坑。2019四模有一道題要求輸出浮點(diǎn)數(shù)保留兩位小數(shù)我第一次直接用print(avg)結(jié)果一直報(bào)錯(cuò)后來(lái)改成print(f{avg:.2f})才通過(guò)。這種格式問(wèn)題在本地完全看不出來(lái)只有提交時(shí)才會(huì)暴露。6. 從2019四模到未來(lái)的筆試這套題還能怎么用把題目本身講完之后我想聊聊這套三年前的?？碱}在今天復(fù)習(xí)過(guò)程中的定位。很多人覺(jué)得舊題就不值得刷這其實(shí)是個(gè)誤區(qū)。算法題的底層考點(diǎn)變化非常慢今天大廠筆試考的還是雙指針、動(dòng)態(tài)規(guī)劃、字符串處理、貪心這些核心內(nèi)容只是包裝更花哨了。2019四模的價(jià)值在于題型設(shè)計(jì)干凈、邊界條件清晰非常適合用來(lái)做基礎(chǔ)查漏補(bǔ)缺。如果你現(xiàn)在是準(zhǔn)備筆試的初期階段建議按這個(gè)順序使用這套題第一遍不限時(shí)間每道題獨(dú)立完成允許查資料但必須保證提交AC用來(lái)定位薄弱點(diǎn)。第二遍限時(shí)90分鐘模擬真實(shí)考場(chǎng)環(huán)境把做題順序和時(shí)間分配練成本能。第三遍只做錯(cuò)題和卡殼超過(guò)15分鐘的題每次重做前先復(fù)述思路再動(dòng)手寫(xiě)。這三次刷題法對(duì)任何題集都有效只是四模這套題的體量和難度特別適合作為中間的檢驗(yàn)工具。它不像新手題那么平淡也不像壓軸難題那么勸退。說(shuō)到Python如果你用Python刷題這里順便提一句很多人關(guān)心Python在OJ上性能不夠的問(wèn)題。我的體會(huì)是對(duì)于絕大多數(shù)筆試編程題Python的PyPy解釋器性能完全夠用關(guān)鍵在于不要寫(xiě)出低效的代碼——比如在循環(huán)里做字符串拼接、高頻調(diào)用print、無(wú)謂的深拷貝。數(shù)據(jù)結(jié)構(gòu)選對(duì)了Python一樣能AC絕大多數(shù)題目。最近的Python一級(jí)編程題考試題目也延續(xù)了這個(gè)趨勢(shì)重點(diǎn)考的依然是基礎(chǔ)語(yǔ)法、字符串處理和簡(jiǎn)單算法邏輯和這套四模題集的底層能力要求高度重合。所以如果你想從更基礎(chǔ)的語(yǔ)法題開(kāi)始熱手先練Python入門(mén)級(jí)別的編程題再上?？湍？歼@類(lèi)綜合題銜接是比較順暢的。7. 刷題之外的三個(gè)效率建議題目本身講了這么多最后再分享幾個(gè)關(guān)于刷題效率的通用建議這些不一定只針對(duì)四模但對(duì)所有編程題復(fù)習(xí)都有效。7.1 錯(cuò)題本比刷題量更重要我見(jiàn)過(guò)太多人刷了幾百道題但遇到原題還是不會(huì)做原因就是沒(méi)有整理錯(cuò)題本。整理錯(cuò)題不需要很復(fù)雜建立一張表格記錄三列就好題目名稱(chēng)、錯(cuò)誤原因、正確思路一句話。比如“兩數(shù)之和——沒(méi)用到哈希表暴力超時(shí)——用哈希表存遍歷過(guò)的數(shù)O(n)查互補(bǔ)數(shù)”。每次刷題前翻一遍錯(cuò)題本比重復(fù)刷一百道簡(jiǎn)單題高效得多。四模這套題我刷了三遍每遍用的錯(cuò)題本記錄都不太一樣。第一遍記的是“這個(gè)知識(shí)點(diǎn)沒(méi)學(xué)過(guò)”第二遍記的是“這個(gè)邊界條件沒(méi)想到”第三遍記的是“這道題5分鐘內(nèi)能否AC”。你會(huì)發(fā)現(xiàn)隨著復(fù)習(xí)深入錯(cuò)題本的內(nèi)容會(huì)從知識(shí)點(diǎn)轉(zhuǎn)向策略這本身就是水平提升的信號(hào)。7.2 寫(xiě)完代碼后花2分鐘口述思路這個(gè)方法聽(tīng)著有點(diǎn)玄學(xué)但我實(shí)測(cè)非常有效。每道題AC之后用手機(jī)錄音或者對(duì)著文檔口述一遍你的解題思路包括為什么選這個(gè)算法、狀態(tài)怎么定義、邊界怎么處理、復(fù)雜度是多少。口述的過(guò)程會(huì)迫使你把模糊的想法清晰化如果發(fā)現(xiàn)自己說(shuō)不清楚那說(shuō)明你并沒(méi)有真正理解這道題只是碰巧調(diào)通了。口述還有一個(gè)額外的作用面試前的模擬。技術(shù)面試經(jīng)常讓你現(xiàn)場(chǎng)講題如果平時(shí)沒(méi)有口述習(xí)慣面試時(shí)容易語(yǔ)無(wú)倫次。把口述當(dāng)成刷題的固定步驟之后面試講題會(huì)自然很多。7.3 每周一次限時(shí)自測(cè)找考場(chǎng)感覺(jué)刷題和考試是兩種不同的能力。有些人平時(shí)刷題很猛一到考試就緊張?jiān)蚴菍?duì)“限時(shí)”沒(méi)有概念。我的建議是每周選一套完整的?？碱}不一定是四模任何成套的題都可以按照真實(shí)筆試的時(shí)長(zhǎng)和規(guī)則進(jìn)行自測(cè)。限時(shí)自測(cè)時(shí)注意三點(diǎn)關(guān)閉IDE的自動(dòng)補(bǔ)全、不用搜索引擎、不中途暫停。這三個(gè)條件模擬的是考場(chǎng)上的真實(shí)約束。自測(cè)完不管分?jǐn)?shù)怎么樣對(duì)照錯(cuò)題本分析一次找出時(shí)間都花在哪了然后針對(duì)性地調(diào)整做題策略。比如你發(fā)現(xiàn)自己總在前兩道簡(jiǎn)單題上浪費(fèi)時(shí)間糾結(jié)“最優(yōu)解”那后面做題就要允許自己先用暴力解法拿分AC了再想優(yōu)化。寫(xiě)在最后的個(gè)人體會(huì)把2019年牛客四模這套題完整重刷一遍之后我的感受挺深的。三年前的題目今天看起來(lái)依然很扎實(shí)——它沒(méi)有為了難而難每一道題都踩在基礎(chǔ)算法和工程習(xí)慣的交匯點(diǎn)上這恰恰是筆試最看重的東西。我當(dāng)年第一次刷這套題的時(shí)候大概只AC了兩道很多現(xiàn)在一眼能看出套路的題目當(dāng)時(shí)連門(mén)都摸不著?，F(xiàn)在能比較輕松地解出來(lái)靠的不是什么天賦就是日復(fù)一日地刷題、記錯(cuò)題、復(fù)盤(pán)思路。如果你現(xiàn)在正處于刷題瓶頸期覺(jué)得怎么練都提不高我的建議是別急著刷更多新題回頭把做過(guò)的舊題尤其是?？碱}重新做一遍。你會(huì)發(fā)現(xiàn)很多當(dāng)時(shí)“AC靠運(yùn)氣”的題現(xiàn)在能說(shuō)清楚每一步為什么這么寫(xiě)也能發(fā)現(xiàn)一些當(dāng)時(shí)“AC了就過(guò)了”的題其實(shí)還隱藏著更優(yōu)的解法或者沒(méi)考慮到的邊界。這個(gè)過(guò)程比刷十道新題都更鍛煉人。最后再分享一個(gè)小技巧做題的時(shí)候把每道題當(dāng)作一次“教導(dǎo)別人”的機(jī)會(huì)寫(xiě)完代碼后假裝有人問(wèn)你“為什么這里要加這個(gè)條件”然后自己回答。這個(gè)簡(jiǎn)單的問(wèn)答練習(xí)能幫你把很多模棱兩可的理解補(bǔ)扎實(shí)也是我從刷這套四模題里收獲最大的一件事。