1. 项目背景与核心价值作为一名计算机专业考研党我在准备东华大学研究生复试时发现OJOnline Judge系统的编程题是复试中的重要环节。经历过一刷的懵懂后二刷时的复盘总结显得尤为关键。这份东华复试OJ二刷复盘5正是我在第五轮刷题过程中的深度总结主要针对动态规划、图论等高频考点题型进行系统性梳理。与初刷时单纯追求ACAccepted不同二刷更注重解题思路的优化和代码质量的提升。通过记录每道题的多种解法、时间空间复杂度对比以及常见错误点这份复盘资料不仅能帮助我巩固算法基础也为后续面试中的算法问题讨论积累了素材。从实际效果来看经过这样系统的二刷训练我在后续模拟面试中算法题的解答速度和代码规范性都有了明显提升。2. 高频题型分析与解题框架2.1 动态规划类题目精讲东华OJ中动态规划题目占比约30%主要集中在背包问题、最长子序列、矩阵路径等领域。以经典的最小路径和为例def minPathSum(grid): m, n len(grid), len(grid[0]) dp [[0]*n for _ in range(m)] dp[0][0] grid[0][0] for i in range(1, m): dp[i][0] dp[i-1][0] grid[i][0] for j in range(1, n): dp[0][j] dp[0][j-1] grid[0][j] for i in range(1, m): for j in range(1, n): dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j] return dp[-1][-1]关键优化点空间复杂度可从O(mn)优化到O(n)边界条件处理要特别注意矩阵为空的情况如果需要输出具体路径需要额外维护路径数组注意东华的测试用例往往会包含m0或n0的边界情况这是很多同学首次提交失败的主要原因。2.2 图论问题实战技巧图论题目约占25%主要集中在最短路径、拓扑排序、连通分量等题型。在实现Dijkstra算法时我发现使用优先队列的实现方式比普通队列效率提升明显import heapq def dijkstra(graph, start): distances {node: float(inf) for node in graph} distances[start] 0 heap [(0, start)] while heap: current_dist, current_node heapq.heappop(heap) if current_dist distances[current_node]: continue for neighbor, weight in graph[current_node].items(): distance current_dist weight if distance distances[neighbor]: distances[neighbor] distance heapq.heappush(heap, (distance, neighbor)) return distances常见踩坑点没有处理负权边的情况这种情况下应该使用Bellman-Ford算法图的表示方式选择不当导致超时邻接表比邻接矩阵更适合稀疏图忘记标记已访问节点导致重复计算3. 代码规范与调试技巧3.1 东华OJ的评判标准解析通过分析多次提交反馈我总结出东华OJ的几个特殊评判标准严格的输出格式要求包括但不限于行末不能有多余空格最后一行必须有换行符浮点数精度要求通常保留2位小数时间限制较为宽松但内存限制严格Python通常给2秒时间限制内存限制一般在128MB左右多测试用例并行评判程序需要能处理多个测试用例连续输入的情况每个测试用例之间变量需要正确初始化3.2 高效的调试方法针对OJ环境的特殊限制我开发了一套本地调试方案测试用例生成模板import random def generate_test_case(): n random.randint(1, 100) print(n) for _ in range(n): print(random.randint(1, 1000), end ) print()对拍脚本用于验证暴力解和优化解#!/bin/bash while true; do python generator.py input.txt python brute.py input.txt output1.txt python optimized.py input.txt output2.txt if ! diff output1.txt output2.txt; then echo Found discrepancy! break fi done内存监控工具import tracemalloc tracemalloc.start() # 你的代码 snapshot tracemalloc.take_snapshot() top_stats snapshot.statistics(lineno) for stat in top_stats[:10]: print(stat)4. 典型题目深度剖析4.1 字符串处理专题东华OJ中字符串题目常考KMP算法、字符串匹配、回文判断等。以最长回文子串为例对比两种解法动态规划解法时间复杂度O(n²)空间O(n²)def longestPalindrome(s): n len(s) dp [[False]*n for _ in range(n)] res for l in range(n): for i in range(n): j i l if j n: break if l 0: dp[i][j] True elif l 1: dp[i][j] (s[i] s[j]) else: dp[i][j] (s[i] s[j] and dp[i1][j-1]) if dp[i][j] and l1 len(res): res s[i:j1] return res中心扩展法时间复杂度O(n²)空间O(1)def expandAroundCenter(s, left, right): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return left 1, right - 1 def longestPalindrome(s): start, end 0, 0 for i in range(len(s)): l1, r1 expandAroundCenter(s, i, i) l2, r2 expandAroundCenter(s, i, i1) if r1 - l1 end - start: start, end l1, r1 if r2 - l2 end - start: start, end l2, r2 return s[start:end1]4.2 树形结构题目精解二叉树相关题目常考遍历、重建、最近公共祖先等。以下是通过前序和中序遍历重建二叉树的优化实现class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def buildTree(preorder, inorder): index_map {val:idx for idx, val in enumerate(inorder)} stack [] root None for val in preorder: node TreeNode(val) if not root: root node elif stack and index_map[val] index_map[stack[-1].val]: stack[-1].left node else: while stack and index_map[val] index_map[stack[-1].val]: parent stack.pop() parent.right node stack.append(node) return root这个实现的时间复杂度是O(n)相比递归解法减少了函数调用开销更适合处理大规模数据。5. 面试延伸问题准备5.1 算法复杂度分析进阶在面试中面试官常常会要求手动分析算法复杂度。以快速排序为例最好情况每次划分都正好平分数组递归深度log₂n每层比较次数n时间复杂度O(nlogn)最坏情况每次划分都极度不平衡递归深度n每层比较次数n时间复杂度O(n²)空间复杂度递归调用栈空间最好O(logn)最坏O(n)原地排序不需要额外空间5.2 系统设计中的算法应用面试中可能会问如何将算法应用到实际系统中。比如设计一个实时排行榜需求分析支持高频更新每秒百万级支持快速查询前K名数据规模可能达到亿级解决方案使用跳表Skip List实现插入/删除时间复杂度平均O(logn)空间复杂度O(n)支持范围查询结合Redis的ZSET实现底层使用跳表和哈希表提供现成的ZADD、ZRANGE等命令优化思路冷热数据分离定时合并写入读写分离架构6. 复盘方法与知识体系构建6.1 错题分类统计表我建立了错题分类统计表帮助发现薄弱环节题型错误次数主要错误原因改进措施动态规划8状态转移方程错误多画状态转移图图论6优先队列使用不当重写Dijkstra模板10遍字符串处理5边界条件处理不全专门练习边界用例树形结构4递归终止条件错误画出递归树验证数学问题3溢出问题统一使用long long类型6.2 知识图谱构建方法我使用思维导图工具构建算法知识图谱主要包含基础数据结构数组/链表栈/队列哈希表堆/优先队列并查集高级数据结构线段树Trie树树状数组跳表经典算法排序算法查找算法图算法字符串算法设计模式递归/分治贪心算法动态规划回溯算法这套复盘方法使我的解题能力在两周内提升了约40%特别是在面对新题时的思路形成速度明显加快。