1. 项目背景与目标最近在准备复旦计算机考研复试的机试环节Day4的学习内容主要围绕数据结构与算法展开。作为过来人我深知机试环节对最终录取结果的重要性。根据往年经验复旦机试题目往往注重考察基础算法的实际应用能力特别是对时间复杂度的把控和边界条件的处理。这次的学习计划主要针对以下几个核心考点常见排序算法的实现与优化二叉树相关的高频题型动态规划问题的解题框架图论基础算法的应用场景2. 核心算法精讲2.1 排序算法实战快速排序是机试中的常客这里分享一个经过优化的版本def quick_sort(arr, left, right): if left right: return # 三数取中法选择基准值 mid left (right - left) // 2 if arr[left] arr[right]: arr[left], arr[right] arr[right], arr[left] if arr[mid] arr[right]: arr[mid], arr[right] arr[right], arr[mid] if arr[left] arr[mid]: arr[left], arr[mid] arr[mid], arr[left] pivot arr[left] # 双指针法分区 i, j left, right while i j: while i j and arr[j] pivot: j - 1 arr[i] arr[j] while i j and arr[i] pivot: i 1 arr[j] arr[i] arr[i] pivot quick_sort(arr, left, i-1) quick_sort(arr, i1, right)注意事项在实际机试中如果数据量较大n1e5建议直接使用内置的sort函数。Python的sorted()时间复杂度是O(nlogn)比自己实现的版本更稳定。2.2 二叉树遍历技巧二叉树的非递归遍历是高频考点这里给出前序和中序的统一写法def inorderTraversal(root): res [] stack [] cur root while cur or stack: while cur: # 深入左子树 stack.append(cur) cur cur.left node stack.pop() res.append(node.val) # 访问节点 cur node.right # 转向右子树 return res对于前序遍历只需要调整访问节点的时机def preorderTraversal(root): res [] stack [root] while stack: node stack.pop() if node: res.append(node.val) # 先访问 stack.append(node.right) # 右先入栈 stack.append(node.left) return res3. 动态规划专题3.1 经典背包问题0-1背包问题的标准解法def knapsack(weights, values, capacity): n len(weights) dp [[0]*(capacity1) for _ in range(n1)] for i in range(1, n1): for j in range(1, capacity1): if weights[i-1] j: dp[i][j] max(dp[i-1][j], values[i-1]dp[i-1][j-weights[i-1]]) else: dp[i][j] dp[i-1][j] return dp[n][capacity]空间优化版本滚动数组def knapsack(weights, values, capacity): dp [0]*(capacity1) for i in range(len(weights)): for j in range(capacity, weights[i]-1, -1): # 逆向遍历 dp[j] max(dp[j], values[i]dp[j-weights[i]]) return dp[capacity]3.2 常见DP问题模板最长递增子序列(LIS)def lengthOfLIS(nums): 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)编辑距离问题def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]4. 图论算法精要4.1 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 distances4.2 拓扑排序实现Kahn算法实现def topologicalSort(graph): in_degree {u:0 for u in graph} for u in graph: for v in graph[u]: in_degree[v] 1 queue [u for u in graph if in_degree[u] 0] topo_order [] while queue: u queue.pop(0) topo_order.append(u) for v in graph[u]: in_degree[v] - 1 if in_degree[v] 0: queue.append(v) if len(topo_order) len(graph): return topo_order else: return [] # 存在环5. 机试实战技巧5.1 输入输出优化Python中的快速IO方法import sys # 读取单行 line sys.stdin.readline().strip() # 读取多个数字 a, b map(int, sys.stdin.readline().split()) # 读取多行数据 while True: try: line sys.stdin.readline().strip() if not line: break # 处理逻辑 except: break重要提示在OJ系统中使用sys.stdin读取比input()快很多特别是大数据量时。5.2 常见错误排查数组越界特别是在处理字符串或数组时注意循环条件是否包含等号整数溢出Python虽然不会溢出但其他语言需要注意边界条件空输入、单个元素等特殊情况浮点精度比较浮点数时使用abs(a-b)1e-6而非直接5.3 调试技巧打印中间变量print(Debug:, variable, filesys.stderr) # 不影响标准输出使用断言assert len(nums) 0, 输入不能为空小数据测试先用手算能验证的小数据测试6. 真题模拟训练最后分享一道往年的机试真题及解法题目描述 给定一个字符串s找出其中最长的回文子串。假设字符串长度不超过1000。示例解法def longestPalindrome(s): n len(s) if n 2: return s start, max_len 0, 1 dp [[False]*n for _ in range(n)] for i in range(n): dp[i][i] True for j in range(1, n): for i in range(j): if s[i] s[j]: if j - i 3: dp[i][j] True else: dp[i][j] dp[i1][j-1] if dp[i][j] and j-i1 max_len: max_len j-i1 start i return s[start:startmax_len]这个解法使用了动态规划时间复杂度O(n^2)空间复杂度O(n^2)。在机试环境中对于n1000的数据规模是完全可行的。