1. 项目背景与核心价值作为一名计算机专业考研党我深知算法能力在复试环节的重要性。去年备战东华大学计算机复试期间我坚持每天刷3道OJ题目并记录解题思路最终在机试环节取得了满分成绩。这个系列文章正是我的实战笔记整理特别适合需要突击提升编程能力的考研学子。相比市面上通用的算法教程本系列有三大独特优势题目全部选自东华大学历年复试真题库针对性极强每道题都包含我的考场级代码实现和优化思路特别标注了易错点和评分标准直击机试得分要点2. 题目34矩阵对角线求和2.1 问题描述给定N×N的整数矩阵计算两条对角线元素之和。主对角线从左上到右下副对角线从右上到左下。要求时间复杂度O(N)空间复杂度O(1)。输入示例3 1 2 3 4 5 6 7 8 9输出示例 25 (159 357)2.2 解题思路这道题考察数组遍历的基本功需要注意三个关键点矩阵阶数N的奇偶性会影响中心点的计算输入数据可能包含负数需要处理N1的边界情况优化技巧单次遍历同时计算两条对角线避免重复循环。主对角线元素满足ij副对角线元素满足ijN-1。2.3 代码实现n int(input()) matrix [list(map(int, input().split())) for _ in range(n)] total 0 for i in range(n): total matrix[i][i] # 主对角线 if i ! n - 1 - i: # 避免中心点重复相加 total matrix[i][n-1-i] print(total)2.4 易错点分析未处理N为奇数时的中心点重复计算问题直接扣50%分数使用双重循环导致时间复杂度不达标O(N^2)方案不得分输入读取时未正确处理空格分隔符导致运行时错误3. 题目35字符串压缩编码3.1 问题描述实现字符串的游程编码RLE将连续相同字符替换为字符出现次数。例如aaabbc压缩为a3b2c1。要求只包含大小写字母原始字符串长度≤1000输出结果不需要解压还原3.2 算法选择本题考察字符串处理能力有双指针和单指针两种主流解法。我推荐双指针方案慢指针标记当前字符起始位置快指针向前探索相同字符边界时间复杂度O(N)空间复杂度O(1)3.3 优化实现s input().strip() if not s: print() exit() res [] left 0 n len(s) for right in range(n 1): if right n or s[right] ! s[left]: res.append(s[left] str(right - left)) left right print(.join(res))3.4 评分要点正确处理空字符串情况10分处理连续字符超过9次的情况20分输出格式严格符合要求10分算法效率达标10分注意测试用例会包含AaA这种大小写交替的情况要注意ASCII码差异4. 题目36二叉树最大宽度4.1 问题描述给定二叉树的根节点计算该树的最大宽度包含节点最多的层的节点数。二叉树节点定义如下class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right4.2 解题思路本题需要层次遍历BFS的变种应用。关键突破点给每个节点分配位置编号左孩子位置2×父节点位置右孩子位置2×父节点位置1每层宽度最右位置-最左位置14.3 完整实现from collections import deque def widthOfBinaryTree(root): if not root: return 0 max_width 0 queue deque([(root, 0)]) while queue: level_size len(queue) _, first_pos queue[0] for _ in range(level_size): node, pos queue.popleft() if node.left: queue.append((node.left, 2*pos)) if node.right: queue.append((node.right, 2*pos1)) max_width max(max_width, pos - first_pos 1) return max_width4.4 复杂度分析时间复杂度O(N) 每个节点访问一次空间复杂度O(W) W为树的最大宽度实测性能在N1000时运行时间100ms5. 每日刷题方法论5.1 时间规划建议早晨30分钟复习前日错题下午60分钟限时完成新题晚上30分钟整理解题报告5.2 调试技巧使用Python的pdb调试器设置断点import pdb; pdb.set_trace()打印中间结果时添加标记print(f[DEBUG] current res: {res})对边界情况单独测试空输入、极值等5.3 效率提升秘诀建立个人错题本按错误类型分类对同类型题目做横向对比如BFS的各种应用场景每周进行一次限时模拟测试经过三个月的持续练习我的编码速度从每题平均30分钟提升到10分钟以内。最关键的是培养了严谨的边界条件检查习惯这在机试高压环境下尤为重要。建议后来者至少坚持30天连续打卡量变必然引起质变。
1. 项目背景与核心价值作为一名计算机专业考研党我深知算法能力在复试环节的重要性。去年备战东华大学计算机复试期间我坚持每天刷3道OJ题目并记录解题思路最终在机试环节取得了满分成绩。这个系列文章正是我的实战笔记整理特别适合需要突击提升编程能力的考研学子。相比市面上通用的算法教程本系列有三大独特优势题目全部选自东华大学历年复试真题库针对性极强每道题都包含我的考场级代码实现和优化思路特别标注了易错点和评分标准直击机试得分要点2. 题目34矩阵对角线求和2.1 问题描述给定N×N的整数矩阵计算两条对角线元素之和。主对角线从左上到右下副对角线从右上到左下。要求时间复杂度O(N)空间复杂度O(1)。输入示例3 1 2 3 4 5 6 7 8 9输出示例 25 (159 357)2.2 解题思路这道题考察数组遍历的基本功需要注意三个关键点矩阵阶数N的奇偶性会影响中心点的计算输入数据可能包含负数需要处理N1的边界情况优化技巧单次遍历同时计算两条对角线避免重复循环。主对角线元素满足ij副对角线元素满足ijN-1。2.3 代码实现n int(input()) matrix [list(map(int, input().split())) for _ in range(n)] total 0 for i in range(n): total matrix[i][i] # 主对角线 if i ! n - 1 - i: # 避免中心点重复相加 total matrix[i][n-1-i] print(total)2.4 易错点分析未处理N为奇数时的中心点重复计算问题直接扣50%分数使用双重循环导致时间复杂度不达标O(N^2)方案不得分输入读取时未正确处理空格分隔符导致运行时错误3. 题目35字符串压缩编码3.1 问题描述实现字符串的游程编码RLE将连续相同字符替换为字符出现次数。例如aaabbc压缩为a3b2c1。要求只包含大小写字母原始字符串长度≤1000输出结果不需要解压还原3.2 算法选择本题考察字符串处理能力有双指针和单指针两种主流解法。我推荐双指针方案慢指针标记当前字符起始位置快指针向前探索相同字符边界时间复杂度O(N)空间复杂度O(1)3.3 优化实现s input().strip() if not s: print() exit() res [] left 0 n len(s) for right in range(n 1): if right n or s[right] ! s[left]: res.append(s[left] str(right - left)) left right print(.join(res))3.4 评分要点正确处理空字符串情况10分处理连续字符超过9次的情况20分输出格式严格符合要求10分算法效率达标10分注意测试用例会包含AaA这种大小写交替的情况要注意ASCII码差异4. 题目36二叉树最大宽度4.1 问题描述给定二叉树的根节点计算该树的最大宽度包含节点最多的层的节点数。二叉树节点定义如下class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right4.2 解题思路本题需要层次遍历BFS的变种应用。关键突破点给每个节点分配位置编号左孩子位置2×父节点位置右孩子位置2×父节点位置1每层宽度最右位置-最左位置14.3 完整实现from collections import deque def widthOfBinaryTree(root): if not root: return 0 max_width 0 queue deque([(root, 0)]) while queue: level_size len(queue) _, first_pos queue[0] for _ in range(level_size): node, pos queue.popleft() if node.left: queue.append((node.left, 2*pos)) if node.right: queue.append((node.right, 2*pos1)) max_width max(max_width, pos - first_pos 1) return max_width4.4 复杂度分析时间复杂度O(N) 每个节点访问一次空间复杂度O(W) W为树的最大宽度实测性能在N1000时运行时间100ms5. 每日刷题方法论5.1 时间规划建议早晨30分钟复习前日错题下午60分钟限时完成新题晚上30分钟整理解题报告5.2 调试技巧使用Python的pdb调试器设置断点import pdb; pdb.set_trace()打印中间结果时添加标记print(f[DEBUG] current res: {res})对边界情况单独测试空输入、极值等5.3 效率提升秘诀建立个人错题本按错误类型分类对同类型题目做横向对比如BFS的各种应用场景每周进行一次限时模拟测试经过三个月的持续练习我的编码速度从每题平均30分钟提升到10分钟以内。最关键的是培养了严谨的边界条件检查习惯这在机试高压环境下尤为重要。建议后来者至少坚持30天连续打卡量变必然引起质变。
