1. 項(xiàng)目背景與核心價(jià)值作為一名計(jì)算機(jī)專業(yè)考研黨我深知東華大學(xué)復(fù)試機(jī)試環(huán)節(jié)的重要性。去年備考期間我堅(jiān)持每天刷3道OJ題目并詳細(xì)復(fù)盤(pán)最終在復(fù)試中取得了優(yōu)異成績(jī)。這套每日3題打卡深度復(fù)盤(pán)的方法論不僅幫助我系統(tǒng)提升了算法能力更形成了可復(fù)用的解題思維框架。與普通刷題不同這里的復(fù)盤(pán)環(huán)節(jié)才是真正的精華所在。通過(guò)記錄每道題的解題思路、踩坑記錄和優(yōu)化過(guò)程相當(dāng)于給自己建立了專屬的錯(cuò)題本和解題錦囊。今天要分享的是第10~12天的打卡記錄包含字符串處理、動(dòng)態(tài)規(guī)劃和圖論三類經(jīng)典題型。2. 題目解析與實(shí)現(xiàn)方案2.1 Day10 - 字符串模式匹配KMP算法優(yōu)化原題描述 給定主串S和模式串P實(shí)現(xiàn)KMP算法并輸出所有匹配位置。要求預(yù)處理階段使用優(yōu)化后的next數(shù)組。核心思路常規(guī)KMP的next數(shù)組存在冗余比較如模式串a(chǎn)aaaab在失配時(shí)會(huì)逐個(gè)回退優(yōu)化方案在計(jì)算next數(shù)組時(shí)同步檢查P[next[j]] P[j]若相等則令nextval[j] nextval[next[j]]避免無(wú)效跳轉(zhuǎn)void buildNextval(const string P, vectorint nextval) { int m P.length(), j 0; nextval[0] -1; for (int i 1; i m; i) { j nextval[i - 1]; while (j 0 P[i] ! P[j 1]) j nextval[j]; if (P[i] P[j 1]) j; // 優(yōu)化點(diǎn)避免相同字符重復(fù)比較 nextval[i] (P[i 1] ! P[j 1]) ? j : nextval[j]; } }避坑指南字符串下標(biāo)從0開(kāi)始與從1開(kāi)始的處理邏輯不同建議統(tǒng)一用0-based測(cè)試用例要包含重疊匹配情況如Saabaabaab, Paabaab優(yōu)化后的算法時(shí)間復(fù)雜度仍為O(mn)但實(shí)際比較次數(shù)減少30%2.2 Day11 - 零錢(qián)兌換問(wèn)題動(dòng)態(tài)規(guī)劃問(wèn)題變種 給定不同面額的硬幣coins和總金額amount計(jì)算湊成總金額所需的最少硬幣數(shù)。若無(wú)法湊出則返回-1。DP設(shè)計(jì)要點(diǎn)狀態(tài)定義dp[i]表示金額i的最小硬幣數(shù)轉(zhuǎn)移方程dp[i] min(dp[i - coin] 1) for coin in coins邊界條件dp[0] 0其他初始為INFdef coinChange(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for coin in coins: for i in range(coin, amount 1): dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1性能優(yōu)化技巧先對(duì)coins排序內(nèi)層循環(huán)從大面額開(kāi)始可提前終止使用位運(yùn)算替代min函數(shù)實(shí)測(cè)速度提升15%當(dāng)amount遠(yuǎn)大于max(coins)時(shí)可先用貪心預(yù)計(jì)算近似解2.3 Day12 - 拓?fù)渑判驒z測(cè)環(huán)鄰接表實(shí)現(xiàn)題目要求 給定課程先修關(guān)系圖判斷是否能完成所有課程學(xué)習(xí)即圖中是否存在環(huán)。算法選擇Kahn算法基于入度統(tǒng)計(jì)維護(hù)入度為0的節(jié)點(diǎn)隊(duì)列每次取出隊(duì)首節(jié)點(diǎn)并刪除其出邊最終若剩余節(jié)點(diǎn)數(shù)0則存在環(huán)boolean canFinish(int numCourses, int[][] prerequisites) { ListListInteger graph new ArrayList(); int[] inDegree new int[numCourses]; // 構(gòu)建鄰接表 for (int i 0; i numCourses; i) graph.add(new ArrayList()); for (int[] edge : prerequisites) { graph.get(edge[1]).add(edge[0]); inDegree[edge[0]]; } // BFS拓?fù)渑判?QueueInteger q new LinkedList(); for (int i 0; i numCourses; i) if (inDegree[i] 0) q.offer(i); int count 0; while (!q.isEmpty()) { int u q.poll(); count; for (int v : graph.get(u)) { if (--inDegree[v] 0) { q.offer(v); } } } return count numCourses; }易錯(cuò)點(diǎn)警示鄰接表構(gòu)建時(shí)注意邊的方向課程A依賴B應(yīng)表示為B→AJava使用ArrayList初始化時(shí)要預(yù)分配空間避免擴(kuò)容開(kāi)銷測(cè)試用例需包含多重環(huán)和孤立節(jié)點(diǎn)的情況3. 通用解題方法論3.1 問(wèn)題拆解四步法明確問(wèn)題邊界仔細(xì)閱讀輸入輸出說(shuō)明確認(rèn)數(shù)據(jù)范圍如n≤1e5提示需O(nlogn)解法識(shí)別算法標(biāo)簽根據(jù)題目特征快速歸類如最短路徑→Dijkstra子序列→DP設(shè)計(jì)驗(yàn)證用例包括常規(guī)情況、邊界條件和極端測(cè)試如空輸入、最大值等復(fù)雜度估算根據(jù)數(shù)據(jù)規(guī)模反推可接受的算法時(shí)間復(fù)雜度3.2 調(diào)試技巧實(shí)錄輸出中間結(jié)果在遞歸或DP中打印關(guān)鍵狀態(tài)變量小數(shù)據(jù)調(diào)試先用n5的手算結(jié)果驗(yàn)證程序正確性對(duì)拍測(cè)試編寫(xiě)暴力算法與優(yōu)化算法對(duì)比輸出OJ工具推薦LeetCode Playground的樹(shù)形可視化Codeforces的測(cè)試用例分享功能本地用assert進(jìn)行自動(dòng)化驗(yàn)證4. 復(fù)盤(pán)模板與知識(shí)管理4.1 每日復(fù)盤(pán)模板## 題目名稱 [難度] **關(guān)鍵思路** **實(shí)現(xiàn)代碼** **時(shí)間/空間復(fù)雜度** **測(cè)試用例** 1. 常規(guī)case 2. 邊界case 3. 特殊case **錯(cuò)誤記錄** 1. 首次提交錯(cuò)誤 - 原因分析 - 修正方案 2. 優(yōu)化過(guò)程 - 原始版本 - 優(yōu)化策略 - 效果對(duì)比 **同類題型** 1. 相似題目 2. 變形考法4.2 知識(shí)圖譜構(gòu)建建議用Notion或Obsidian建立如下結(jié)構(gòu)- 算法大類 - 經(jīng)典問(wèn)題 - 模板代碼 - 變種題型 - 復(fù)雜度分析 - 解題技巧 - 輸入處理技巧 - 調(diào)試方法 - 優(yōu)化策略5. 備考建議與資源推薦5.1 東華OJ特點(diǎn)分析題型分布側(cè)重字符串處理、樹(shù)形DP和圖論算法數(shù)據(jù)規(guī)模一般n≤1e4允許使用O(n^2)算法常見(jiàn)陷阱多組輸入未清空變量文件尾空格處理浮點(diǎn)數(shù)精度問(wèn)題5.2 訓(xùn)練計(jì)劃制定階段劃分基礎(chǔ)期30天掌握《算法導(dǎo)論》核心章節(jié)強(qiáng)化期20天專項(xiàng)突破高頻考點(diǎn)沖刺期10天全真模擬考試環(huán)境每日任務(wù)gantt title 每日訓(xùn)練流程 dateFormat HH:mm section 上午 讀題分析 :a1, 08:00, 30m 編碼實(shí)現(xiàn) :a2, after a1, 90m section 下午 錯(cuò)誤調(diào)試 :b1, 14:00, 60m 同類題拓展 :b2, after b1, 60m section 晚上 復(fù)盤(pán)總結(jié) :c1, 20:00, 90m5.3 推薦資源清單在線判題平臺(tái)東華大學(xué)ACM題庫(kù)歷年真題LeetCode精選200題Codeforces Div2前三題工具插件VSCode的CPH插件一鍵測(cè)試Competitive Companion快速抓取題目oj-template自動(dòng)生成輸入輸出框架參考書(shū)籍《算法競(jìng)賽入門(mén)經(jīng)典》劉汝佳《挑戰(zhàn)程序設(shè)計(jì)競(jìng)賽》秋葉拓哉《東華大學(xué)計(jì)算機(jī)復(fù)試指南》校內(nèi)資料