1. 项目概述一份“过来人”的代码笔记如果你正在为北航OJOnline Judge上的题目抓耳挠腮或者想找一份靠谱的参考来验证思路、学习不同语言的实现那么你找对地方了。这份源码合集不是什么官方答案也不是什么“一键通关”的脚本它更像是我和身边一些同学在刷题路上一点点攒下来的“错题本”和“思路集”。里面包含了我们用C、Java、Python三种主流语言ACAccepted通过的代码。做这件事的初衷很简单一是给自己做个备份方便回顾二是觉得很多题目的解题思路和代码实现上的“坑”光看题目描述是体会不到的有份能跑通的代码对照着看理解起来会快很多。北航OJ的题目质量很高覆盖了从基础语法、数据结构到经典算法的各个方面是锻炼编程思维和代码能力的绝佳平台。但正因为题目经典且有一定难度很多同学会在同一个地方反复跌倒。这份合集的价值不在于给你答案去“抄”而在于给你提供一个经过验证的正确实现样本。你可以对比自己的代码看看是逻辑有漏洞还是边界条件没处理好或者是语言特性使用不当。对于正在学习第二门、第三门编程语言的同学来说同一个算法用不同语言实现更能帮你理解语言间的差异和各自的优势。比如处理字符串和容器C的STL、Java的集合框架和Python的内置数据结构用法和性能考量就完全不同。2. 源码合集的设计思路与使用定位2.1 为什么是C/Java/Python选择这三种语言覆盖是基于它们在算法竞赛和实际开发中的普及度以及各自的特点。C是算法竞赛的“事实标准”。它的执行效率极高对内存和计算资源的控制最为精细STL标准模板库提供了强大且高效的容器与算法。学习用C解OJ题能让你最直接地理解时间复杂度和空间复杂度培养写出高性能代码的直觉。很多公司技术面试中的算法轮也默认或推荐使用C。Java在企业级开发中占据统治地位。它的语法严谨面向对象特性纯粹拥有庞大的生态。用Java刷题能让你更好地理解类、接口、异常处理等工程化概念。虽然Java在绝对性能上不如C但其稳定的表现和清晰的代码结构对于培养良好的编码习惯非常有帮助。此外Java的BigInteger和BigDecimal对于处理大数运算是“开箱即用”的比C方便不少。Python以“人生苦短我用Python”著称语法简洁开发效率高。在解决一些需要快速原型验证、或者涉及字符串处理、列表推导的题目时Python往往能用极少的代码量完成。其强大的内置库如collections,itertools,heapq能让你更专注于算法逻辑本身而非语言细节。近年来Python在面试和数据处理领域的使用也越来越广泛。这份合集提供了同一问题的多语言视角不是为了炫技而是为了让你明白算法思想是核心语言只是工具。掌握核心思想后用任何语言实现都是水到渠成。2.2 合集的编排逻辑与正确性保证合集里的代码绝不是从网上随意复制粘贴的。每一份AC代码都对应着我们在北航OJ上的一次成功提交记录。在整理时我们遵循了几个原则以题号为纲所有代码按北航OJ的题目ID如1000,1001进行组织。这是最直接、最无歧义的查找方式。代码清洁提交的AC代码可能包含一些调试用的输出语句或者变量命名比较随意。在整理进合集时我们对代码进行了“美化”移除调试信息使用更有意义的变量名添加必要的注释但绝不改变原有的算法逻辑和核心代码结构。注释重点注释不会事无巨细地解释每一行而是聚焦在算法的核心思想如“此处使用迪杰斯特拉算法求单源最短路”、容易出错的边界条件如“n0或1时需要特判”、以及该语言下的特定技巧如“C中cin与scanf混用的陷阱”、“Java中Scanner读取大数据量的优化”、“Python递归深度限制”。版本标注对于C会标注使用的标准如C11/14/17因为不同标准下的特性如auto关键字、Lambda表达式可能影响代码写法。对于Python会标注主要版本如Python 3.8。重要提示OJ平台本身可能会更新、题目描述或测试数据也可能微调。虽然合集里的代码在提交时都是AC的但无法保证在任何时间点、任何环境下都100%通过。它的首要作用是参考和学习而不是“万能钥匙”。最可靠的方式永远是理解思路后自己动手实现并提交验证。3. 核心内容解析从AB到动态规划合集的题目覆盖了北航OJ的各个难度层级。下面我挑几个有代表性的类别结合具体代码片段讲讲里面的门道和不同语言的实现差异。3.1 基础输入输出与数据处理这是所有题目的第一步也是最容易栽跟头的地方。北航OJ的输入格式多变可能有多组测试数据每行数据个数不定。C示例读取不定长整数行// 题目求每行数字的和每行数字个数不定 #include iostream #include sstream #include string using namespace std; int main() { string line; while (getline(cin, line)) { // 读取整行 if (line.empty()) break; // 处理可能的空行 stringstream ss(line); int sum 0, num; while (ss num) { // 从字符串流中读取数字 sum num; } cout sum endl; } return 0; }要点使用getline读取整行避免cin跳过空格和换行带来的问题再利用stringstream进行分割。这是处理不定长输入非常稳健的模式。Java示例高效读取大数据量// 同样的问题在Java中 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); PrintWriter pw new PrintWriter(System.out); String line; while ((line br.readLine()) ! null !line.isEmpty()) { StringTokenizer st new StringTokenizer(line); int sum 0; while (st.hasMoreTokens()) { sum Integer.parseInt(st.nextToken()); } pw.println(sum); } pw.flush(); } }要点使用BufferedReader和StringTokenizer组合其效率远高于单纯的Scanner。PrintWriter用于输出也比System.out.println在大量输出时更高效。这是Java在OJ中追求性能的常见写法。Python示例最简洁的实现import sys for line in sys.stdin: line line.strip() if not line: continue numbers list(map(int, line.split())) print(sum(numbers))要点Python的简洁性体现得淋漓尽致。sys.stdin迭代读取strip()去除首尾空白split()分割map()转换类型sum()求和一气呵成。但要注意对于极大的数据量这种写法可能因为list创建而产生额外内存开销此时可以考虑直接迭代map对象。3.2 经典算法实现对比以快速排序为例排序是基础快速排序是重点。我们来看看三种语言如何实现经典的快速排序算法。C实现原地排序使用STL风格接口// 快速排序的经典分区函数 int partition(vectorint arr, int low, int high) { int pivot arr[high]; // 选择最右元素作为基准 int i low - 1; // 小于基准的区域的右边界 for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr[i], arr[j]); } } swap(arr[i 1], arr[high]); return i 1; } void quickSort(vectorint arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } // 实际调用quickSort(vec, 0, vec.size() - 1);要点这是经典的Lomuto分区方案逻辑清晰。C中直接操作vector引用效率高。但在实际解题中我们更多直接使用sort(arr.begin(), arr.end())因为STL的sort是高度优化的混合排序内省排序性能在绝大多数情况下优于手写快排。Java实现面向对象返回新数组public class QuickSort { public static int[] quickSort(int[] arr) { if (arr null || arr.length 1) { return arr.clone(); // 返回副本避免修改原数组 } int[] sortedArr arr.clone(); quickSortHelper(sortedArr, 0, sortedArr.length - 1); return sortedArr; } private static void quickSortHelper(int[] arr, int low, int high) { if (low high) return; int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; int pi i 1; quickSortHelper(arr, low, pi - 1); quickSortHelper(arr, pi 1, high); } }要点Java版本提供了一个返回新数组的静态方法更符合其“不可变性”倾向的编程风格。内部实现与C类似。实际开发中对数组排序用Arrays.sort()对集合用Collections.sort()它们都经过深度优化。Python实现极简的列表推导式版本def quick_sort(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] # 选择中间元素作为基准 left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] return quick_sort(left) middle quick_sort(right)要点这是Python函数式编程风格的优雅体现代码几乎就是算法定义的直译。但请注意这个版本不是原地排序它创建了大量新的列表空间复杂度是O(n log n)而非最优的O(log n)。在OJ题目对空间有严格限制时这种写法可能导致内存超限MLE。一个更接近C风格的原地排序版本是必要的。def quick_sort_inplace(arr, low, high): if low high: return pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] pi i 1 quick_sort_inplace(arr, low, pi - 1) quick_sort_inplace(arr, pi 1, high)对比心得从这三个实现可以看出C追求极致的控制和效率Java在效率和工程规范性间取得平衡Python则提供了表达力最强的写法但需要开发者自己警惕性能陷阱。在OJ中根据题目要求选择合适的实现方式至关重要。3.3 数据结构应用图的深度优先搜索DFS图的遍历是许多复杂算法的基础。我们以经典的“岛屿数量”或连通块问题为例展示DFS的应用。C实现使用递归和二维向量// 题目计算二维网格中‘1’陆地形成的岛屿数量 #include vector using namespace std; void dfs(vectorvectorchar grid, int i, int j) { int m grid.size(), n grid[0].size(); if (i 0 || i m || j 0 || j n || grid[i][j] 0) { return; // 越界或已是水域 } grid[i][j] 0; // 标记为已访问沉没岛屿 // 四个方向递归搜索 dfs(grid, i - 1, j); dfs(grid, i 1, j); dfs(grid, i, j - 1); dfs(grid, i, j 1); } int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); // 将整个岛屿“沉没” } } } return count; }要点递归DFS代码非常简洁。关键在于访问后立即将‘1’改为‘0’这同时起到了visited访问数组的作用节省了空间。注意递归深度如果网格非常大递归可能导致栈溢出此时需用栈模拟递归迭代DFS。Java实现递归使用方向数组public class Solution { private void dfs(char[][] grid, int i, int j) { if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0) { return; } grid[i][j] 0; // 使用方向数组使代码更清晰便于扩展如八方向 int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int[] dir : dirs) { dfs(grid, i dir[0], j dir[1]); } } public int numIslands(char[][] grid) { if (grid null || grid.length 0) return 0; int count 0; for (int i 0; i grid.length; i) { for (int j 0; j grid[0].length; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } }要点使用方向数组dirs是更工程化的写法逻辑清晰且易于修改。Java中同样要注意递归深度问题。Python实现递归注意递归深度限制def numIslands(grid): if not grid: return 0 def dfs(i, j): if not (0 i len(grid) and 0 j len(grid[0]) and grid[i][j] 1): return grid[i][j] 0 # 标记为已访问 # Python中相邻的递归调用可以写在一行但分开写更清晰 dfs(i 1, j) dfs(i - 1, j) dfs(i, j 1) dfs(i, j - 1) count 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] 1: count 1 dfs(i, j) return count要点Python的递归深度默认有限制通常1000层对于特别大的网格上述递归代码可能引发RecursionError。这是Python刷题时的一个经典“坑”。解决方案是使用栈list来模拟递归过程实现迭代DFS。def numIslands_iterative(grid): if not grid: return 0 m, n len(grid), len(grid[0]) count 0 for i in range(m): for j in range(n): if grid[i][j] 1: count 1 stack [(i, j)] while stack: ci, cj stack.pop() if 0 ci m and 0 cj n and grid[ci][cj] 1: grid[ci][cj] 0 # 将四个邻接点入栈 stack.append((ci 1, cj)) stack.append((ci - 1, cj)) stack.append((ci, cj 1)) stack.append((ci, cj - 1)) return count避坑指南在Python中处理图、树等深度可能很大的递归问题时优先考虑迭代写法使用栈或队列是一个好习惯可以彻底避免递归深度限制的问题。这份合集中对于此类问题我们通常会同时提供递归和迭代两种版本的Python代码并注明适用场景。3.4 动态规划DP问题剖析背包问题动态规划是OJ中的难点和重点。我们以经典的0-1背包问题为例展示状态定义、转移方程和代码实现。问题描述有N件物品和一个容量为V的背包。第i件物品的体积是c[i]价值是w[i]。求解将哪些物品装入背包可使价值总和最大。C实现二维DP空间未优化// 二维DP dp[i][j] 表示前i件物品背包容量为j时的最大价值 int knapsack(int V, vectorint c, vectorint w) { int N c.size(); vectorvectorint dp(N 1, vectorint(V 1, 0)); for (int i 1; i N; i) { for (int j 0; j V; j) { dp[i][j] dp[i-1][j]; // 不选第i件物品 if (j c[i-1]) { // 注意下标对齐c[i-1]对应第i件物品 dp[i][j] max(dp[i][j], dp[i-1][j - c[i-1]] w[i-1]); } } } return dp[N][V]; }要点这是最直观的DP解法dp[i][j]的状态定义清晰。空间复杂度为O(NV)。注意物品下标从0开始而DP表的第一维从1开始所以转移时用c[i-1]和w[i-1]。C实现一维DP空间优化// 一维DP滚动数组 dp[j] 表示背包容量为j时的最大价值 int knapsack_1d(int V, vectorint c, vectorint w) { int N c.size(); vectorint dp(V 1, 0); for (int i 0; i N; i) { // 必须逆序枚举容量这是关键。 for (int j V; j c[i]; --j) { dp[j] max(dp[j], dp[j - c[i]] w[i]); } } return dp[V]; }要点空间优化是背包问题的必备技巧。核心在于内层循环必须从大到小逆序遍历容量。因为dp[j]依赖于dp[j - c[i]]而j - c[i]小于j。如果顺序遍历在计算dp[j]时dp[j - c[i]]可能已经被本层循环即考虑第i件物品时更新过了这相当于同一件物品被多次放入变成了完全背包问题而不是0-1背包。这是新手最容易出错的地方之一。Java实现一维DPpublic int knapsack(int V, int[] c, int[] w) { int N c.length; int[] dp new int[V 1]; for (int i 0; i N; i) { for (int j V; j c[i]; j--) { // 同样逆序 dp[j] Math.max(dp[j], dp[j - c[i]] w[i]); } } return dp[V]; }要点逻辑与C完全一致。Java数组初始化后默认值为0符合DP初始条件。Python实现一维DPdef knapsack(V, c, w): N len(c) dp [0] * (V 1) for i in range(N): for j in range(V, c[i] - 1, -1): # 逆序步长为-1 dp[j] max(dp[j], dp[j - c[i]] w[i]) return dp[V]要点Python的range函数可以方便地实现逆序循环range(V, c[i]-1, -1)。清晰且不易出错。DP问题心得先想清楚再写代码DP的核心是状态定义和转移方程。在动手写代码前务必在纸上把dp[i][j]的含义、初始状态、转移方程写清楚。北航OJ上很多DP题目的难点在于抽象出正确的状态。从二维到一维先实现直观的二维DP确保逻辑正确。然后再考虑空间优化到一维。优化时务必画图理解遍历顺序确认依赖关系不被破坏。调试DP如果结果不对不要慌。可以打印出整个DP表对于二维或者逐步打印一维数组的变化对比与手动推导的差异。这是定位DP错误最有效的方法。4. 不同语言的特性与实战技巧在刷题过程中每种语言都有其独特的“甜点”和“坑点”。了解这些能让你事半功倍。4.1 C效率与控制优势STL容器vector,map,set,priority_queue等是算法题的利器。熟练掌握它们的特性和时间复杂度如map是O(log n)查找unordered_map是平均O(1)至关重要。算法库sort,lower_bound,next_permutation等函数能极大简化代码。IO优化在输入输出数据量极大时10^5级别使用scanf/printf或关闭cin/cout同步流可以显著提升速度。ios::sync_with_stdio(false); cin.tie(nullptr);常见坑点整数溢出这是C最隐蔽的bug来源之一。两个int相乘即使结果赋给long long乘法本身也可能已经溢出。解决方案是提前将操作数转换为long long。// 错误a*b可能溢出即使c是long long long long c a * b; // 正确 long long c 1LL * a * b;容器下标访问vector或字符串时确保下标在[0, size())范围内。未定义行为可能导致WA错误答案或RE运行时错误。内存管理虽然OJ上不用手动delete但要理解栈内存有限。超大数组如int arr[1000000]应定义为全局变量或使用vector避免栈溢出。4.2 Java严谨与健壮优势丰富的APIArrays.sort(),Collections.sort(),StringBuilder,BigInteger等工具类非常强大。清晰的错误信息相比C的段错误Java的异常堆栈信息更能帮你定位问题。面向对象对于复杂的数据结构建模如图、树节点用类来表示非常自然。常见坑点Scanner的缓慢如前所述大数据量输入时务必使用BufferedReader。默认值int[]默认全0boolean[]默认全false对象数组默认全null。初始化时要留意。字符串比较比较的是引用equals()比较的是内容。这是Java经典坑。String s1 new String(hello); String s2 new String(hello); System.out.println(s1 s2); // false System.out.println(s1.equals(s2)); // true递归深度和Python一样Java的递归深度也有限制深度过大可能引发StackOverflowError。4.3 Python简洁与陷阱优势语法糖列表推导式、生成器表达式、切片操作等能让代码极其简洁。强大的内置库collections模块deque,defaultdict,Counterheapq堆bisect二分是算法题的“瑞士军刀”。动态类型写起来快不用声明类型。常见坑点递归深度限制前文已强调务必警惕。默认约1000层。列表复制直接赋值b a是浅拷贝修改b会影响a。需要深拷贝时用copy.deepcopy()或对于简单列表用a[:]。a [[1,2], [3,4]] b a[:] # 浅拷贝b[0][0] 9 会改变 a[0][0]时间复杂度陷阱Python的list的pop(0)或insert(0, x)操作是O(n)的因为需要移动所有后续元素。需要队列时请使用collections.deque。全局解释器锁GIL与多线程在OJ中基本用不到但要知道Python的多线程不适合CPU密集型任务。5. 使用源码合集的正确姿势与避坑指南有了这份合集怎么用才能最大化它的价值而不是沦为“抄答案”的工具呢5.1 分阶段使用建议第一阶段卡壳时参考当你独立思考一段时间比如半小时后完全没有思路或者一直WAWrong Answer却找不到原因时可以打开合集找到对应题目的代码。不要直接看代码先看代码开头的注释了解大致的算法思路。然后尝试自己根据这个思路重新实现。如果还是不行再对比代码细节找到自己逻辑的漏洞。第二阶段一题多解学习对于一道已经AC的题目可以看看合集里其他语言的实现。思考为什么Python代码这么短C的这部分操作用Java怎么写这能加深你对算法本质和语言特性的理解。第三阶段专题突破如果你在动态规划上比较薄弱可以集中查看合集中所有DP题目的代码。对比它们的状态定义、转移方程、初始化有何异同总结出几类常见的DP模型如线性DP、区间DP、树形DP、状压DP。5.2 常见问题排查清单WA/TLE/MLE/RE当你的提交遇到错误时可以按以下清单自查合集中的AC代码可以作为对照的“标答”。Wrong Answer (WA)边界条件输入为0、1、负数、空数组、空字符串的情况处理了吗初始化DP数组、累加和、最大值/最小值初始值设对了吗溢出中间结果或最终结果超过int范围了吗C/Java特别注意精度浮点数比较用了吗应该用fabs(a-b) 1e-9这样的方式。逻辑错误算法本身在特定情况下有漏洞用合集的代码跑一下同样的边缘测试用例对比输出。多组数据题目要求处理到文件结束EOF你的代码在本地测试单组数据正确但提交WA很可能是因为没有正确处理多组输入。Time Limit Exceeded (TLE)复杂度你的算法时间复杂度是多少是否可能优化例如O(n²)的算法对于n10^5的数据必然超时死循环检查循环的终止条件。IO效率C用了cin/cout且没关同步Java用了ScannerPython用了input()尝试换成高效IO。常数过大在循环内部执行了低效操作如频繁的ArrayList插入删除应使用LinkedList、字符串拼接应用StringBuilder或join。Memory Limit Exceeded (MLE)不必要的存储是否开了过大的全局数组是否存储了所有中间结果而实际上可以滚动递归过深递归DFS没有剪枝导致调用栈过深Python/Java尤其需要注意。数据结构选择用HashMap存储稀疏数据是否浪费能否用数组Runtime Error (RE)数组越界这是C和Java RE的最常见原因。仔细检查所有数组访问下标。除零错误在取模、除法运算前检查分母是否为0。空指针/空引用Java中调用对象方法前检查是否为null。递归爆栈深度过大导致栈溢出。5.3 从AC到精通下一步做什么当你能够稳定AC题目后这份合集还有更多用法代码重构与优化看看自己的AC代码和合集的代码谁的更简洁、更高效尝试重构自己的代码追求极致的可读性和性能。撰写解题报告尝试为一道经典的题目写一篇详细的解题报告讲解思路、难点、坑点。这是巩固知识的最佳方式。合集的代码可以作为你报告中的示例。参与开源与贡献如果你发现了合集中某份代码的bug或者有更优的实现更快的算法、更简洁的写法非常欢迎你提出改进。这也是一个学习交流的过程。最后我想说的是刷OJ、解算法题其最终目的不是为了AC那一道题而是为了训练一种将复杂问题分解、抽象、并用代码精确描述的能力。这份源码合集希望能成为你在这条路上的一块垫脚石而不是终点。当你不再需要频繁查阅它甚至能发现其中可以改进的地方时你就真正成长了。编程之路道阻且长行则将至。
1. 项目概述一份“过来人”的代码笔记如果你正在为北航OJOnline Judge上的题目抓耳挠腮或者想找一份靠谱的参考来验证思路、学习不同语言的实现那么你找对地方了。这份源码合集不是什么官方答案也不是什么“一键通关”的脚本它更像是我和身边一些同学在刷题路上一点点攒下来的“错题本”和“思路集”。里面包含了我们用C、Java、Python三种主流语言ACAccepted通过的代码。做这件事的初衷很简单一是给自己做个备份方便回顾二是觉得很多题目的解题思路和代码实现上的“坑”光看题目描述是体会不到的有份能跑通的代码对照着看理解起来会快很多。北航OJ的题目质量很高覆盖了从基础语法、数据结构到经典算法的各个方面是锻炼编程思维和代码能力的绝佳平台。但正因为题目经典且有一定难度很多同学会在同一个地方反复跌倒。这份合集的价值不在于给你答案去“抄”而在于给你提供一个经过验证的正确实现样本。你可以对比自己的代码看看是逻辑有漏洞还是边界条件没处理好或者是语言特性使用不当。对于正在学习第二门、第三门编程语言的同学来说同一个算法用不同语言实现更能帮你理解语言间的差异和各自的优势。比如处理字符串和容器C的STL、Java的集合框架和Python的内置数据结构用法和性能考量就完全不同。2. 源码合集的设计思路与使用定位2.1 为什么是C/Java/Python选择这三种语言覆盖是基于它们在算法竞赛和实际开发中的普及度以及各自的特点。C是算法竞赛的“事实标准”。它的执行效率极高对内存和计算资源的控制最为精细STL标准模板库提供了强大且高效的容器与算法。学习用C解OJ题能让你最直接地理解时间复杂度和空间复杂度培养写出高性能代码的直觉。很多公司技术面试中的算法轮也默认或推荐使用C。Java在企业级开发中占据统治地位。它的语法严谨面向对象特性纯粹拥有庞大的生态。用Java刷题能让你更好地理解类、接口、异常处理等工程化概念。虽然Java在绝对性能上不如C但其稳定的表现和清晰的代码结构对于培养良好的编码习惯非常有帮助。此外Java的BigInteger和BigDecimal对于处理大数运算是“开箱即用”的比C方便不少。Python以“人生苦短我用Python”著称语法简洁开发效率高。在解决一些需要快速原型验证、或者涉及字符串处理、列表推导的题目时Python往往能用极少的代码量完成。其强大的内置库如collections,itertools,heapq能让你更专注于算法逻辑本身而非语言细节。近年来Python在面试和数据处理领域的使用也越来越广泛。这份合集提供了同一问题的多语言视角不是为了炫技而是为了让你明白算法思想是核心语言只是工具。掌握核心思想后用任何语言实现都是水到渠成。2.2 合集的编排逻辑与正确性保证合集里的代码绝不是从网上随意复制粘贴的。每一份AC代码都对应着我们在北航OJ上的一次成功提交记录。在整理时我们遵循了几个原则以题号为纲所有代码按北航OJ的题目ID如1000,1001进行组织。这是最直接、最无歧义的查找方式。代码清洁提交的AC代码可能包含一些调试用的输出语句或者变量命名比较随意。在整理进合集时我们对代码进行了“美化”移除调试信息使用更有意义的变量名添加必要的注释但绝不改变原有的算法逻辑和核心代码结构。注释重点注释不会事无巨细地解释每一行而是聚焦在算法的核心思想如“此处使用迪杰斯特拉算法求单源最短路”、容易出错的边界条件如“n0或1时需要特判”、以及该语言下的特定技巧如“C中cin与scanf混用的陷阱”、“Java中Scanner读取大数据量的优化”、“Python递归深度限制”。版本标注对于C会标注使用的标准如C11/14/17因为不同标准下的特性如auto关键字、Lambda表达式可能影响代码写法。对于Python会标注主要版本如Python 3.8。重要提示OJ平台本身可能会更新、题目描述或测试数据也可能微调。虽然合集里的代码在提交时都是AC的但无法保证在任何时间点、任何环境下都100%通过。它的首要作用是参考和学习而不是“万能钥匙”。最可靠的方式永远是理解思路后自己动手实现并提交验证。3. 核心内容解析从AB到动态规划合集的题目覆盖了北航OJ的各个难度层级。下面我挑几个有代表性的类别结合具体代码片段讲讲里面的门道和不同语言的实现差异。3.1 基础输入输出与数据处理这是所有题目的第一步也是最容易栽跟头的地方。北航OJ的输入格式多变可能有多组测试数据每行数据个数不定。C示例读取不定长整数行// 题目求每行数字的和每行数字个数不定 #include iostream #include sstream #include string using namespace std; int main() { string line; while (getline(cin, line)) { // 读取整行 if (line.empty()) break; // 处理可能的空行 stringstream ss(line); int sum 0, num; while (ss num) { // 从字符串流中读取数字 sum num; } cout sum endl; } return 0; }要点使用getline读取整行避免cin跳过空格和换行带来的问题再利用stringstream进行分割。这是处理不定长输入非常稳健的模式。Java示例高效读取大数据量// 同样的问题在Java中 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); PrintWriter pw new PrintWriter(System.out); String line; while ((line br.readLine()) ! null !line.isEmpty()) { StringTokenizer st new StringTokenizer(line); int sum 0; while (st.hasMoreTokens()) { sum Integer.parseInt(st.nextToken()); } pw.println(sum); } pw.flush(); } }要点使用BufferedReader和StringTokenizer组合其效率远高于单纯的Scanner。PrintWriter用于输出也比System.out.println在大量输出时更高效。这是Java在OJ中追求性能的常见写法。Python示例最简洁的实现import sys for line in sys.stdin: line line.strip() if not line: continue numbers list(map(int, line.split())) print(sum(numbers))要点Python的简洁性体现得淋漓尽致。sys.stdin迭代读取strip()去除首尾空白split()分割map()转换类型sum()求和一气呵成。但要注意对于极大的数据量这种写法可能因为list创建而产生额外内存开销此时可以考虑直接迭代map对象。3.2 经典算法实现对比以快速排序为例排序是基础快速排序是重点。我们来看看三种语言如何实现经典的快速排序算法。C实现原地排序使用STL风格接口// 快速排序的经典分区函数 int partition(vectorint arr, int low, int high) { int pivot arr[high]; // 选择最右元素作为基准 int i low - 1; // 小于基准的区域的右边界 for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr[i], arr[j]); } } swap(arr[i 1], arr[high]); return i 1; } void quickSort(vectorint arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } // 实际调用quickSort(vec, 0, vec.size() - 1);要点这是经典的Lomuto分区方案逻辑清晰。C中直接操作vector引用效率高。但在实际解题中我们更多直接使用sort(arr.begin(), arr.end())因为STL的sort是高度优化的混合排序内省排序性能在绝大多数情况下优于手写快排。Java实现面向对象返回新数组public class QuickSort { public static int[] quickSort(int[] arr) { if (arr null || arr.length 1) { return arr.clone(); // 返回副本避免修改原数组 } int[] sortedArr arr.clone(); quickSortHelper(sortedArr, 0, sortedArr.length - 1); return sortedArr; } private static void quickSortHelper(int[] arr, int low, int high) { if (low high) return; int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; int pi i 1; quickSortHelper(arr, low, pi - 1); quickSortHelper(arr, pi 1, high); } }要点Java版本提供了一个返回新数组的静态方法更符合其“不可变性”倾向的编程风格。内部实现与C类似。实际开发中对数组排序用Arrays.sort()对集合用Collections.sort()它们都经过深度优化。Python实现极简的列表推导式版本def quick_sort(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] # 选择中间元素作为基准 left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] return quick_sort(left) middle quick_sort(right)要点这是Python函数式编程风格的优雅体现代码几乎就是算法定义的直译。但请注意这个版本不是原地排序它创建了大量新的列表空间复杂度是O(n log n)而非最优的O(log n)。在OJ题目对空间有严格限制时这种写法可能导致内存超限MLE。一个更接近C风格的原地排序版本是必要的。def quick_sort_inplace(arr, low, high): if low high: return pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] pi i 1 quick_sort_inplace(arr, low, pi - 1) quick_sort_inplace(arr, pi 1, high)对比心得从这三个实现可以看出C追求极致的控制和效率Java在效率和工程规范性间取得平衡Python则提供了表达力最强的写法但需要开发者自己警惕性能陷阱。在OJ中根据题目要求选择合适的实现方式至关重要。3.3 数据结构应用图的深度优先搜索DFS图的遍历是许多复杂算法的基础。我们以经典的“岛屿数量”或连通块问题为例展示DFS的应用。C实现使用递归和二维向量// 题目计算二维网格中‘1’陆地形成的岛屿数量 #include vector using namespace std; void dfs(vectorvectorchar grid, int i, int j) { int m grid.size(), n grid[0].size(); if (i 0 || i m || j 0 || j n || grid[i][j] 0) { return; // 越界或已是水域 } grid[i][j] 0; // 标记为已访问沉没岛屿 // 四个方向递归搜索 dfs(grid, i - 1, j); dfs(grid, i 1, j); dfs(grid, i, j - 1); dfs(grid, i, j 1); } int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); // 将整个岛屿“沉没” } } } return count; }要点递归DFS代码非常简洁。关键在于访问后立即将‘1’改为‘0’这同时起到了visited访问数组的作用节省了空间。注意递归深度如果网格非常大递归可能导致栈溢出此时需用栈模拟递归迭代DFS。Java实现递归使用方向数组public class Solution { private void dfs(char[][] grid, int i, int j) { if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0) { return; } grid[i][j] 0; // 使用方向数组使代码更清晰便于扩展如八方向 int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int[] dir : dirs) { dfs(grid, i dir[0], j dir[1]); } } public int numIslands(char[][] grid) { if (grid null || grid.length 0) return 0; int count 0; for (int i 0; i grid.length; i) { for (int j 0; j grid[0].length; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } }要点使用方向数组dirs是更工程化的写法逻辑清晰且易于修改。Java中同样要注意递归深度问题。Python实现递归注意递归深度限制def numIslands(grid): if not grid: return 0 def dfs(i, j): if not (0 i len(grid) and 0 j len(grid[0]) and grid[i][j] 1): return grid[i][j] 0 # 标记为已访问 # Python中相邻的递归调用可以写在一行但分开写更清晰 dfs(i 1, j) dfs(i - 1, j) dfs(i, j 1) dfs(i, j - 1) count 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] 1: count 1 dfs(i, j) return count要点Python的递归深度默认有限制通常1000层对于特别大的网格上述递归代码可能引发RecursionError。这是Python刷题时的一个经典“坑”。解决方案是使用栈list来模拟递归过程实现迭代DFS。def numIslands_iterative(grid): if not grid: return 0 m, n len(grid), len(grid[0]) count 0 for i in range(m): for j in range(n): if grid[i][j] 1: count 1 stack [(i, j)] while stack: ci, cj stack.pop() if 0 ci m and 0 cj n and grid[ci][cj] 1: grid[ci][cj] 0 # 将四个邻接点入栈 stack.append((ci 1, cj)) stack.append((ci - 1, cj)) stack.append((ci, cj 1)) stack.append((ci, cj - 1)) return count避坑指南在Python中处理图、树等深度可能很大的递归问题时优先考虑迭代写法使用栈或队列是一个好习惯可以彻底避免递归深度限制的问题。这份合集中对于此类问题我们通常会同时提供递归和迭代两种版本的Python代码并注明适用场景。3.4 动态规划DP问题剖析背包问题动态规划是OJ中的难点和重点。我们以经典的0-1背包问题为例展示状态定义、转移方程和代码实现。问题描述有N件物品和一个容量为V的背包。第i件物品的体积是c[i]价值是w[i]。求解将哪些物品装入背包可使价值总和最大。C实现二维DP空间未优化// 二维DP dp[i][j] 表示前i件物品背包容量为j时的最大价值 int knapsack(int V, vectorint c, vectorint w) { int N c.size(); vectorvectorint dp(N 1, vectorint(V 1, 0)); for (int i 1; i N; i) { for (int j 0; j V; j) { dp[i][j] dp[i-1][j]; // 不选第i件物品 if (j c[i-1]) { // 注意下标对齐c[i-1]对应第i件物品 dp[i][j] max(dp[i][j], dp[i-1][j - c[i-1]] w[i-1]); } } } return dp[N][V]; }要点这是最直观的DP解法dp[i][j]的状态定义清晰。空间复杂度为O(NV)。注意物品下标从0开始而DP表的第一维从1开始所以转移时用c[i-1]和w[i-1]。C实现一维DP空间优化// 一维DP滚动数组 dp[j] 表示背包容量为j时的最大价值 int knapsack_1d(int V, vectorint c, vectorint w) { int N c.size(); vectorint dp(V 1, 0); for (int i 0; i N; i) { // 必须逆序枚举容量这是关键。 for (int j V; j c[i]; --j) { dp[j] max(dp[j], dp[j - c[i]] w[i]); } } return dp[V]; }要点空间优化是背包问题的必备技巧。核心在于内层循环必须从大到小逆序遍历容量。因为dp[j]依赖于dp[j - c[i]]而j - c[i]小于j。如果顺序遍历在计算dp[j]时dp[j - c[i]]可能已经被本层循环即考虑第i件物品时更新过了这相当于同一件物品被多次放入变成了完全背包问题而不是0-1背包。这是新手最容易出错的地方之一。Java实现一维DPpublic int knapsack(int V, int[] c, int[] w) { int N c.length; int[] dp new int[V 1]; for (int i 0; i N; i) { for (int j V; j c[i]; j--) { // 同样逆序 dp[j] Math.max(dp[j], dp[j - c[i]] w[i]); } } return dp[V]; }要点逻辑与C完全一致。Java数组初始化后默认值为0符合DP初始条件。Python实现一维DPdef knapsack(V, c, w): N len(c) dp [0] * (V 1) for i in range(N): for j in range(V, c[i] - 1, -1): # 逆序步长为-1 dp[j] max(dp[j], dp[j - c[i]] w[i]) return dp[V]要点Python的range函数可以方便地实现逆序循环range(V, c[i]-1, -1)。清晰且不易出错。DP问题心得先想清楚再写代码DP的核心是状态定义和转移方程。在动手写代码前务必在纸上把dp[i][j]的含义、初始状态、转移方程写清楚。北航OJ上很多DP题目的难点在于抽象出正确的状态。从二维到一维先实现直观的二维DP确保逻辑正确。然后再考虑空间优化到一维。优化时务必画图理解遍历顺序确认依赖关系不被破坏。调试DP如果结果不对不要慌。可以打印出整个DP表对于二维或者逐步打印一维数组的变化对比与手动推导的差异。这是定位DP错误最有效的方法。4. 不同语言的特性与实战技巧在刷题过程中每种语言都有其独特的“甜点”和“坑点”。了解这些能让你事半功倍。4.1 C效率与控制优势STL容器vector,map,set,priority_queue等是算法题的利器。熟练掌握它们的特性和时间复杂度如map是O(log n)查找unordered_map是平均O(1)至关重要。算法库sort,lower_bound,next_permutation等函数能极大简化代码。IO优化在输入输出数据量极大时10^5级别使用scanf/printf或关闭cin/cout同步流可以显著提升速度。ios::sync_with_stdio(false); cin.tie(nullptr);常见坑点整数溢出这是C最隐蔽的bug来源之一。两个int相乘即使结果赋给long long乘法本身也可能已经溢出。解决方案是提前将操作数转换为long long。// 错误a*b可能溢出即使c是long long long long c a * b; // 正确 long long c 1LL * a * b;容器下标访问vector或字符串时确保下标在[0, size())范围内。未定义行为可能导致WA错误答案或RE运行时错误。内存管理虽然OJ上不用手动delete但要理解栈内存有限。超大数组如int arr[1000000]应定义为全局变量或使用vector避免栈溢出。4.2 Java严谨与健壮优势丰富的APIArrays.sort(),Collections.sort(),StringBuilder,BigInteger等工具类非常强大。清晰的错误信息相比C的段错误Java的异常堆栈信息更能帮你定位问题。面向对象对于复杂的数据结构建模如图、树节点用类来表示非常自然。常见坑点Scanner的缓慢如前所述大数据量输入时务必使用BufferedReader。默认值int[]默认全0boolean[]默认全false对象数组默认全null。初始化时要留意。字符串比较比较的是引用equals()比较的是内容。这是Java经典坑。String s1 new String(hello); String s2 new String(hello); System.out.println(s1 s2); // false System.out.println(s1.equals(s2)); // true递归深度和Python一样Java的递归深度也有限制深度过大可能引发StackOverflowError。4.3 Python简洁与陷阱优势语法糖列表推导式、生成器表达式、切片操作等能让代码极其简洁。强大的内置库collections模块deque,defaultdict,Counterheapq堆bisect二分是算法题的“瑞士军刀”。动态类型写起来快不用声明类型。常见坑点递归深度限制前文已强调务必警惕。默认约1000层。列表复制直接赋值b a是浅拷贝修改b会影响a。需要深拷贝时用copy.deepcopy()或对于简单列表用a[:]。a [[1,2], [3,4]] b a[:] # 浅拷贝b[0][0] 9 会改变 a[0][0]时间复杂度陷阱Python的list的pop(0)或insert(0, x)操作是O(n)的因为需要移动所有后续元素。需要队列时请使用collections.deque。全局解释器锁GIL与多线程在OJ中基本用不到但要知道Python的多线程不适合CPU密集型任务。5. 使用源码合集的正确姿势与避坑指南有了这份合集怎么用才能最大化它的价值而不是沦为“抄答案”的工具呢5.1 分阶段使用建议第一阶段卡壳时参考当你独立思考一段时间比如半小时后完全没有思路或者一直WAWrong Answer却找不到原因时可以打开合集找到对应题目的代码。不要直接看代码先看代码开头的注释了解大致的算法思路。然后尝试自己根据这个思路重新实现。如果还是不行再对比代码细节找到自己逻辑的漏洞。第二阶段一题多解学习对于一道已经AC的题目可以看看合集里其他语言的实现。思考为什么Python代码这么短C的这部分操作用Java怎么写这能加深你对算法本质和语言特性的理解。第三阶段专题突破如果你在动态规划上比较薄弱可以集中查看合集中所有DP题目的代码。对比它们的状态定义、转移方程、初始化有何异同总结出几类常见的DP模型如线性DP、区间DP、树形DP、状压DP。5.2 常见问题排查清单WA/TLE/MLE/RE当你的提交遇到错误时可以按以下清单自查合集中的AC代码可以作为对照的“标答”。Wrong Answer (WA)边界条件输入为0、1、负数、空数组、空字符串的情况处理了吗初始化DP数组、累加和、最大值/最小值初始值设对了吗溢出中间结果或最终结果超过int范围了吗C/Java特别注意精度浮点数比较用了吗应该用fabs(a-b) 1e-9这样的方式。逻辑错误算法本身在特定情况下有漏洞用合集的代码跑一下同样的边缘测试用例对比输出。多组数据题目要求处理到文件结束EOF你的代码在本地测试单组数据正确但提交WA很可能是因为没有正确处理多组输入。Time Limit Exceeded (TLE)复杂度你的算法时间复杂度是多少是否可能优化例如O(n²)的算法对于n10^5的数据必然超时死循环检查循环的终止条件。IO效率C用了cin/cout且没关同步Java用了ScannerPython用了input()尝试换成高效IO。常数过大在循环内部执行了低效操作如频繁的ArrayList插入删除应使用LinkedList、字符串拼接应用StringBuilder或join。Memory Limit Exceeded (MLE)不必要的存储是否开了过大的全局数组是否存储了所有中间结果而实际上可以滚动递归过深递归DFS没有剪枝导致调用栈过深Python/Java尤其需要注意。数据结构选择用HashMap存储稀疏数据是否浪费能否用数组Runtime Error (RE)数组越界这是C和Java RE的最常见原因。仔细检查所有数组访问下标。除零错误在取模、除法运算前检查分母是否为0。空指针/空引用Java中调用对象方法前检查是否为null。递归爆栈深度过大导致栈溢出。5.3 从AC到精通下一步做什么当你能够稳定AC题目后这份合集还有更多用法代码重构与优化看看自己的AC代码和合集的代码谁的更简洁、更高效尝试重构自己的代码追求极致的可读性和性能。撰写解题报告尝试为一道经典的题目写一篇详细的解题报告讲解思路、难点、坑点。这是巩固知识的最佳方式。合集的代码可以作为你报告中的示例。参与开源与贡献如果你发现了合集中某份代码的bug或者有更优的实现更快的算法、更简洁的写法非常欢迎你提出改进。这也是一个学习交流的过程。最后我想说的是刷OJ、解算法题其最终目的不是为了AC那一道题而是为了训练一种将复杂问题分解、抽象、并用代码精确描述的能力。这份源码合集希望能成为你在这条路上的一块垫脚石而不是终点。当你不再需要频繁查阅它甚至能发现其中可以改进的地方时你就真正成长了。编程之路道阻且长行则将至。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
