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