1. 项目背景与目标

最近在准备东华大学计算机专业的研究生复试，发现他们的在线评测系统（OJ）题目很有特点。特别是第12套题，第一次做的时候踩了不少坑，这次二刷特意做了详细复盘。这套题主要考察数据结构与算法的实际应用能力，涉及字符串处理、动态规划等核心知识点。

作为计算机专业考研复试的必考内容，OJ题目的熟练度直接影响复试成绩。通过系统性地整理错题和优化解法，不仅能提升编程能力，还能培养解决工程问题的思维模式。下面我就把这套题的解题思路、常见陷阱和优化技巧完整分享出来。

2. 题目分析与解题思路

2.1 第一题：字符串模式匹配

这道题要求实现带通配符的字符串匹配算法。与标准KMP算法不同，题目中的通配符"?"可以匹配任意单个字符，"*"可以匹配任意长度字符串（包括空串）。

def isMatch(s: str, p: str) -> bool: m, n = len(s), len(p) dp = [[False]*(n+1) for _ in range(m+1)] dp[0][0] = True for j in range(1, n+1): if p[j-1] == '*': dp[0][j] = dp[0][j-1] for i in range(1, m+1): for j in range(1, n+1): if p[j-1] == s[i-1] or p[j-1] == '?': dp[i][j] = dp[i-1][j-1] elif p[j-1] == '*': dp[i][j] = dp[i][j-1] or dp[i-1][j] return dp[m][n]

注意：初始化时dp[0][0]=True表示两个空字符串匹配，对于模式串开头的多个'*'，需要特殊处理它们可以匹配空字符串的情况。

2.2 第二题：二叉树路径求和

题目给出一个二叉树，要求找出所有从根节点到叶子节点的路径，使得路径上节点值之和等于给定目标值。这是典型的DFS应用场景。

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def pathSum(root: TreeNode, target: int) -> List[List[int]]: res = [] def dfs(node, path, remain): if not node: return path.append(node.val) if not node.left and not node.right and remain == node.val: res.append(list(path)) dfs(node.left, path, remain - node.val) dfs(node.right, path, remain - node.val) path.pop() dfs(root, [], target) return res

常见错误：

1. 忘记在递归返回前弹出当前节点（path.pop()）
2. 没有判断叶子节点条件（not node.left and not node.right）
3. 直接添加path到res而没有创建新列表（会导致后续修改影响结果）

3. 动态规划专题

3.1 最长递增子序列

这道题要求找出数组中最长的严格递增子序列的长度。经典解法时间复杂度是O(n²)，但可以用二分查找优化到O(nlogn)。

def lengthOfLIS(nums: List[int]) -> int: tails = [] for num in nums: left, right = 0, len(tails) while left < right: mid = (left + right) // 2 if tails[mid] < num: left = mid + 1 else: right = mid if left == len(tails): tails.append(num) else: tails[left] = num return len(tails)

优化思路：

1. tails数组维护当前长度的最小末尾值
2. 对于每个新元素，用二分查找确定它在tails中的位置
3. 要么扩展tails数组，要么替换某个位置的元素

3.2 零钱兑换问题

给定不同面额的硬币和一个总金额，计算可以凑成总金额的最少硬币数。这是典型的完全背包问题。

def coinChange(coins: List[int], amount: int) -> int: 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]=0）
2. 内循环从coin开始，避免数组越界
3. 最后需要判断是否有解（是否仍为无穷大）

4. 图论问题解析

4.1 课程安排问题

典型的拓扑排序应用，判断课程安排是否存在循环依赖。可以用Kahn算法或DFS实现。

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool: graph = [[] for _ in range(numCourses)] in_degree = [0] * numCourses for course, pre in prerequisites: graph[pre].append(course) in_degree[course] += 1 queue = [i for i in range(numCourses) if in_degree[i] == 0] count = 0 while queue: node = queue.pop() count += 1 for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) return count == numCourses

关键步骤：

1. 构建邻接表和入度数组
2. 初始化队列（入度为0的节点）
3. 不断移除队列中的节点并更新邻居的入度
4. 最后检查是否所有节点都被处理

4.2 岛屿数量问题

给定二维网格，计算其中岛屿的数量。经典连通分量问题，DFS/BFS均可。

def numIslands(grid: List[List[str]]) -> int: if not grid: return 0 rows, cols = len(grid), len(grid[0]) count = 0 def dfs(r, c): if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1': return grid[r][c] = '0' # 标记为已访问 dfs(r+1, c) dfs(r-1, c) dfs(r, c+1) dfs(r, c-1) for r in range(rows): for c in range(cols): if grid[r][c] == '1': count += 1 dfs(r, c) return count

优化技巧：

1. 直接在原数组上标记访问过的位置（节省空间）
2. 四个方向的DFS可以用循环简化
3. 遇到'1'时立即进行标记和扩展

5. 高频考点与应试技巧

5.1 时间复杂度分析

东华OJ题常要求分析算法复杂度。几个常见复杂度及其场景：

5.2 代码风格建议

1. 变量命名要有意义（避免用temp, a, b等）
2. 适当添加注释解释复杂逻辑
3. 保持一致的缩进风格（4个空格）
4. 函数长度控制在30行以内
5. 边界条件要单独测试（空输入、极值等）

5.3 调试技巧

1. 使用print调试关键变量值
2. 对样例输入手动模拟算法流程
3. 编写测试用例覆盖各种边界情况
4. 利用OJ提供的错误信息定位问题
5. 遇到超时先检查死循环和复杂度

6. 复试准备建议

1. 基础巩固：重点复习数据结构（树、图、堆）和算法（排序、查找、DP）
2. 刷题策略：按专题练习（字符串、数组、链表等），每个专题10-15题
3. 错题整理：建立错题本，记录错误原因和正确解法
4. 模拟练习：使用计时功能模拟真实考试环境
5. 代码规范：平时就注意书写规范，避免考试时扣分

这套OJ题目很好地覆盖了复试常见考点，建议至少刷3遍：

• 第一遍：熟悉题目，记录难点
• 第二遍：优化解法，分析复杂度
• 第三遍：模拟考试，提升速度