1. 项目背景与目标最近在准备东华大学计算机专业的研究生复试发现他们的在线评测系统OJ题目很有特点。特别是第12套题第一次做的时候踩了不少坑这次二刷特意做了详细复盘。这套题主要考察数据结构与算法的实际应用能力涉及字符串处理、动态规划等核心知识点。作为计算机专业考研复试的必考内容OJ题目的熟练度直接影响复试成绩。通过系统性地整理错题和优化解法不仅能提升编程能力还能培养解决工程问题的思维模式。下面我就把这套题的解题思路、常见陷阱和优化技巧完整分享出来。2. 题目分析与解题思路2.1 第一题字符串模式匹配这道题要求实现带通配符的字符串匹配算法。与标准KMP算法不同题目中的通配符?可以匹配任意单个字符*可以匹配任意长度字符串包括空串。def isMatch(s: str, p: str) - bool: m, n len(s), len(p) dp [[False]*(n1) for _ in range(m1)] dp[0][0] True for j in range(1, n1): if p[j-1] *: dp[0][j] dp[0][j-1] for i in range(1, m1): for j in range(1, n1): 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, val0, leftNone, rightNone): 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常见错误忘记在递归返回前弹出当前节点path.pop()没有判断叶子节点条件not node.left and not node.right直接添加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)优化思路tails数组维护当前长度的最小末尾值对于每个新元素用二分查找确定它在tails中的位置要么扩展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易错点初始值设为无穷大表示不可达除了dp[0]0内循环从coin开始避免数组越界最后需要判断是否有解是否仍为无穷大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关键步骤构建邻接表和入度数组初始化队列入度为0的节点不断移除队列中的节点并更新邻居的入度最后检查是否所有节点都被处理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(r1, c) dfs(r-1, c) dfs(r, c1) 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优化技巧直接在原数组上标记访问过的位置节省空间四个方向的DFS可以用循环简化遇到1时立即进行标记和扩展5. 高频考点与应试技巧5.1 时间复杂度分析东华OJ题常要求分析算法复杂度。几个常见复杂度及其场景复杂度典型算法适用场景O(1)哈希查找常数时间操作O(logn)二分查找有序数据查找O(n)线性扫描遍历数组/链表O(nlogn)快速排序大多数排序算法O(n²)冒泡排序简单但低效算法O(2ⁿ)全排列暴力穷举5.2 代码风格建议变量命名要有意义避免用temp, a, b等适当添加注释解释复杂逻辑保持一致的缩进风格4个空格函数长度控制在30行以内边界条件要单独测试空输入、极值等5.3 调试技巧使用print调试关键变量值对样例输入手动模拟算法流程编写测试用例覆盖各种边界情况利用OJ提供的错误信息定位问题遇到超时先检查死循环和复杂度6. 复试准备建议基础巩固重点复习数据结构树、图、堆和算法排序、查找、DP刷题策略按专题练习字符串、数组、链表等每个专题10-15题错题整理建立错题本记录错误原因和正确解法模拟练习使用计时功能模拟真实考试环境代码规范平时就注意书写规范避免考试时扣分这套OJ题目很好地覆盖了复试常见考点建议至少刷3遍第一遍熟悉题目记录难点第二遍优化解法分析复杂度第三遍模拟考试提升速度
