当前位置：首页 > news >正文

东华大学OJ复试题解析：字符串匹配与动态规划实战

news 2026/8/9 2:34:37

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

常见错误：

忘记在递归返回前弹出当前节点（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(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

优化技巧：

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

5. 高频考点与应试技巧

5.1 时间复杂度分析

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

复杂度	典型算法	适用场景
O(1)	哈希查找	常数时间操作
O(logn)	二分查找	有序数据查找
O(n)	线性扫描	遍历数组/链表
O(nlogn)	快速排序	大多数排序算法
O(n²)	冒泡排序	简单但低效算法
O(2ⁿ)	全排列	暴力穷举