东华大学考研复试机试：动态规划、图论与字符串处理实战

1. 项目背景与核心价值

作为一名计算机专业考研过来人，我深知东华大学复试机试环节的重要性。OJ（Online 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 322）

def 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

易错点分析：

1. 初始值设置：除dp[0]外都应初始化为极大值
2. 遍历顺序：必须先遍历硬币再遍历金额，避免排列重复计数
3. 返回值判断：注意无法兑换时的-1处理

2.1.3 编辑距离（LeetCode 72）

def 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(E+VlogV)（邻接表+优先队列）
• 适用场景：边权非负的有向/无向图

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 [] # 判断是否有环

关键点：

1. 入度统计：必须准确记录每个节点的前置依赖数
2. 队列维护：始终处理当前入度为0的节点
3. 环检测：结果列表长度不足说明存在环

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 -1

LPS数组理解技巧：

• 每个位置的值表示当前子串的最长相同前后缀长度
• 匹配失败时，利用LPS数组跳过已匹配部分

2.3.2 马拉车算法（Manacher）

def 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]

算法精髓：

1. 奇偶统一处理：插入特殊字符使所有回文都变为奇数长度
2. 对称性利用：通过已知回文信息减少重复计算
3. 最右边界维护：动态扩大搜索范围

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:ptr+n])) ptr += n # 调用解题函数 result = solve(data) print(result) if __name__ == "__main__": main()

输入处理要点：

• 使用sys.stdin.read()批量读取提高效率
• 维护指针(ptr)避免反复切割列表
• 封装解题逻辑到独立函数方便调试

3.3 考场策略

1. 5分钟读题：标注输入范围、特殊边界条件
2. 10分钟构思：在草稿纸画出状态转移方程或算法流程图
3. 20分钟编码：先写核心逻辑再补全IO处理
4. 5分钟测试：构造边界用例（空输入、极值等）

4. 高频考点延伸训练

4.1 动态规划变种题

• 环形子数组最大和（LeetCode 918）
• 股票买卖系列（含冷冻期、手续费等变种）
• 背包问题求具体方案

4.2 图论进阶题目

• 网络延迟时间（Dijkstra应用）
• 课程表II（拓扑排序输出序列）
• 连接所有城市的最低成本（最小生成树）

4.3 字符串难题精选

• 单词拆分II（DFS+记忆化）
• 不同的子序列（DP计数）
• 回文对（哈希优化）

重要提醒：东华OJ近年新增了系统设计题型，建议额外准备LRU缓存、哈希表实现等面向对象编程题。我在临考前两周每天加练1道系统设计题，复试时恰好遇到类似题目，这种前瞻性训练非常值得投入。