2023年春招季伴鱼技术岗的A卷在圈子里讨论度不低。原因倒不是题目有多偏多怪恰恰相反这套卷子出得相当克制——三道编程题全部围绕字符串处理、动态规划、图论三个经典方向展开没有故弄玄虚的脑筋急转弯但每一道题都埋了足够多的细节坑。三位一体考察下来既能看到候选人的基本功也能看出写代码的工程习惯。这份解析我按自己的复盘习惯整理出来了。适合三类人看一是准备投教育行业后端或算法岗位的应届生可以拿这套题自测一下水平二是已经在准备其他公司笔试的同学很多思路和排查技巧是通用的三是技术面试官可以从出题角度反推一下这类A卷到底想筛什么样的人。三道题我都给了完整的参考实现Java为主关键思路会补充说明。1. 试卷结构与考察思路分析1.1 三道题的整体布局先看这套A卷的题目分布情况我整理了一张总览表题号考察方向核心数据结构难度系数建议用时第1题字符串统计与自定义排序HashMap、Comparator偏简单15分钟第2题加权区间调度动态规划排序、二分查找、DP数组中等偏上30分钟第3题拓扑排序与环检测邻接表、队列、入度数组中等25分钟三题分布在三个完全不同的算法领域难度呈阶梯状上升。第一题是送分题但需要写对第二题是拉开差距的关键题第三题则考察图的建模能力。整体来看没有超纲内容全部落在大学数据结构与算法的课程范围内但做起来绝对不轻松。1.2 为什么这样设计题目伴鱼做在线教育业务后端系统要处理的很多问题天然就是字符串和调度类问题。比如课程内容的分词统计、学习计划的排期背后都是这几类算法。所以这套题并不是随便从题库里抽的而是紧扣业务场景的。第1题考察的是编码基本功。这道题代码量不大但涉及HashMap的统计、自定义比较器、集合排序等一堆高频API如果平时写代码依赖IDE自动补全太多在这道题上就会卡壳。第2题是经典的加权区间调度问题能区分出候选人是否真正理解了动态规划的适用条件而不是单纯背模板。第3题考察的是图论建模能力数据规模不大但环检测的正确性必须考虑周全能看出一个候选人的思维是否缜密。1.3 答题节奏建议参考我自己的经验建议时间分配如下第一题控制在10到15分钟先做掉拿稳基础分第二题留足30分钟左右这是全卷的核心题第三题如果剩余时间少于20分钟可以先写思路和核心数据结构的定义再补BFS拓扑排序的主逻辑。每一道题写完都要留2到3分钟自测边界尤其是空输入、单元素输入、存在环这三种情况这是最容易翻车的地方。2. 第1题字符串字符统计与重排2.1 题目描述给定一个只包含小写字母的字符串s请将字符串中的字符按出现频率从高到低重新排列后输出。如果两个字符的出现频率相同则按字母表顺序排列。输入输出格式要求输入一行字符串s长度$1 \le |s| \le 10^5$只含小写字母。输出重排后的字符串。示例一输入: tree 输出: eert解释t和r都出现1次e出现2次所以e开头t和r频率相同按字母序r在t前面结果为eert。示例二输入: aabbcccd 输出: cccaabb d?这里我验证一下a两次、b两次、c三次、d一次按频率从高到低ccc然后a和b频率相同按字母序a在b前最后d所以结果是cccaabbd。注意aabb中间不需要空格我写的是cccaabbd。2.2 解题思路推演这道题的核心就两个步骤统计频率、按规则排序。统计频率是标准的HashMap操作不展开说。排序这里有两种做法一种是直接对字符集合排序另一种是使用桶排序的思路。考虑到字符集只有26个小写字母其实最优做法是桶排序。先统计每个字符的频率按频率从高到低遍历每个字符直接重复输出对应次数。因为字母表顺序天然就可以通过遍历a到z保证频率从高到低可以通过排序或者手动倒序遍历实现。这里有一个容易忽略的地方如果直接用HashMapCharacter, Integer统计后把keySet转成List再sort需要自定义Comparator。我第一次写就踩了坑比较逻辑写成freqB - freqA是降频但同频情况下需要升序字母序必须追加a - b。这也就是为什么我建议直接用数组int[26]来统计避免了装箱拆箱的麻烦而且最后遍历也更容易保证字典序。2.3 参考实现import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.nextLine(); int[] freq new int[26]; for (char c : s.toCharArray()) { freq[c - a]; } ListCharacter chars new ArrayList(); for (int i 0; i 26; i) { if (freq[i] 0) { chars.add((char) (a i)); } } chars.sort((a, b) - { if (freq[a - a] ! freq[b - a]) { return freq[b - a] - freq[a - a]; // 按频率降序 } return a - b; // 同频率按字典序升序 }); StringBuilder sb new StringBuilder(); for (char c : chars) { for (int i 0; i freq[c - a]; i) { sb.append(c); } } System.out.println(sb.toString()); } }这里排序的字符集合最多24个有值的元素排序成本极低。当然也可以这么做定义一个桶数组下标是频率每个桶里存一个字符串从高频率到低频率拼接就是典型的桶排序思路复杂度O(n)。笔试现场写HashMap版本更容易出bug我建议直接用int[26]数组。2.4 现场容易踩的坑这道题翻车最多的地方不在算法而在输出。有些人统计完频率直接往HashMap里put然后遍历entrySet拼接字符串忘记先按频率排序。还有的人Comparator写反了结果频率从小到大排样例都过不了。建议提交前一定跑三个自测用例单个字符、全部相同字符、aabbcc这种所有频率相同的情况。另外一个小技巧是用StringBuilder而不要用String拼接在字符长度10^5时直接会频繁创建新对象虽然这个量级不至于超时但会显得工程素养不够。3. 第2题课程学习计划加权区间调度3.1 题目描述你是一位在线教育平台的课程顾问。平台上有n门课程每门课程有开始时间、结束时间、学习收益值。由于精力有限同一时间只能学习一门课程且课程之间不能有时间重叠但可以首尾相接即上一门课结束时间等于下一门课开始时间。请选择若干门课程使得总收益值最大。输入格式第一行一个整数n表示课程数量。接下来n行每行三个整数start_i、end_i、value_i。输出格式一个整数表示最大收益值。数据范围$1 \le n \le 10^5$$0 \le start_i end_i \le 10^9$$1 \le value_i \le 10^9$。示例3 1 2 5 2 3 6 1 3 8输出11解释选择课程[1,2]和[2,3]总收益为5 6 11大于只选[1,3]的8。3.2 先想贪心再想DP我第一次看到这题想到的是活动安排问题的贪心策略按结束时间排序后尽量选早结束的课程。但题目一旦引入每个课程的收益值不同贪心就不成立了。比如上面样例里如果按最早结束优先第一门课选[1,2]没问题但后续贪心地选[2,3]恰好是正解再看一个反例课程A[1,3]收益100课程B[1,2]收益1课程C[2,3]收益1按结束时间贪心会选B和C收益只有2但选A收益100。这说明收益值让问题从区间覆盖变成了带权区间调度。带权区间调度的标准解法就是动态规划。核心状态定义是把所有课程按结束时间升序排列设dp[i]表示前i门课程中能够获得的最大收益。对于第i门课有两种选择不选它那么收益就是dp[i-1]选了它那么收益是value_i加上dp[p]其中p是结束时间小于等于第i门课开始时间的最后一门课的编号。注意dp[p]这里用的是结束时间做下标映射所以排序后的课程顺序和二分查找就非常关键。p的查找可以用二分因为课程已经按结束时间排好序了要找的是最后一个end_j start_i的课程。3.3 二分查找的细节这里二分查找是整道题最容易写错的地方。一般写法是维护一个endTimes数组配合一个t数组存dp值的索引比如用int[] dp然后对第i门课在endTimes数组中二分查找最后一个不大于start_i的位置。由于endTimes可能重复要用右边界二分。我直接给出模板int p upperBound(endTimes, start[i]) - 1;其中upperBound返回第一个大于start[i]的位置减1恰好就是最后一个不大于start[i]的位置。如果直接用Arrays.binarySearch再处理插入点很容易边界出错。建议单独封装这个函数。3.4 参考实现import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[][] courses new int[n][3]; for (int i 0; i n; i) { courses[i][0] sc.nextInt(); courses[i][1] sc.nextInt(); courses[i][2] sc.nextInt(); } Arrays.sort(courses, (a, b) - a[1] - b[1]); long[] dp new long[n 1]; int[] endTimes new int[n]; for (int i 0; i n; i) { endTimes[i] courses[i][1]; } for (int i 0; i n; i) { int p upperBound(endTimes, courses[i][0]) - 1; long include courses[i][2] dp[p 1]; long exclude dp[i]; dp[i 1] Math.max(include, exclude); } System.out.println(dp[n]); } private static int upperBound(int[] arr, int target) { int left 0, right arr.length; while (left right) { int mid (left right) 1; if (arr[mid] target) { left mid 1; } else { right mid; } } return left; } }几个细节说明一下。第一收益值和dp数组用long因为n是10^5每个value最大10^9总和完全可能超过int范围这是这道题隐藏的一个大坑。第二p的dp下标是p1因为dp数组偏移了一位。第三排序时如果结束时间相同按开始时间排序不影响正确性但建议写成稳定的比较器即if (a[1] b[1]) return a[0] - b[0]这样二分出来的位置更符合直觉。3.5 动态规划状态转移的直观理解为什么dp[p1]而不是dp[p]因为dp数组下标从1开始对应第0门课做完后的状态。dp[i]表示前i门课程即索引0到i-1能获得的最大收益。第i门课索引i-1如果要选需要找到前p门课程索引0到p-1的最优值即dp[p]。由于我们的p是上界二分减1后的结果p可能是-1此时dp[0] 0所以统一用dp[p1]没有问题。转移方程可以直接写成dp[i1] max(dp[i], value_i dp[p1])左边的dp[i1]表示处理完第i门课程索引i-1之后的状态不选的话就继承dp[i]选的话就是当前课程收益加上兼容前序课程的最优收益。这道题做完基本就能把带权区间DP的套路吃透。同类变体还有任务调度、会议室预订、广告排期都是这个模型。4. 第3题课程依赖顺序拓扑排序与环检测4.1 题目描述某在线教育平台要为学习者们规划课程学习顺序。一共有n门课程编号从0到n-1。学习某些课程之前需要先完成若干前序课程。给定m个依赖关系每条关系用[a, b]表示学习课程a之前必须先学习课程b。请判断是否存在一种合法的学习顺序使得所有课程都能完成学习。如果存在输出任意一种顺序如果不存在输出-1。输入格式第一行两个整数n和m。接下来m行每行两个整数a、b。输出格式若存在合法顺序输出n个整数表示课程编号否则输出-1。示例一4 3 0 1 1 2 2 3输出0 1 2 3或者任何合法的顺序均可。示例二2 2 0 1 1 0输出-14.2 题目本质是图建模这道题的模板特征非常明显课程是节点依赖关系是有向边a依赖b表示有一条b指向a的边。判断是否存在一种学习顺序本质上就是判断整个有向图是否存在拓扑序列也就是图中是否存在环。有环的情况下课程之间的依赖形成死锁比如课程0依赖课程1课程1又依赖课程0那两门课都没法学。所以检测环是这道题的核心。我建议用Kahn算法做也就是BFS拓扑排序。它的思路是统计每个节点的入度把所有入度为0的节点加入队列每次出队一个节点把它加进拓扑序列同时把以它为前驱的所有节点的入度减1如果某个节点入度变为0就加入队列。最后如果拓扑序列的元素个数等于n说明无环否则存在环。4.3 参考实现import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); ListListInteger graph new ArrayList(); for (int i 0; i n; i) { graph.add(new ArrayList()); } int[] indegree new int[n]; for (int i 0; i m; i) { int a sc.nextInt(); int b sc.nextInt(); graph.get(b).add(a); // b - a indegree[a]; } QueueInteger queue new LinkedList(); for (int i 0; i n; i) { if (indegree[i] 0) { queue.offer(i); } } ListInteger order new ArrayList(); while (!queue.isEmpty()) { int cur queue.poll(); order.add(cur); for (int next : graph.get(cur)) { indegree[next]--; if (indegree[next] 0) { queue.offer(next); } } } if (order.size() ! n) { System.out.println(-1); } else { for (int i 0; i order.size(); i) { if (i 0) System.out.print( ); System.out.print(order.get(i)); } System.out.println(); } } }4.4 需要注意的边界这道题的数据范围没说但常规是n在10^5级别m在10^5级别所以用邻接表而不是邻接矩阵。另外一个需要注意的点是输入的依赖关系可能有重复这不会影响正确性因为重复边会让入度多增加一次但处理时也会多减一次Kahn算法天然兼容重复边。但如果用DFS染色法判断环重复边则不会产生实际影响因为对已经访问过的节点不会重复加边。环检测有两种思路Kahn算法是其中一种另一种是DFS三色标记法白色表示未访问灰色表示在递归栈中黑色表示已访问完成。如果在DFS过程中遇到灰色节点说明有环。这种方法也能输出拓扑序列实现是递归后入栈再反转。现场如果Kahn算法的队列实现不熟DFS三色法也可以但递归深度可能达到10^5容易栈溢出。所以我更推荐Kahn算法。4.5 三种情况的测试建议提交前建议想三组测试用例第一组是无环图验证输出顺序的长度必须是n第二组是存在环必须输出-1第三组是有多个入度为0的起始节点的情况比如0依赖12依赖3输出任意合法顺序都可以。这道题判断输出合法性的逻辑很简单检查输出的每个节点是否满足所有前驱都在它之前。笔试的判题系统通常会做这个校验。5. 现场实战经验与常见问题5.1 时间分配和节奏感我自己按这套卷子的难度估算第一题10分钟第二题35分钟第三题25分钟合计70分钟刚好符合一般笔试90分钟的时长限制。如果你在第二题卡了超过40分钟建议先跳到第三题因为第三题的拓扑排序模板相对固定拿到分的概率更高。很多人在第二题死磕导致第三题没时间写这个损失太大了。有一个经验分享给大家笔试时不要急着写代码先在纸上把每个题的数据范围和算法复杂度写出来。比如看到n10^5排序算法用O(n log n)没问题看到value_i可达10^9立刻想到long看到图题先想邻接表。这30秒的思考能避免80%的返工。5.2 输入读取和自测的细节在线笔试平台多数用标准输入输出Scanner虽然慢一些但n10^5时完全够用。如果嫌Scanner慢可以用BufferedReader但要注意读空行、换行符等细节处理不好反而容易RE。自测的时候我一般会额外测几个边界数据。比如第一题测长度1的字符串a第二题测n1即只有一门课第三题测n1, m0这种情况订单只有一个节点入度为0输出0。这些case虽然简单但能快速验证程序不会在极端情况上崩溃。5.3 从出题角度看这类A卷想考察什么我复盘这套卷子时最大的感受是它考的不是偏题怪题而是工程场景中最常见、最底层的算法能力。第一题考验候选人的基础API熟练度和代码整洁度第二题考验是否真正理解动态规划的建模过程而不是只会套模板第三题考验图论建模和边界处理能力。这三者恰好对应了后端开发日常最常打交道的三件事数据处理、资源调度、依赖管理。从面试官视角来看候选人在这套卷子上的表现主要分四档第一档三题全部AC代码清晰说明算法功底扎实可以直接进入综合面。第二档第一题全过第二题部分过或者思路正确但边界没处理好第三题有思路但没写完说明基础不错但临场时间规划需要加强。第三档只会做第一题第二题第三题都没写核心内容这说明算法训练比较薄弱。第四档第一题都写错这种基本没有后续了。所以如果你目标是进入这类教育公司的技术岗日常训练时一定不要只刷简单题要把经典DP模型和图论模板题练到条件反射的程度。5.4 两个容易忽略的刷题训练方向基于这套卷子我建议大家在准备阶段额外加强两个方向。一是带权区间调度类DP这类题在Java后端岗位笔试中出现频率极高相关变体包括最多能预约多少场会议、任务调度最大收益等核心都是按结束时间排序二分找前驱DP转移。二是拓扑排序的两种写法都要手写熟练Kahn算法和DFS三色法都要能在5分钟内无bug写出因为不同笔试平台对语言和输入输出的处理方式不同。另外代码风格也是打分会考虑的因素。变量命名有意义循环边界不靠硬背Comparator可读性好这些都会在面试官review代码的时候给你加分。最后再分享一个我实际刷题时养成的小习惯每道DP题写完都手动把样例的dp数组整个推导一遍写在草稿纸上。这个习惯能帮你抓住很多写代码时注意不到的细节比如dp数组下标偏移、二分边界条件等。这次A卷第二题我就是靠这个习惯提前发现p的取值边界才没有被卡住。
伴鱼春招A卷算法题解析：字符串统计、动规与拓扑排序实战
2023年春招季伴鱼技术岗的A卷在圈子里讨论度不低。原因倒不是题目有多偏多怪恰恰相反这套卷子出得相当克制——三道编程题全部围绕字符串处理、动态规划、图论三个经典方向展开没有故弄玄虚的脑筋急转弯但每一道题都埋了足够多的细节坑。三位一体考察下来既能看到候选人的基本功也能看出写代码的工程习惯。这份解析我按自己的复盘习惯整理出来了。适合三类人看一是准备投教育行业后端或算法岗位的应届生可以拿这套题自测一下水平二是已经在准备其他公司笔试的同学很多思路和排查技巧是通用的三是技术面试官可以从出题角度反推一下这类A卷到底想筛什么样的人。三道题我都给了完整的参考实现Java为主关键思路会补充说明。1. 试卷结构与考察思路分析1.1 三道题的整体布局先看这套A卷的题目分布情况我整理了一张总览表题号考察方向核心数据结构难度系数建议用时第1题字符串统计与自定义排序HashMap、Comparator偏简单15分钟第2题加权区间调度动态规划排序、二分查找、DP数组中等偏上30分钟第3题拓扑排序与环检测邻接表、队列、入度数组中等25分钟三题分布在三个完全不同的算法领域难度呈阶梯状上升。第一题是送分题但需要写对第二题是拉开差距的关键题第三题则考察图的建模能力。整体来看没有超纲内容全部落在大学数据结构与算法的课程范围内但做起来绝对不轻松。1.2 为什么这样设计题目伴鱼做在线教育业务后端系统要处理的很多问题天然就是字符串和调度类问题。比如课程内容的分词统计、学习计划的排期背后都是这几类算法。所以这套题并不是随便从题库里抽的而是紧扣业务场景的。第1题考察的是编码基本功。这道题代码量不大但涉及HashMap的统计、自定义比较器、集合排序等一堆高频API如果平时写代码依赖IDE自动补全太多在这道题上就会卡壳。第2题是经典的加权区间调度问题能区分出候选人是否真正理解了动态规划的适用条件而不是单纯背模板。第3题考察的是图论建模能力数据规模不大但环检测的正确性必须考虑周全能看出一个候选人的思维是否缜密。1.3 答题节奏建议参考我自己的经验建议时间分配如下第一题控制在10到15分钟先做掉拿稳基础分第二题留足30分钟左右这是全卷的核心题第三题如果剩余时间少于20分钟可以先写思路和核心数据结构的定义再补BFS拓扑排序的主逻辑。每一道题写完都要留2到3分钟自测边界尤其是空输入、单元素输入、存在环这三种情况这是最容易翻车的地方。2. 第1题字符串字符统计与重排2.1 题目描述给定一个只包含小写字母的字符串s请将字符串中的字符按出现频率从高到低重新排列后输出。如果两个字符的出现频率相同则按字母表顺序排列。输入输出格式要求输入一行字符串s长度$1 \le |s| \le 10^5$只含小写字母。输出重排后的字符串。示例一输入: tree 输出: eert解释t和r都出现1次e出现2次所以e开头t和r频率相同按字母序r在t前面结果为eert。示例二输入: aabbcccd 输出: cccaabb d?这里我验证一下a两次、b两次、c三次、d一次按频率从高到低ccc然后a和b频率相同按字母序a在b前最后d所以结果是cccaabbd。注意aabb中间不需要空格我写的是cccaabbd。2.2 解题思路推演这道题的核心就两个步骤统计频率、按规则排序。统计频率是标准的HashMap操作不展开说。排序这里有两种做法一种是直接对字符集合排序另一种是使用桶排序的思路。考虑到字符集只有26个小写字母其实最优做法是桶排序。先统计每个字符的频率按频率从高到低遍历每个字符直接重复输出对应次数。因为字母表顺序天然就可以通过遍历a到z保证频率从高到低可以通过排序或者手动倒序遍历实现。这里有一个容易忽略的地方如果直接用HashMapCharacter, Integer统计后把keySet转成List再sort需要自定义Comparator。我第一次写就踩了坑比较逻辑写成freqB - freqA是降频但同频情况下需要升序字母序必须追加a - b。这也就是为什么我建议直接用数组int[26]来统计避免了装箱拆箱的麻烦而且最后遍历也更容易保证字典序。2.3 参考实现import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.nextLine(); int[] freq new int[26]; for (char c : s.toCharArray()) { freq[c - a]; } ListCharacter chars new ArrayList(); for (int i 0; i 26; i) { if (freq[i] 0) { chars.add((char) (a i)); } } chars.sort((a, b) - { if (freq[a - a] ! freq[b - a]) { return freq[b - a] - freq[a - a]; // 按频率降序 } return a - b; // 同频率按字典序升序 }); StringBuilder sb new StringBuilder(); for (char c : chars) { for (int i 0; i freq[c - a]; i) { sb.append(c); } } System.out.println(sb.toString()); } }这里排序的字符集合最多24个有值的元素排序成本极低。当然也可以这么做定义一个桶数组下标是频率每个桶里存一个字符串从高频率到低频率拼接就是典型的桶排序思路复杂度O(n)。笔试现场写HashMap版本更容易出bug我建议直接用int[26]数组。2.4 现场容易踩的坑这道题翻车最多的地方不在算法而在输出。有些人统计完频率直接往HashMap里put然后遍历entrySet拼接字符串忘记先按频率排序。还有的人Comparator写反了结果频率从小到大排样例都过不了。建议提交前一定跑三个自测用例单个字符、全部相同字符、aabbcc这种所有频率相同的情况。另外一个小技巧是用StringBuilder而不要用String拼接在字符长度10^5时直接会频繁创建新对象虽然这个量级不至于超时但会显得工程素养不够。3. 第2题课程学习计划加权区间调度3.1 题目描述你是一位在线教育平台的课程顾问。平台上有n门课程每门课程有开始时间、结束时间、学习收益值。由于精力有限同一时间只能学习一门课程且课程之间不能有时间重叠但可以首尾相接即上一门课结束时间等于下一门课开始时间。请选择若干门课程使得总收益值最大。输入格式第一行一个整数n表示课程数量。接下来n行每行三个整数start_i、end_i、value_i。输出格式一个整数表示最大收益值。数据范围$1 \le n \le 10^5$$0 \le start_i end_i \le 10^9$$1 \le value_i \le 10^9$。示例3 1 2 5 2 3 6 1 3 8输出11解释选择课程[1,2]和[2,3]总收益为5 6 11大于只选[1,3]的8。3.2 先想贪心再想DP我第一次看到这题想到的是活动安排问题的贪心策略按结束时间排序后尽量选早结束的课程。但题目一旦引入每个课程的收益值不同贪心就不成立了。比如上面样例里如果按最早结束优先第一门课选[1,2]没问题但后续贪心地选[2,3]恰好是正解再看一个反例课程A[1,3]收益100课程B[1,2]收益1课程C[2,3]收益1按结束时间贪心会选B和C收益只有2但选A收益100。这说明收益值让问题从区间覆盖变成了带权区间调度。带权区间调度的标准解法就是动态规划。核心状态定义是把所有课程按结束时间升序排列设dp[i]表示前i门课程中能够获得的最大收益。对于第i门课有两种选择不选它那么收益就是dp[i-1]选了它那么收益是value_i加上dp[p]其中p是结束时间小于等于第i门课开始时间的最后一门课的编号。注意dp[p]这里用的是结束时间做下标映射所以排序后的课程顺序和二分查找就非常关键。p的查找可以用二分因为课程已经按结束时间排好序了要找的是最后一个end_j start_i的课程。3.3 二分查找的细节这里二分查找是整道题最容易写错的地方。一般写法是维护一个endTimes数组配合一个t数组存dp值的索引比如用int[] dp然后对第i门课在endTimes数组中二分查找最后一个不大于start_i的位置。由于endTimes可能重复要用右边界二分。我直接给出模板int p upperBound(endTimes, start[i]) - 1;其中upperBound返回第一个大于start[i]的位置减1恰好就是最后一个不大于start[i]的位置。如果直接用Arrays.binarySearch再处理插入点很容易边界出错。建议单独封装这个函数。3.4 参考实现import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[][] courses new int[n][3]; for (int i 0; i n; i) { courses[i][0] sc.nextInt(); courses[i][1] sc.nextInt(); courses[i][2] sc.nextInt(); } Arrays.sort(courses, (a, b) - a[1] - b[1]); long[] dp new long[n 1]; int[] endTimes new int[n]; for (int i 0; i n; i) { endTimes[i] courses[i][1]; } for (int i 0; i n; i) { int p upperBound(endTimes, courses[i][0]) - 1; long include courses[i][2] dp[p 1]; long exclude dp[i]; dp[i 1] Math.max(include, exclude); } System.out.println(dp[n]); } private static int upperBound(int[] arr, int target) { int left 0, right arr.length; while (left right) { int mid (left right) 1; if (arr[mid] target) { left mid 1; } else { right mid; } } return left; } }几个细节说明一下。第一收益值和dp数组用long因为n是10^5每个value最大10^9总和完全可能超过int范围这是这道题隐藏的一个大坑。第二p的dp下标是p1因为dp数组偏移了一位。第三排序时如果结束时间相同按开始时间排序不影响正确性但建议写成稳定的比较器即if (a[1] b[1]) return a[0] - b[0]这样二分出来的位置更符合直觉。3.5 动态规划状态转移的直观理解为什么dp[p1]而不是dp[p]因为dp数组下标从1开始对应第0门课做完后的状态。dp[i]表示前i门课程即索引0到i-1能获得的最大收益。第i门课索引i-1如果要选需要找到前p门课程索引0到p-1的最优值即dp[p]。由于我们的p是上界二分减1后的结果p可能是-1此时dp[0] 0所以统一用dp[p1]没有问题。转移方程可以直接写成dp[i1] max(dp[i], value_i dp[p1])左边的dp[i1]表示处理完第i门课程索引i-1之后的状态不选的话就继承dp[i]选的话就是当前课程收益加上兼容前序课程的最优收益。这道题做完基本就能把带权区间DP的套路吃透。同类变体还有任务调度、会议室预订、广告排期都是这个模型。4. 第3题课程依赖顺序拓扑排序与环检测4.1 题目描述某在线教育平台要为学习者们规划课程学习顺序。一共有n门课程编号从0到n-1。学习某些课程之前需要先完成若干前序课程。给定m个依赖关系每条关系用[a, b]表示学习课程a之前必须先学习课程b。请判断是否存在一种合法的学习顺序使得所有课程都能完成学习。如果存在输出任意一种顺序如果不存在输出-1。输入格式第一行两个整数n和m。接下来m行每行两个整数a、b。输出格式若存在合法顺序输出n个整数表示课程编号否则输出-1。示例一4 3 0 1 1 2 2 3输出0 1 2 3或者任何合法的顺序均可。示例二2 2 0 1 1 0输出-14.2 题目本质是图建模这道题的模板特征非常明显课程是节点依赖关系是有向边a依赖b表示有一条b指向a的边。判断是否存在一种学习顺序本质上就是判断整个有向图是否存在拓扑序列也就是图中是否存在环。有环的情况下课程之间的依赖形成死锁比如课程0依赖课程1课程1又依赖课程0那两门课都没法学。所以检测环是这道题的核心。我建议用Kahn算法做也就是BFS拓扑排序。它的思路是统计每个节点的入度把所有入度为0的节点加入队列每次出队一个节点把它加进拓扑序列同时把以它为前驱的所有节点的入度减1如果某个节点入度变为0就加入队列。最后如果拓扑序列的元素个数等于n说明无环否则存在环。4.3 参考实现import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); ListListInteger graph new ArrayList(); for (int i 0; i n; i) { graph.add(new ArrayList()); } int[] indegree new int[n]; for (int i 0; i m; i) { int a sc.nextInt(); int b sc.nextInt(); graph.get(b).add(a); // b - a indegree[a]; } QueueInteger queue new LinkedList(); for (int i 0; i n; i) { if (indegree[i] 0) { queue.offer(i); } } ListInteger order new ArrayList(); while (!queue.isEmpty()) { int cur queue.poll(); order.add(cur); for (int next : graph.get(cur)) { indegree[next]--; if (indegree[next] 0) { queue.offer(next); } } } if (order.size() ! n) { System.out.println(-1); } else { for (int i 0; i order.size(); i) { if (i 0) System.out.print( ); System.out.print(order.get(i)); } System.out.println(); } } }4.4 需要注意的边界这道题的数据范围没说但常规是n在10^5级别m在10^5级别所以用邻接表而不是邻接矩阵。另外一个需要注意的点是输入的依赖关系可能有重复这不会影响正确性因为重复边会让入度多增加一次但处理时也会多减一次Kahn算法天然兼容重复边。但如果用DFS染色法判断环重复边则不会产生实际影响因为对已经访问过的节点不会重复加边。环检测有两种思路Kahn算法是其中一种另一种是DFS三色标记法白色表示未访问灰色表示在递归栈中黑色表示已访问完成。如果在DFS过程中遇到灰色节点说明有环。这种方法也能输出拓扑序列实现是递归后入栈再反转。现场如果Kahn算法的队列实现不熟DFS三色法也可以但递归深度可能达到10^5容易栈溢出。所以我更推荐Kahn算法。4.5 三种情况的测试建议提交前建议想三组测试用例第一组是无环图验证输出顺序的长度必须是n第二组是存在环必须输出-1第三组是有多个入度为0的起始节点的情况比如0依赖12依赖3输出任意合法顺序都可以。这道题判断输出合法性的逻辑很简单检查输出的每个节点是否满足所有前驱都在它之前。笔试的判题系统通常会做这个校验。5. 现场实战经验与常见问题5.1 时间分配和节奏感我自己按这套卷子的难度估算第一题10分钟第二题35分钟第三题25分钟合计70分钟刚好符合一般笔试90分钟的时长限制。如果你在第二题卡了超过40分钟建议先跳到第三题因为第三题的拓扑排序模板相对固定拿到分的概率更高。很多人在第二题死磕导致第三题没时间写这个损失太大了。有一个经验分享给大家笔试时不要急着写代码先在纸上把每个题的数据范围和算法复杂度写出来。比如看到n10^5排序算法用O(n log n)没问题看到value_i可达10^9立刻想到long看到图题先想邻接表。这30秒的思考能避免80%的返工。5.2 输入读取和自测的细节在线笔试平台多数用标准输入输出Scanner虽然慢一些但n10^5时完全够用。如果嫌Scanner慢可以用BufferedReader但要注意读空行、换行符等细节处理不好反而容易RE。自测的时候我一般会额外测几个边界数据。比如第一题测长度1的字符串a第二题测n1即只有一门课第三题测n1, m0这种情况订单只有一个节点入度为0输出0。这些case虽然简单但能快速验证程序不会在极端情况上崩溃。5.3 从出题角度看这类A卷想考察什么我复盘这套卷子时最大的感受是它考的不是偏题怪题而是工程场景中最常见、最底层的算法能力。第一题考验候选人的基础API熟练度和代码整洁度第二题考验是否真正理解动态规划的建模过程而不是只会套模板第三题考验图论建模和边界处理能力。这三者恰好对应了后端开发日常最常打交道的三件事数据处理、资源调度、依赖管理。从面试官视角来看候选人在这套卷子上的表现主要分四档第一档三题全部AC代码清晰说明算法功底扎实可以直接进入综合面。第二档第一题全过第二题部分过或者思路正确但边界没处理好第三题有思路但没写完说明基础不错但临场时间规划需要加强。第三档只会做第一题第二题第三题都没写核心内容这说明算法训练比较薄弱。第四档第一题都写错这种基本没有后续了。所以如果你目标是进入这类教育公司的技术岗日常训练时一定不要只刷简单题要把经典DP模型和图论模板题练到条件反射的程度。5.4 两个容易忽略的刷题训练方向基于这套卷子我建议大家在准备阶段额外加强两个方向。一是带权区间调度类DP这类题在Java后端岗位笔试中出现频率极高相关变体包括最多能预约多少场会议、任务调度最大收益等核心都是按结束时间排序二分找前驱DP转移。二是拓扑排序的两种写法都要手写熟练Kahn算法和DFS三色法都要能在5分钟内无bug写出因为不同笔试平台对语言和输入输出的处理方式不同。另外代码风格也是打分会考虑的因素。变量命名有意义循环边界不靠硬背Comparator可读性好这些都会在面试官review代码的时候给你加分。最后再分享一个我实际刷题时养成的小习惯每道DP题写完都手动把样例的dp数组整个推导一遍写在草稿纸上。这个习惯能帮你抓住很多写代码时注意不到的细节比如dp数组下标偏移、二分边界条件等。这次A卷第二题我就是靠这个习惯提前发现p的取值边界才没有被卡住。