如果你是用 Java 报名蓝桥杯的选手第二章基础算法大概率是你备赛路上真正意义上的分水岭。我连续几年带学生准备蓝桥杯看过的报名选手不下百人最大的规律就是能稳定拿下省奖的几乎都在基础算法上下过笨功夫。而那些一上来就追着动态规划、图论跑的多半连卷子里的结果填空题都写不利索。蓝桥杯 Java 组省赛一共 10 道题、4 个小时题型里有相当比例的结果填空、代码填空和简单程序设计考的正是一批最朴素的算法枚举、模拟、排序、二分、递归、前缀和。这一章学扎实了你不仅有了保底分后续学动态规划、DFS、贪心的时候也会顺很多。这篇内容就是按“备战蓝桥杯第三章之前必须吃透的东西”来写的适合刚入门刷题的 Java 选手也适合那些已经会写代码但一上 OJ 就卡思路的同学。1. 基础算法在蓝桥杯里到底是什么地位1.1 先看清试卷结构把精力花在刀刃上蓝桥杯省赛 Java 组这几年题目数量基本稳定在 10 道左右时间 4 小时。题型大致分三类结果填空、代码填空、程序设计。其中程序设计题的难度是梯度上升的大概 30% 到 40% 的题目属于“基础算法 简单思维”就能搞定的类型。你不需要一上来就会动态规划更不需要背一堆图论模板只要把枚举、模拟、排序、二分、前缀和、简单递归这几个东西练熟练省二甚至省一的下限就已经被兜住了。很多同学容易犯一个毛病看了几道省赛真题涉及到动态规划就以为算法学习要直接奔着 DP 去。实际上 DP 那种状态转移题的难点恰恰在于“你连暴力都不会写又怎么去找重叠子问题”。基础算法这一章看起来简单却是所有高阶算法的表达工具DFS 的每一层就是枚举的递归形态动态规划的状态压缩很多时候就是枚举状态的优化版二分和前缀和更是全场用得最多的“加速器”。所以这一章不是“会了就行”而是要熟练到形成条件反射。我把这章内容按实战频率排了个序枚举和模拟 排序 二分 前缀和/差分 递归。这个顺序不是按照教材目录排的而是按历年卷子里出现的频次和取分效率排的。后文的所有代码和例题也都围绕这个主线展开。1.2 “会Java”到“会解题”还差一套基本功我发现很多同学在 IDE 里写控制台程序很流畅一上 OJ 就不会了。问题不是语法不会是缺少“把自然语言翻译成代码”的训练。比如题目里说“统计所有满足条件的整数”条件长一串不少人的第一反应是“我知道要判断但我不知道怎么写判断最简洁”再比如“求一段区间所有元素的和”很多人会写个 for 循环每次重新累加这就是典型的基础算法意识缺失。基础算法教的就是三件事怎么把问题拆小、怎么把拆出来的部分用代码表示、怎么让代码在限时内跑完。以 Java 为例你还要额外面对输入输出慢、大数溢出、对象数组排序的坑等一堆语言层面的问题。这些问题放在基础算法这一章处理是最合适的因为题目本身不复杂你有余力去关注代码的写法和性能。一旦拖到后期你又在学动态规划又得琢磨 Scanner 为什么慢那才是最痛苦的阶段。所以这一章的学习目标不是“看懂”而是“闭着眼能写”。我建议每学一个算法就立刻在 OJ 上找几道对应标签的题刷完并且把模板整理成自己的笔记。不要只复制粘贴要手动敲一遍把自己经常写错的边界条件标记出来。后面我会给出一套可以直接当笔记用的模板代码但先别急着往下翻我们先把选型思路捋清楚。2. 备战第二章算法选型与思路设计2.1 枚举与模拟看似笨却是最好的兜底招枚举字面意思就是“把所有可能的情况全部试一遍”。很多同学觉得枚举 low比赛要秀技术结果一拿到题就开始往状态压缩、线段树方向想半天写不出来。实际比赛里能暴力枚举出来的题目占了很大一块。尤其蓝桥杯有部分分机制你先把暴力写对了就能拿到一部分分数再去想优化这个策略在很多难度中等的题目里非常保值。写枚举的核心是“明确搜索空间和筛选条件”。搜索空间给大了会超时给小了会漏答案。拿到题先估算一下循环次数1 秒大概能跑 10^8 次极简操作Java 会再打点折扣控制在 10^7 到 10^8 以内比较稳。如果搜索空间是 10^9 级别那就得换个思路或者考虑枚举后能不能提前剪枝。模拟比枚举更进一步它要求你严格照着题目场景一步步执行。这类题考的是“用例理解”和“代码组织”没有太多算法思维含量但特别容易栽在细节上。我的经验是模拟题一定要先在纸上画出状态变化哪怕只是几个变量别一上来就写代码。很多选手代码写了大半才发现自己理解错了规则一改就是重写。2.2 排序别只按一个sort键就完事Java 的Arrays.sort()确实好用但你要清楚它底层在干什么。对于基本类型数组它用的是双轴快速排序对于对象数组它用的是 TimSort一种稳定的归并排序变体。这里有个隐藏考点如果你对int[]想按降序排直接传Comparator是不行的因为Comparator只适用于对象数组。我见过不少人在机试现场为了降序折腾半天最后只能手写排序白白浪费时间。所以第二张基础算法里排序要会两层第一层是用熟库函数包括正序、降序、对象按某个字段排序第二层是能手写冒泡和快排不是为了炫技而是有些题目要求你只排一部分或者让你在排序过程中做额外统计库函数反而没那么好使。冒泡排序虽然复杂度高但它的优化写法非常锻炼你对循环边界的感知。快排则需要你理解“分治”和“基准值”这是后面很多递归算法的敲门砖。2.3 二分查找见到单调性就想到它二分查找的经典使用场景是在有序数组里找某个数。但蓝桥杯里更常见的用法是在一个“具有单调性的答案范围”上二分。比如给一个阈值条件要求找“满足条件的最大值/最小值”只要判断函数写出来是单调的就可以用二分答案快速逼近结果。二分最大的坑是边界。写mid (left right) / 2还是mid left (right - left) / 2用left right还是left right退出循环后left到底指向目标还是要向左移一位这些细节都必须自己推一遍而不是靠记忆。我推荐一套模板左闭右开区间写法配合“求第一个大于等于 target 的位置”这种语义基本可以解决竞赛里 90% 的二分题。后面我会把模板代码放出来。2.4 递归与分治把规模“变小再变小”递归是基础算法这一章里最需要耐心的一块。很多人的困难是“不知道怎么往下递归”说白了就是没有找到递归公式。比如求阶乘你把n! n * (n-1)!写出来代码就出来了再比如归并排序你把“左半边排序、右半边排序、最后合并”这三句话写出来递归结构也就出来了。递归要注意两件事递归出口和递归参数。出口写错了栈溢出参数没变无限递归。写递归代码有个习惯非常有用先不要想太深假设递归函数已经实现了功能直接调用然后只关注本层怎么做。这种“信任递归”的思路能帮你跳出细节。分治思想也一样本质上就是“把大问题切成小问题小问题再切直到小到可以直接解决”归并排序、快速排序、二叉树遍历全是这个套路。3. 高频基础算法的Java实现拆解3.1 枚举与拆位这类题的Java写法蓝桥杯特别喜欢考整数拆位。所谓拆位就是把一个整数的每一位取出来处理。比如判断一个数是否含有某个数字或者统计各数字出现次数或者类似“顺子数字”这种要看相邻数位差的题。Java 里最常用的是“取余 10 整除 10”的组合int x 12345; while (x 0) { int digit x % 10; // 取出当前最低位 // 处理 digit x / 10; // 去掉最低位 }这段代码看似简单但有两个细节值得强调一是循环结束条件x变成 0 说明所有位都拆完了二是负数处理如果原数可能为负先取绝对值再拆。只要这一套写熟了很多结果填空题就能直接手算写答案根本不用上机。在枚举题的写法上我建议大家先写最简单的版本保证正确再考虑优化。比如要统计 1 到 n 之间满足条件的数可以先 for 循环从 1 到 n逐个判断。如果超时了再想想能不能跳过一些明显不可能是答案的数。很多人一上来就想构造答案反而容易漏情况这个习惯要改。3.2 排序模板与降序处理小坑大坑一起趟先说库函数的正序排序int[] arr {5, 2, 8, 1}; Arrays.sort(arr); // 升序如果你要降序对int[]最省事的写法是装箱后丢给 ComparatorInteger[] nums {5, 2, 8, 1}; Arrays.sort(nums, (a, b) - b - a);注意这里数组类型必须是Integer[]而不是int[]。如果你非要用int[]朴素办法就是自己手写一个排序循环千万不要执着地在Arrays.sort上硬传 Comparator编译都过不去。手写冒泡排序的时候我推荐的写法是加一个“是否交换过”的标记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 tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped true; } } if (!swapped) { // 没交换说明已经有序 break; } } }这样做的好处是当数组基本有序时能提前退出虽然复杂度理论没变但实战里能省不少时间。手写排序的意义不只在于降序更在于你理解“每一轮把最大值冒到末尾”这个过程。后面做某些需要在排序中同时统计逆序对的题你就知道怎么改了。3.3 二分模板与库函数正反两个写法都给你先给手写模板我习惯用“左闭右开区间”加“找第一个大于等于 target 的位置”public static int lowerBound(int[] arr, int target) { int l 0, r arr.length; // 注意r 是开区间 while (l r) { int mid l ((r - l) 1); // 防溢出写法 if (arr[mid] target) { r mid; } else { l mid 1; } } return l; // 第一个 target 的位置 }这个函数返回的是“小于 target 的元素个数”在统计题里特别好用。如果数组里不存在大于等于 target 的数l最后会走到arr.length这个值本身就表示所有元素都小于 target直接可以用不会像数组越界那样报错。Java 库函数Arrays.binarySearch也可以用但它找不到目标时返回的是负数规则是-(插入点) - 1比如数组{1, 3, 5}搜 4结果会是 -3因为 4 应该插在下标 2 处所以返回-(2) - 1 -3。你需要自己换算回插入点很容易把人绕晕。所以我个人建议竞赛场景里直接用自己写的lowerBound比记忆库函数的返回规则更踏实。3.4 前缀和与差分把区间查询从O(n)降到O(1)前缀和的思路特别简单预处理一个数组让pre[i]表示前 i 个元素的总和这样任意区间[l, r]的和就是pre[r] - pre[l - 1]查询一次从 O(n) 变成 O(1)。代价是预处理时多花 O(n)但之后不管询问多少次都极快。int[] a new int[n]; int[] pre new int[n 1]; // 多开一位方便处理 l0 for (int i 1; i n; i) { pre[i] pre[i - 1] a[i - 1]; } // 查询第 l 到第 r 个元素的和l、r从1开始计数 int sum pre[r] - pre[l - 1];一定要记得pre数组开n 1并且下标从 1 开始存。这样pre[0]就是 0查询[1, r]的时候会变成pre[r] - pre[0]逻辑统一不容易写错。如果你非要从 0 存起每次查询就要小心判断l 0的情况容易出 bug。差分跟前缀和是一对互补操作。当你需要对一个区间[l, r]整体增加一个值val朴素做法是循环累加复杂度 O(n)。用差分数组只需改两个位置int[] diff new int[n 2]; diff[l] val; diff[r 1] - val; // 最后做一次前缀和还原 for (int i 1; i n; i) { diff[i] diff[i - 1]; } // 这时候 diff[i] 就是每个位置最终叠加的值这个技巧在做二维矩阵区域加法、区间覆盖类题目时尤其有用。蓝桥杯里经常会出“m 次操作每次给某个区间的所有元素加上同一个数最后输出整个数组”差分就是标准解法。4. 真题风格实战三道题的完整复盘4.1 实战题一顺子数字统计题目描述给定一个正整数 n统计 1 到 n 之间有多少个“顺子数”。顺子数的定义是数字至少两位且从低位往高位看任意相邻两位之差的绝对值都等于 1。例如 123、321、2345 都是顺子数而 181、240 不是。这道题一看到范围如果 n 是 10^5 以内直接枚举加拆位就好完全不需要优化。核心代码就是我前面写的拆位循环import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int count 0; for (int i 10; i n; i) { // 从10开始保证至少两位 if (isShunzi(i)) { count; } } System.out.println(count); } private static boolean isShunzi(int x) { int last x % 10; x / 10; while (x 0) { int cur x % 10; if (Math.abs(cur - last) ! 1) { return false; } last cur; x / 10; } return true; } }我为什么强调从 10 开始因为在“顺子数”的定义里单独一个数字 7 没有相邻位可以考虑如果把它算进去结果会平白无故多 9 个很可能跟标准答案对不上。这种题目细节就是坑点你只能在写题的时候自己确认清楚或者看题目样例里的边界情况。枚举题的复杂度是 O(n log n)对 10^5 级别的 n 完全够用。如果你遇到的是 10^9 级别的大 n那就不能裸枚举了可以尝试按位数构造顺子数。比如从 1 位数字开始每次在低位补上满足差值 1 的数字形成新的数再判断是否小于等于 n。这就是“枚举子集”和“构造搜索”的思路等学到 DFS 之后你会有更深的体会。现阶段先把暴力分拿稳。4.2 实战题二小于x的数字个数题目描述输入一个长度为 n 的整数数组 a再输入 q 个询问每次给一个整数 x要求输出数组中有多少个数小于 x。如果 n 和 q 都是 10^5 级别每次直接遍历数组就是 O(nq)10^10 的操作量Java 基本跑不动。正确做法是先把数组排序然后用二分找到第一个大于等于 x 的位置这个位置的下标就是小于 x 的数字个数。import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int q sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } Arrays.sort(a); while (q-- 0) { int x sc.nextInt(); System.out.println(lowerBound(a, x)); } } private static int lowerBound(int[] arr, int target) { int l 0, r arr.length; while (l r) { int mid l ((r - l) 1); if (arr[mid] target) { r mid; } else { l mid 1; } } return l; } }这里有一个容易踩的坑lowerBound返回的是“第一个大于等于 x 的位置”它同时也是“小于 x 的元素数量”。为什么因为数组已经升序排列下标从 0 到返回位置之前的所有元素都小于 x。比如数组{1, 3, 5, 7}x4第一个大于等于 4 的位置是下标 2下标 0 和 1 的元素是 1 和 3正好 2 个正确。如果 x 小于所有元素返回 0表示没有数字小于 x如果 x 大于所有元素返回 n表示全部小于 x。这个边界设计是无缝的。这就是排序 二分的组合拳也是蓝桥杯里特别常见的“预处理一次多次快速查询”思路。你以后遇到“统计某范围内数的数量”之类的题都可以优先想这个套路。4.3 实战题三区间和查询题目描述给定一个长度为 n 的整数数组m 次询问每次输入 L、R输出从第 L 个元素到第 R 个元素的和。n 最大 10^5m 最大 10^5。没有前缀和的话每次查询都从 L 加到 R最坏情况是 O(nm)肯定超时。用前缀和每次查询 O(1)总复杂度 O(n m)这就是它能拿满分的根本原因。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } int[] pre new int[n 1]; for (int i 1; i n; i) { pre[i] pre[i - 1] a[i - 1]; } int m sc.nextInt(); while (m-- 0) { int l sc.nextInt(); int r sc.nextInt(); System.out.println(pre[r] - pre[l - 1]); } } }写这道题的时候我建议你先自己造一组小数据比如a {1, 2, 3, 4, 5}手推一遍pre数组应该是什么再去验证代码输出。这种“手算小样例”的习惯能帮你快速发现下标偏移错误。注意我在数组里用的是a[i - 1]因为pre[i]要累加数组的第 i 个元素而数组下标从 0 开始所以是a[i - 1]。这个偏移量看着小现场写特别容易漏。另外一个细节是查询时的 L、R 是几号元素。如果题目说“第 l 个到第 r 个”代码里pre[r] - pre[l - 1]是对的。如果题目改成“下标从 0 开始到 r 结束”那就要换成pre[r 1] - pre[l]。读题时先把下标基准搞清楚能避免后面反复改代码。5. 刷题中的常见坑与排查技巧5.1 超时元凶可能不是算法而是Scanner很多同学写完一个 O(n log n) 的算法自认为复杂度没问题结果一提交还是 TLE超时。这时候先别急着优化算法看看你的输入输出代码。Java 的Scanner在做大量输入时性能很差它的缓冲和内部正则解析开销不小。当 n 达到 10^5 或 10^6 级别Scanner可能成为最大瓶颈。我推荐的替代方案是用BufferedReaderStringTokenizer读取速度能快不少BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken());输出也一样不要一次一次System.out.println那会触发很多次 IO。用一个StringBuilder把所有结果拼起来最后一次性打印StringBuilder sb new StringBuilder(); while (condition) { sb.append(ans).append(\n); } System.out.print(sb);这套“快读快写”模板在蓝桥杯机试里非常实用尤其最后一道大题数据量大的时候省下来的时间可能就是过题和不过题的区别。建议你在平时的练习里就养成习惯别等到比赛再去试。5.2 数据溢出int不够别再硬撑基础算法里最容易忽视的是整数溢出。Java 的int最大值约 21 亿一旦累加超过这个范围数据会直接变成负数结果让人完全摸不着头脑。蓝桥杯里不少题目的累加结果都能到 10^12 甚至 10^18所以只要看到运算量或值域可能超过 10^9就果断用long。long sum 0; for (int i 0; i n; i) { sum a[i]; }如果遇到更大的数字比如 10^18 的乘幂long也不够就需要用BigInteger。但BigInteger运算非常慢建议只在非用不可的场景下使用比如高精度大数加减、大数乘除。能用long解决就不要碰BigInteger这是我刷题攒下来的经验。还有一个隐蔽点两个int相乘结果可能溢出后再赋给long。比如int a 100000; int b 100000; long c a * b;其实已经在乘法时溢出了。正确写法是long c (long) a * b;这个(long)强转得放在乘法发生之前。细节虽小但在枚举、前缀和这类题里很容易踩中。5.3 降序排序的坑别把基本类型当对象前文提过Arrays.sort传 Comparator 只适用于对象数组。如果你写int[] arr {...}; Arrays.sort(arr, (a, b) - b - a);编译直接报错。因为语法泛型要求的是对象类型int不是对象。你要么把数组改成Integer[]要么自己在循环里实现排序。这里还有个容易误导新手的点(a, b) - b - a这种写法在数值很大时可能因为差值溢出产生错误排序结果。比如a Integer.MAX_VALUE, b -1b - a会溢出成负数排序结果就乱了。比较稳妥的写法是(a, b) - Integer.compare(b, a)利用Integer.compare来比较既简洁又安全。如果你用的是Integer[]并且想按降序排也可以直接用现成的Collections.reverseOrder()Integer[] nums {3, 1, 4, 1, 5, 9}; Arrays.sort(nums, Collections.reverseOrder());这个写法简洁但记住它只能用于对象数组。如果一定要操作int[]同时还想避免装箱开销那就手写一个快速排序或者用Arrays.stream转换不过竞赛里我更推荐直接用Integer[]简单可靠数据量不大时性能差距可忽略。5.4 二分死循环与越界两个边界口诀二分最常见的现场事故是死循环。死循环的根源通常是mid计算和区间更新不匹配。我用的是左闭右开区间更新逻辑是if (arr[mid] target) r mid; else l mid 1;。因为r是开区间所以r mid是合法的不会把已经验证过的位置丢掉l mid 1是因为arr[mid] target这个位置可以直接排除。另一个容易出问题的是mid (l r) / 2在极端情况下可能溢出。虽然蓝桥杯的数组下标一般到不了 10^9但养成写l (r - l) / 2的习惯最好。我自己的口诀是区间更新要让l和r始终都在向中间收缩绝对不能出现某个分支里l或r不变化的情况否则就是死循环。遇到“求最后一个小于等于 target 的位置”这类变体二分我会建议你先把问题转化成“求某种条件的分界点”而不是死记硬背多个模板。理解了 lowerBound 这个基础版本很多变体都可以通过变换条件来套用比你背五个模板要稳得多。5.5 调试小习惯边界样例和中间结果打印基础算法题调试起来其实很直接因为逻辑不复杂大多数问题出在边界和下标。我调试时习惯先造三组数据最小数据、最大数据、特殊边界。比如二分题我肯定要试空数组、只有一个元素、所有元素都小于 target、所有元素都大于 target这四种情况跑一遍。如果结果不对就在循环的关键位置加打印语句把关键变量的中间值输出出来。比如二分里打印l、r、mid前缀和里打印pre数组中几个关心的位置。代码不复杂的时候打印调试比断点调试更快因为 OJ 环境里你也无法挂 IDE 的断点。等确认输出符合预期再把打印注释掉。还有一个习惯非常推荐不要在写完一大段代码后才提交测试。每写一个函数就可以用main方法直接调一下验证正确性。这种“小步验证”的方式能让你快速定位错误是在读题、在边界还是在代码实现而不是最后对着闪红的提交记录发呆。我个人带选手的感受是基础算法这章更像练基本功不像高阶算法那样讲究奇技淫巧但它决定你整张卷子的下限。你把这些模板练到闭眼能写考场上才有余力去啃后面的大题。另外一个小建议是每刷完一道题把题号、考点、自己犯的错都记在一个本子上。等我带下一届学生的时候他们问得最多的往往就是这些被我反复记录的“老坑”。