蓝桥杯Java基础算法全攻略：从排序到贪心的备赛指南

1. 环境准备与备赛思路1.1 Java环境配置与OJ平台选型先说点实在话。很多同学学Java基础算法一上来就闷头刷题结果越刷越迷茫IDE装好了不会配、本地跑通了提交却编译报错、明明思路对了一交上去就超时。这些问题我在带蓝桥杯集训队时见得太多了所以这一章先从环境讲起。Java环境配置其实就三步装JDK、配环境变量、验证。JDK版本建议直接用17或21蓝桥杯OJ系统早就支持新版Java了网上那些还在让你装JDK 8的文章多半是几年前的教程。配环境变量时在Windows下就是新建一个JAVA_HOME指向你的JDK安装目录然后往Path里追加%JAVA_HOME%\bin。记得在命令行敲java -version确认一下能正常输出版本号就说明环境没问题。OJ平台选型上蓝桥杯官网的练习系统是必刷的历年真题都在那里。除此之外LeetCode的“必刷基础算法题”热榜和咱们常规的在线评测平台也可以作为日常练习场。不过我要提醒一点蓝桥杯的题目风格和LeetCode有区别蓝桥杯更看重程序的完整性和边界处理能力做题时一定要在本地把完整代码写出来别只写核心函数就完事。很多同学在本地IDE里写主类跑通一到OJ上忘记类名必须叫Main、忘记去掉包名直接白给。1.2 蓝桥杯的算法考察范围与学习节奏蓝桥杯Java组的基础算法考察范围说白了就那几个板块枚举、模拟、排序、查找、递归、贪心、动态规划入门、搜索DFS/BFS、数据结构基础栈、队列、链表、哈希。别被“算法”两个字吓住蓝桥杯省赛的难度层次很分明前几道题基本都是枚举、模拟和简单排序吃透基础算法拿个省二省三是大概率事件。学习节奏上我建议分三个阶段。第一个阶段两周左右把基础算法全部过一遍重点搞定排序、二分、递归、枚举每类算法至少亲手敲三遍代码。第二个阶段开始刷真题从最近的年份往前刷每套题掐时间模拟。第三个阶段是查漏补缺把薄弱环节针对性训练。特别推荐用“分类刷题法”一周只刷枚举题下一周只刷排序题这样能快速建立题感比每天随机换类型强太多。2. 排序算法从冒泡到快排的进阶之路2.1 基础排序的代码模板与复杂度对比排序是算法学习的第一个硬骨头也是蓝桥杯高频考点。Java里虽然可以直接用Arrays.sort()但竞赛题经常让你手工实现而且排序思想是后面很多算法的地基。咱们从最基础的三种排序说起。冒泡排序是最好写的两层循环外层控制轮数内层做相邻比较和交换。核心代码就这几行public static void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped true; } } if (!swapped) break; // 优化没有交换说明已经有序 } }这个swapped标记就是常说的优化点真题里有时候会考“最好情况下冒泡排序的时间复杂度”答O(n)就是因为这个标记。选择排序和插入排序也属于必须掌握的内容特别是插入排序它在数据基本有序时效率很高而且思想被用在希尔排序和各种高级算法的常数优化里。三种基础排序的复杂度关系冒泡排序平均O(n²)最好O(n)稳定选择排序平均O(n²)最好O(n²)不稳定插入排序平均O(n²)最好O(n)稳定选排序写代码时最容易踩的坑是“交换目标位置和自己”加上if (minIndex ! i)判断能省掉一次无意义的赋值。插入排序的坑在于内层循环的边界条件j 0 arr[j - 1] key这个顺序不能反否则当前元素根本挪不动。2.2 快速排序与归并排序蓝桥杯高频考点真正在蓝桥杯真题里频繁考察的是快速排序和归并排序尤其是归并排序的逆序对问题属于经典中的经典。快速排序的核心是分区partition操作我推荐用“挖坑法”实现逻辑最直白public static void quickSort(int[] arr, int left, int right) { if (left right) return; int pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) j--; if (i j) arr[i] arr[j]; while (i j arr[i] pivot) i; if (i j) arr[j--] arr[i]; } arr[i] pivot; quickSort(arr, left, i - 1); quickSort(arr, i 1, right); }这里有个实战经验如果数组里大量重复元素上面的写法会退化到接近O(n²)。蓝桥杯的测试数据经常故意放重复元素所以你需要在分区循环里处理相等情况——要么用三路快排要么在快速排序前判断一下“如果所有元素相等就不用继续排了”。用三路快排是最稳妥的所谓三路就是把小于基准、等于基准、大于基准的三段分别处理。归并排序的模板我更推荐背下来因为它的稳定性和可预测的O(nlogn)复杂度在竞赛里很讨喜public static void mergeSort(int[] arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } public static void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) temp[k] arr[i]; else temp[k] arr[j]; } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; for (int p 0; p temp.length; p) arr[left p] temp[p]; }注意mid的计算用left (right - left) / 2而不是(left right) / 2这一步能防止大数组时leftright整型溢出也是面试和竞赛中非常喜欢考察的细节。3. 查找算法与枚举思想3.1 二分查找的边界处理与变形题目二分查找是蓝桥杯的必考内容说它是基础算法里的性价比之王一点不夸张代码短、思路清晰、变形丰富。但恰恰是这段十行不到的代码每年能挂掉一半选手原因就是边界条件搞不清楚。我先给出最经典的“查找第一个等于target的位置”的模板public static int binarySearchLeft(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid - 1; } else { left mid 1; } } if (left nums.length nums[left] target) return left; return -1; }这个模板特别容易写错的地方有两个一是left right要不要等于号二是收缩区间时mid要不要加一减一。我的经验是直接用左闭右闭区间配合等于号循环看nums[mid] target时收缩右边界这样返回的left天然就是第一个满足条件的位置。蓝桥杯里常见的二分变形包括查找旋转数组的最小值、查找峰值元素、二分答案最大值最小化、最小值最大化这些都建立在你对基础模板了然于胸的基础上。二分答案这一块很多人不懂我举个例子。题目让“求最大能装多少东西使每份不超过limit”这类问题直接枚举超时但答案具有单调性如果容量cap可行cap1一定也可行。于是可以对答案二分每次用O(n)验证整体复杂度从O(n²)降到O(nlogn)。判断“是否可行”的验证函数就是这类题的核心。3.2 枚举与模拟蓝桥杯最亲民的送分题如果把蓝桥杯基础算法按得分性价比排个序枚举和模拟绝对并列第一。省赛的前两道题九成概率就是枚举或模拟。枚举的核心就一句话把所有可能的情况不重不漏地试一遍。听起来简单实际做题时最大的难点反而是“如何设计枚举的顺序以避免漏掉情况”。举个典型案例求1000以内所有满足“各位数字立方和等于本身”的数也就是水仙花数。最自然的写法是三层循环枚举百位、十位、个位复杂度O(1)级别的常数循环。但有的题目隐藏较深比如“给定一个正整数n求最小正整数m使得m的各位乘积等于n”这就要考虑枚举m的位数和各位数字需要一些数学直觉才能定好枚举范围。模拟题的套路更固定题目怎么说代码就怎么写关键是细心。踩过的坑主要有三种一是读入格式的坑比如用nextInt()之后直接nextLine()会把换行符读进去需要用nextLine()多吞一行二是循环边界的坑模拟题经常给“第n天”这种描述你到底是for (int i 0; i n; i)还是 n必须先从样例推敲清楚三是状态初始化的坑有些题要求输出“第0秒”的状态很多人在初始化时就把状态搞错了。3.3 Java字符串处理的常见陷阱蓝桥杯的枚举模拟题里字符串处理是绕不开的一环。Java字符串在竞赛中的使用频率极高所以这里专门讲几个高频坑。第一个坑是字符和数字的转换。char c 9; int num c - 0;这是标准写法但有人会写成Integer.parseInt(String.valueOf(c))虽然也不算错但慢且啰嗦。第二个坑是字符串匹配判断一个字符串是否“只包含字母和数字”用正则表达式matches([a-zA-Z0-9])最方便但要注意空字符串和大小写问题。第三个坑是大量字符串拼接时要用StringBuilder而不是这个在循环里差别巨大。另外提一句Java 8和更高版本在字符串上有一些特性差异但竞赛场景里别执着于新特性老老实实把基础API用熟就够用了。split()处理空字符串时的表现、substring()的区间是左闭右开、compareTo()的字典序比较这些细节每一个都值得你亲手验证一遍。4. 递归与分治算法思维的第一次跃迁4.1 递归的三要素与经典递归题目递归是很多同学的“劝退点”但只要把三个要素想清楚递归其实比循环更符合人类思维。三要素分别是终止条件、递归公式、返回值意义。以计算阶乘为例public static long factorial(int n) { if (n 1) return 1; // 终止条件 return n * factorial(n - 1); // 递归公式 }这里返回值factorial(n)的意思是“n的阶乘”终止条件是n等于1时返回1。很多人在递归里迷路就是因为没有给自己写的函数一个明确的“语义定义”写一步想一步自然越写越乱。蓝桥杯常考的递归题目有这几类斐波那契数列注意效率问题纯递归会指数爆炸要用记忆化、汉诺塔、全排列、组合数计算。汉诺塔是个很好的思维训练题核心就三步把n-1个盘子从A借助C移到B把第n个从A移到C把n-1个从B借助A移到C。代码不超过十行但理解了它递归的“分治思想”就入门了。4.2 回溯法与深度优先搜索的入门回溯法本质上是递归的一种特殊形式区别在于它要在递归返回时“撤销”当前的选择从而穷举所有可能路径。蓝桥杯里的全排列、组合问题、数独、八皇后问题用回溯法都能解决。全排列的经典模板public static void backtrack(int[] nums, boolean[] used, ListInteger path, ListListInteger res) { if (path.size() nums.length) { res.add(new ArrayList(path)); return; } for (int i 0; i nums.length; i) { if (used[i]) continue; used[i] true; path.add(nums[i]); backtrack(nums, used, path, res); path.remove(path.size() - 1); // 撤销选择 used[i] false; } }这段代码里path.remove和used[i] false这两行就是回溯法区别于普通递归的关键。做题时有个技巧把path在递归调用前打印出来观察它是怎么一步步构建和撤销的很快就能建立起“递归栈”的心智模型。DFS深度优先搜索和回溯的关系是DFS是搜索策略回溯是其中的一种实现手法——在DFS中为了探索所有分支需要回到上一步换一条路走这就是回溯。蓝桥杯的迷宫题、岛屿数量题、矩阵路径题基本都是DFS加一个visited数组标记去过的地方。写DFS时的常见错误是忘记标记已访问导致死循环另一个极端是标记了但不撤销导致漏掉合法路径——具体要不要撤销取决于题目问的是“是否存在一条路径”还是“一共有多少种路径”。4.3 记忆化搜索递归的加速器单纯的递归经常超时因为同一个子问题被反复计算。斐波那契数列用纯递归算n50在你的电脑上可能要跑几分钟而用记忆化瞬间出结果。记忆化的思路极其简单用一个数组或Map存结果算过就不再算第二次。static long[] memo new long[100]; public static long fib(int n) { if (n 1) return n; if (memo[n] ! 0) return memo[n]; return memo[n] fib(n - 1) fib(n - 2); }就这么一个改动时间从指数级降到线性级。蓝桥杯里的很多动态规划题目本质上就是“记忆化搜索去掉递归”后的产物。我个人建议新手先练记忆化搜索理解“状态”和“转移”的概念后再学动态规划的迭代写法这样过渡非常平滑。很多教程上来就讲DP数组和状态转移方程对新手太抽象而记忆化搜索就是从你已经会的递归出发只加一个缓存数组思路没有任何跳跃。5. 贪心算法最优策略的直觉训练5.1 贪心算法的核心思路与适用条件贪心算法在蓝桥杯基础算法中的地位比较特殊代码通常极短但正确性证明经常让人头疼。贪心的核心思想是“每一步都选择当前看起来最优的决策寄希望于局部最优能推出全局最优”。这句话听起来简单但真正可怕的是——贪心并不总是对的。很多题看起来能用贪心实际上一用一个错。判断一道题能不能用贪心我的经验是看三个条件一是问题具有最优子结构即子问题的最优解能组成原问题的最优解二是贪心选择性质即每次的局部最优选择最终能导向全局最优三是最关键的一点——你得能举出反例证明自己不成立。蓝桥杯真题里最常考察的贪心场景包括活动安排问题选最多的不重叠区间、背包问题分数背包用贪心0-1背包用DP、任务调度求最小等待时间、找零钱问题等。这里特别想强调一个容易混淆的点0-1背包不能直接用贪心按单位价值从高到低取因为物品不可分割局部最优决策可能会卡住导致整体最优解丢失。而分数背包物品可以切分则可以用贪心因为每次切走最高单位价值的物品不会影响后续决策。很多新手在这两类问题上栽跟头最后总结时才发现原来“可分割性”决定了贪心的适用性。5.2 实战案例区间覆盖问题的贪心解法区间覆盖问题是我在讲贪心时最爱的入门题。题目描述很简单给定若干区间要求用最少的区间覆盖一条线段[start, end]。贪心策略是按左端点排序每次选择一个能覆盖当前起点且右端点最远的区间。public static int minCover(int[][] intervals, int start, int end) { Arrays.sort(intervals, (a, b) - a[0] - b[0]); int count 0; int curStart start; int i 0; int n intervals.length; while (curStart end) { int maxRight curStart; while (i n intervals[i][0] curStart) { maxRight Math.max(maxRight, intervals[i][1]); i; } if (maxRight curStart) return -1; // 无法推进说明覆盖不了 curStart maxRight; count; } return count; }这个代码有几个细节值得琢磨。一是排序后要把所有左端点不大于当前起点的区间全部扫一遍取最大右端点而不是只取第一个区间。二是maxRight curStart说明没有任何区间能突破当前起点直接返回-1避免死循环。三是变量i在循环中只增不减保证了总体复杂度是O(nlogn)。我每次让学生把这题抄三遍抄完再自己手写一遍基本就能理解贪心的运行逻辑了。6. 基础算法的常见问题排查与实战技巧6.1 高频Bug清单与调试思路这一小节先讲个真实统计数据我翻过几十份省赛选手的源码发现排名前五的Bug分别是数组越界、死循环、类型溢出、读入错误、变量污染。这里面每一个都是可以靠习惯避免的。数组越界的典型场景是在二分或递归里边界没处理好导致mid - 1变成负数。死循环最爱出现在while循环里没有更新指针或者遍历链表时循环条件写错导致绕圈。类型溢出是最阴的坑比如int计算阶乘n13就爆了蓝桥杯高精度题目一定要用long甚至BigInteger不要等到WA了才怀疑是溢出。调试思路我推荐三步法第一步小样例手算把答案算出来跟程序输出对比第二步在代码关键位置打印调试信息比如在快排的partition前后打印数组内容第三步用递增规模的数据测试性能从n100到n10万观察耗时。尤其最后一步很多超时问题在小数据上完全暴露不出来只有测大数据才能发现。值得单独提醒的是很多同学在OJ上提交时遇到“编译错误”就懵了。蓝桥杯要求类名必须是Main且不要package语句。我见过太多考生在本地Eclipse里调试得挺好提交时忘记改类名直接编译失败冤得很。6.2 蓝桥杯比赛的做题顺序与时间分配关于比赛策略我有一套自己的心得分享出来供大家参考。拿到卷子后先把所有题目浏览一遍大致判断每道题的难度然后按“先易后难、先短后长”的顺序做。这里所谓“短”不只是代码短还包括读题时间短、思维复杂度低的题。我建议的时间分配是前30分钟集中解决前两道最简单题中间60分钟处理中等题最后一个小时攻克难题和复盘前面的代码。不要死磕一道题超过20分钟竞赛里“捡芝麻丢西瓜”是最常见的失败原因。另外特别强调每做完一题花30秒重新读一遍自己的代码检查边界条件和输出格式。样例过了不代表对了很多题目给的是弱样例你过了样例也可能错得离谱。这里想起一个案例某年省赛题要求输出结果时“每个数字之间用空格分隔末尾不能有多余空格”我的一个学生整体思路全对就是多打了个空格直接被判0分非常可惜。类似这种输出格式题在OJ上特别容易被卡提交前一定要检查输出是否有换行符或空格多余。6.3 从基础算法到进阶算法的衔接路径基础算法学完以后接下来怎么走我给出的路线是动态规划 → 深度优先搜索加强 → 图论基础 → 数据结构进阶。这条路线不是拍脑袋定的而是基于蓝桥杯真题的分布规律。动态规划是承接基础算法最自然的下一步因为它本质上就是“递归加记忆化”的迭代形式前面已经打好基础。跟DFS相关的迷宫和岛屿问题你掌握了回溯法之后也可以直接用DFS解决只是要注意剪枝技巧。图论的入门点是图遍历DFS/BFS然后是最短路径和最小生成树这些都需要前面排序、递归和搜索的基础。还有一个很多人忽略的环节数学知识。蓝桥杯的不少题目藏着数学推导比如数论中的最大公约数、素数判断、同余问题。Java基础算法学习到这里我强烈建议你每天手写一个gcd和isPrime别小看这些几行的数学工具函数它们能解决很多看似是“高深算法”的题目。质数筛法埃氏筛也要掌握这是很多数论题的大前提。6.4 刷题习惯与备赛心态的调整最后这部分我不讲技术了讲讲更重要的东西刷题习惯和心态。第一个建议是“少看题解多想一步”。很多人做题遇到卡壳就看题解看完觉得自己懂了其实下次遇还不会。正确的做法是给每道题的思考设定一个上限时间比如15分钟过了时间还没头绪就果断看题解但看完题解后必须自己独立把代码敲出来而且隔天要再敲一遍。第二个建议是建立错题本。别用什么复杂工具一个普通文档就够了按算法类型分类记录“题目大意”、“我的错误思路”、“正确思路”、“代码要点”。考前复习时翻这个文档比重新刷题效率高十倍。第三个建议是参加模拟赛。蓝桥杯官网和其他OJ经常有模拟赛严格按照真实比赛的时间和环境去练多练几次就能消除紧张感。我见过太多平时很厉害的同学考试时因为紧张读错题、看漏条件而翻车模拟赛的价值就是让这种风险显著降低。关于心态就说一句大实话省赛拿奖没有想象中那么难别被网上渲染的焦虑带偏。把基础算法吃透保证考场不犯低级错误省二省三是稳的再往上学动态规划和搜索剪枝省一完全可以冲。基础不打牢算法书囤再多都是空中楼阁。最后的经验分享带了几届蓝桥杯选手之后我最大的感受是基础算法没那么多玄学反复练就能吃透。排序、查找、枚举、递归、贪心这些名字听着唬人其实拆开来看每个知识点也就十行核心代码。先把它写对再把它写快最后才谈得上灵活变通。如果这章里有一个方法值得你立刻行动那一定是今天就去蓝桥杯官网挑一道排序真题用快排和归并各写一遍然后提交看看能得多少分。提前做完这一步你后面会走得很轻松。