1. 项目背景与核心价值作为一名计算机专业考研过来人我深知东华大学复试机试环节的重要性。OJOnline Judge在线编程平台是检验考生算法能力和编码熟练度的关键战场而每日3题打卡正是我去年备战期间总结出的高效训练法。这个系列记录了我从第22天到第24天的实战复盘包含题目解析、代码优化和易错点分析特别适合正在备战东华复试的学弟学妹参考。提示东华OJ常考知识点集中在动态规划、图论和字符串处理每日保持3题的训练强度既能巩固基础又能提升临场应变能力。2. 三日题目全景解析2.1 第22天经典动态规划三连2.1.1 最大子序列和LeetCode 53改编# 标准DP解法 def maxSubArray(nums): dp [0] * len(nums) dp[0] nums[0] for i in range(1, len(nums)): dp[i] max(nums[i], dp[i-1] nums[i]) return max(dp) # 空间优化版面试推荐 def maxSubArray_optimized(nums): pre max_sum nums[0] for num in nums[1:]: pre max(num, pre num) max_sum max(max_sum, pre) return max_sum避坑指南边界条件输入为空数组时需特殊处理初始化陷阱dp[0]必须初始化为nums[0]而非0优化技巧发现状态转移只依赖前一个值时立即考虑滚动数组2.1.2 零钱兑换LeetCode 322def 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易错点分析初始值设置除dp[0]外都应初始化为极大值遍历顺序必须先遍历硬币再遍历金额避免排列重复计数返回值判断注意无法兑换时的-1处理2.1.3 编辑距离LeetCode 72def minDistance(word1, word2): m, n len(word1), len(word2) 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 word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]状态转移方程精讲相等时直接继承左上方值无需操作不等时取增删改三种操作的最小值1初始化第一行/列对应空字符串的转换步数2.2 第23天图论专题突破2.2.1 Dijkstra算法实现邻接矩阵版import heapq def dijkstra(graph, start): n len(graph) dist [float(inf)] * n dist[start] 0 heap [(0, start)] while heap: d, u heapq.heappop(heap) if d dist[u]: continue for v in range(n): if graph[u][v] 0: # 存在边 new_dist dist[u] graph[u][v] if new_dist dist[v]: dist[v] new_dist heapq.heappush(heap, (new_dist, v)) return dist复杂度分析时间复杂度O(V^2)邻接矩阵或 O(EVlogV)邻接表优先队列适用场景边权非负的有向/无向图2.2.2 拓扑排序Kahn算法from collections import deque def topological_sort(vertices, edges): in_degree {v: 0 for v in vertices} adj {v: [] for v in vertices} for u, v in edges: adj[u].append(v) in_degree[v] 1 queue deque([v for v in vertices if in_degree[v] 0]) result [] while queue: u queue.popleft() result.append(u) for v in adj[u]: in_degree[v] - 1 if in_degree[v] 0: queue.append(v) return result if len(result) len(vertices) else [] # 判断是否有环关键点入度统计必须准确记录每个节点的前置依赖数队列维护始终处理当前入度为0的节点环检测结果列表长度不足说明存在环2.2.3 并查集实现路径压缩按秩合并class UnionFind: def __init__(self, size): self.parent list(range(size)) self.rank [0] * size def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路径压缩 return self.parent[x] def union(self, x, y): x_root self.find(x) y_root self.find(y) if x_root y_root: return # 按秩合并 if self.rank[x_root] self.rank[y_root]: self.parent[x_root] y_root else: self.parent[y_root] x_root if self.rank[x_root] self.rank[y_root]: self.rank[x_root] 1优化原理路径压缩使查询操作均摊时间复杂度接近O(1)按秩合并避免树过高影响查询效率2.3 第24天字符串处理进阶2.3.1 KMP算法实现def build_lps(pattern): lps [0] * len(pattern) length 0 i 1 while i len(pattern): if pattern[i] pattern[length]: length 1 lps[i] length i 1 else: if length ! 0: length lps[length - 1] else: lps[i] 0 i 1 return lps def kmp_search(text, pattern): lps build_lps(pattern) i j 0 while i len(text): if text[i] pattern[j]: i 1 j 1 if j len(pattern): return i - j else: if j ! 0: j lps[j - 1] else: i 1 return -1LPS数组理解技巧每个位置的值表示当前子串的最长相同前后缀长度匹配失败时利用LPS数组跳过已匹配部分2.3.2 马拉车算法Manacherdef longest_palindrome(s): # 预处理字符串 t ^# #.join(s) #$ n len(t) p [0] * n center right 0 for i in range(1, n - 1): # 利用对称性快速初始化 if i right: mirror 2 * center - i p[i] min(right - i, p[mirror]) # 中心扩展 while t[i p[i] 1] t[i - p[i] - 1]: p[i] 1 # 更新最右边界 if i p[i] right: center i right i p[i] max_len max(p) center_index p.index(max_len) start (center_index - max_len) // 2 return s[start: start max_len]算法精髓奇偶统一处理插入特殊字符使所有回文都变为奇数长度对称性利用通过已知回文信息减少重复计算最右边界维护动态扩大搜索范围2.3.3 正则表达式引擎简化版def is_match(text, pattern): memo {} def dp(i, j): if (i, j) not in memo: if j len(pattern): ans i len(text) else: first_match i len(text) and pattern[j] in {text[i], .} if j 1 len(pattern) and pattern[j 1] *: ans dp(i, j 2) or (first_match and dp(i 1, j)) else: ans first_match and dp(i 1, j 1) memo[(i, j)] ans return memo[(i, j)] return dp(0, 0)递归转DP要点状态定义(文本位置模式位置)的匹配情况星号处理匹配0次或多次的两种分支记忆化存储避免重复计算3. 复试备战方法论3.1 每日训练节奏把控早间1.5h研究昨日错题理解最优解法午后2h限时完成新题3题/90分钟晚间1h代码重构与复杂度分析3.2 调试技巧分享# 在OJ平台调试的常用模板 import sys def main(): input sys.stdin.read().split() ptr 0 # 处理输入数据 while ptr len(input): n int(input[ptr]) ptr 1 data list(map(int, input[ptr:ptrn])) ptr n # 调用解题函数 result solve(data) print(result) if __name__ __main__: main()输入处理要点使用sys.stdin.read()批量读取提高效率维护指针(ptr)避免反复切割列表封装解题逻辑到独立函数方便调试3.3 考场策略5分钟读题标注输入范围、特殊边界条件10分钟构思在草稿纸画出状态转移方程或算法流程图20分钟编码先写核心逻辑再补全IO处理5分钟测试构造边界用例空输入、极值等4. 高频考点延伸训练4.1 动态规划变种题环形子数组最大和LeetCode 918股票买卖系列含冷冻期、手续费等变种背包问题求具体方案4.2 图论进阶题目网络延迟时间Dijkstra应用课程表II拓扑排序输出序列连接所有城市的最低成本最小生成树4.3 字符串难题精选单词拆分IIDFS记忆化不同的子序列DP计数回文对哈希优化重要提醒东华OJ近年新增了系统设计题型建议额外准备LRU缓存、哈希表实现等面向对象编程题。我在临考前两周每天加练1道系统设计题复试时恰好遇到类似题目这种前瞻性训练非常值得投入。