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