有人提了猿辅导2019年的校招技术笔试题问我还能不能从里面挖出点东西。说实话一套两三年前的笔试题放到现在具体题目细节肯定有变化但考察的底层能力和出题思路是真的没过时。尤其猿辅导这种在线教育公司业务场景决定了它对算法、数据结构、网络并发这些基本功有比较硬的要求笔试题目出得也相对有区分度。这篇文章我就以那套题为主线把题型结构、高频考点、典型编程题的解法和笔试实战里容易踩的坑一起拆开讲一讲。1. 这套笔试题的题型结构与备考风向先说整体印象。2019年猿辅导校招技术笔试客观题和编程题都有题量不小时间卡得比较紧。整套卷子传递出来的信号很明确它不是在考你会不会背某个API而是在考你在有限时间内能不能把基本功用出来。从题型分布来看大概是这样一个结构模块大致占比考察方向单选题30%左右数据结构、操作系统、计算机网络、数据库基础多选题10%左右某个知识点的多角度理解错选漏选都扣分编程题50%以上链表、字符串、动态规划、图论/搜索简单问答少量场景设计或概念解释比如某个技术方案的取舍为什么是这种结构因为在线教育业务对后端的要求是既要懂业务又要扛得住高并发比如选课高峰期的抢课、直播课的连麦互动、课后作业的实时批改。这些场景往底层拆全是数据结构和网络并发问题。所以笔试里客观题考基础、编程题考算法就是在筛基础扎实、能动手写代码的人。另外有一个容易被忽略的点一套题里往往会有一道场景题它不是纯算法而是给你一个业务场景让你设计方案。猿辅导这类公司很爱出这种题因为能看出你有没有工程思维。2019年的卷子里就有一道关于直播课堂里学生消息的高频推送怎么设计的题虽然乍看是系统设计但落到笔试阶段核心还是在考你对队列、缓冲、协议的理解。这种题没有标准答案考察的是思路是否完整。所以如果你现在准备技术笔试不要只盯着LeetCode刷题还得把基础概念捡起来。我当时备考时走过一个弯路就是觉得算法题刷够了就行结果选择题一道TCP三次握手为什么不是两次都犹豫了半天。这套题给我提了个醒笔试不是算法竞赛它比算法竞赛更看重全面性。2. 客观题里的高频考点这些坑你大概率也踩过客观题看起来简单实际丢分往往比编程题还多。原因是编程题错了你知道错在哪客观题错了经常连为什么错都不知道。我把自己当时记下来的几个高频考点和易错点整理一下。2.1 二叉树遍历与递归栈的底层换算关系客观题里考二叉树最爱考的不只是前中后序遍历的顺序而是给定两种遍历序列能不能唯一确定一棵二叉树。这个题看起来是概念题实际上考递归和分治的理解。前序中序可以唯一确定二叉树后序中序也可以但前序后序不行除非是满二叉树。很多人记反了条件做题时选了前序后序可以唯一确定这就丢了分。理解方式其实很简单中序序列的价值在于把左右子树分开缺少中序就缺少了左右子树的边界信息自然无法唯一还原。用这个逻辑去推就不需要死记结论。还有一道题是二叉树的前序遍历序列为ABCDEF中序遍历序列为CBAEDF求后序遍历。这种题在纸上画一画就能解但关键在于递归栈的理解。你画树的顺序其实就是递归压栈的顺序画错了说明递归没吃透。这类题建议多练几道画到不再出错的熟练度笔试才稳。2.2 哈希冲突、快排复杂度、TCP连接这些经典必考题哈希冲突的考查方式一般是以下哪种方法不能解决哈希冲突——拉链法、线性探测、再哈希、二次探测其中排序是不相关的。还有一种考法是给一个装载因子和一组数据让你算平均查找长度。做这种题别去背公式要理解哈希表的物理结构冲突越多查找链越长性能退化越严重。快速排序的复杂度也是选择题常客。最好情况O(n log n)最坏情况O(n^2)平均O(n log n)。最坏情况什么时候出现每次划分都选到最大或最小元素做基准比如一个已经有序的数组如果用固定基准比如第一个元素那快排会退化成O(n^2)。很多人在这里踩坑。我建议你把基准选择对复杂度的影响吃透这比背复杂度结论有用得多。TCP连接这块几乎每套题都会出现为什么三次握手不能减少为两次。核心原因防止已失效的连接请求突然又传到服务器导致服务器建立错误连接。两次握手做不到这点因为服务器收到SYN后返回ACK就算建立了但此时客户端可能根本没想连。这个逻辑想清楚比背十遍握手流程都管用。2.3 进程线程区别和数据库索引的隐藏考点进程和线程的区别选择题爱考以下描述正确的是四五个选项里混着进程是资源分配的最小单位线程是CPU调度的基本单位同一进程的线程共享地址空间但各自有独立栈之类。你要注意的是线程切换一定比进程切换快这种绝对化表述通常是错的。同一进程内的线程切换确实代价低但不同进程的线程切换照样涉及地址空间切换不具备绝对的快。这类绝对化的选项往往是陷阱。数据库索引考点里B树为什么适合做索引、聚簇索引和非聚簇索引的区别、覆盖索引的概念这几个点反复出现。特别是最左前缀原则2019年那套题考了。很多人知道这个原则但不知道为什么——因为B树的索引结构是按顺序存储的联合索引(a,b)先按a排再按b排所以查b条件用不上索引。你理解了存储顺序这个原则就是顺理成章的事。3. 编程题复盘四道典型题从读题到AC编程题是整套卷子的重头戏也是区分度最大的环节。2019年那套题里的编程题难度阶梯设计得比较合理有保底送分题也有拉开差距的压轴题。我挑几道有代表性的题按照题目描述→思路分析→代码实现→复杂度与边界这条链路完整复盘一下。3.1 最长无重复字符的子串滑动窗口的两种写法这道题很经典LeetCode第3题出现频率极高。题目描述很简单给定一个字符串找出其中不含重复字符的最长子串长度。比如abcabcbb答案是3abc。思路核心是滑动窗口。窗口维护一个范围保证范围内的字符不重复然后右指针不断向右扩展遇到重复字符时左指针跳到重复字符的下一个位置。关键点是用什么数据结构记录字符最后出现的位置——用一个数组或哈希表就能在O(1)时间完成判断。public int lengthOfLongestSubstring(String s) { if (s null || s.length() 0) { return 0; } MapCharacter, Integer lastIndex new HashMap(); int maxLen 0; int left 0; for (int right 0; right s.length(); right) { char c s.charAt(right); if (lastIndex.containsKey(c) lastIndex.get(c) left) { left lastIndex.get(c) 1; } lastIndex.put(c, right); maxLen Math.max(maxLen, right - left 1); } return maxLen; }这里有个细节很多人会漏判断重复时不能只看lastIndex里有没有这个字符还要看它的位置是否在当前窗口内。比如字符串abba遍历到第二个a时lastIndex里确实有a但它的下标0已经不在当前窗口窗口是1~3里了所以不会触发左指针移动。如果少了lastIndex.get(c) left这个条件结果就错了。我自己第一次写的时候就漏了导致abba这种字符串返回3而不是2。还有一种写法是维护一个大小为128的数组ASCII码范围速度更快省去了哈希表的自动装箱开销。笔试环境里用数组更稳因为不会有哈希冲突的常数开销。这个优化在数据量大时差距明显实测100万长度的字符串数组写法比哈希表写法快3倍以上。3.2 按K个一组翻转链表思路清晰不等于代码能一次写对这道题在2019年那套题里属于中等偏上的难度。题目给你一个链表每K个节点一组进行翻转不足K个的保持原样返回翻转后的链表。链表的题特点就是思路不复杂但写起来极易出错。翻转单链表本身是个基础操作但按组翻转就涉及记录每组的前驱和后继、翻转后重新连接这些细节。我当时用的是迭代递归结合的方式写一个辅助函数判断剩余节点够不够K个够的话就翻转这一组然后递归处理下一组。public ListNode reverseKGroup(ListNode head, int k) { if (head null || k 1) { return head; } ListNode curr head; int count 0; while (curr ! null count k) { curr curr.next; count; } if (count k) { return head; // 不足K个直接返回 } // 现在curr指向第K1个节点先翻转前K个 ListNode prev null; ListNode node head; while (node ! curr) { ListNode next node.next; node.next prev; prev node; node next; } // 翻转之后head变成了这一组的尾节点它的next要接到下一组的翻转结果上 head.next reverseKGroup(curr, k); return prev; }这个解法的核心是递归思路每次只翻转当前这一组翻转后把尾节点的next指向下一组的翻转结果。递归的出口是剩余节点不足K个。理解了这个思路代码其实是好写的难的是翻转过程中指针的重新指向。我建议你在白纸上把prev→node→next三步指针移动画一遍画熟了再写代码正确率会高很多。另一种纯迭代写法需要维护一个dummy节点用prevTail记录上一组的尾节点代码更繁琐但避免了递归栈的额外空间。笔试时我推荐递归写法因为逻辑更清晰调试成本低。关于空间复杂度这里递归深度是n/k并不大所以不用太担心。3.3 找出数组里最大的K个数不是所有时候都该用排序笔试里除了链表题还常考这种找最大K个数的题。题目描述给一个无序整数数组和一个整数K返回最大的K个数顺序不限。大多数人第一反应是排序然后取前K个时间复杂度O(n log n)数据量小时没问题。但面试官想看到的通常不是这个解法而是堆或者快速选择。堆的写法维护一个大小为K的最小堆遍历数组如果堆没满就入堆如果堆满了且当前元素比堆顶大就弹出堆顶再入堆。最后堆里就是最大的K个数。时间复杂度O(n log K)空间复杂度O(K)。public int[] findTopK(int[] nums, int k) { if (nums null || nums.length 0 || k 0) { return new int[0]; } PriorityQueueInteger minHeap new PriorityQueue(k); for (int num : nums) { if (minHeap.size() k) { minHeap.offer(num); } else if (num minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } int[] result new int[minHeap.size()]; int i 0; for (int val : minHeap) { result[i] val; } return result; }这里有个容易误解的点为什么用最小堆而不是最大堆。最小堆的堆顶是堆里最小的元素当你想知道这个新元素能不能挤进TopK时只需和堆顶比。如果用最大堆堆顶是最大的元素你没法快速判断新元素是否应该淘汰掉当前的某个元素。这是一个典型的反直觉但正确的设计理解了原理就不会选错。关于快速选择QuickSelect平均时间复杂度是O(n)最坏O(n^2)在数据量极大时比堆更快。但笔试里我建议用堆因为快速选择有个麻烦它是部分排序返回的K个元素是有序的如果题目要求按从大到小返回用快速选择后还得再排一次序反而多一道工序。还有一个重要注意点K的大小和n的关系。如果k接近nTopK问题就变成了排序问题堆的O(n log n)并不比直接排序快多少。笔试里如果题目描述没有特别说明数据规模堆是通用解但如果明确说了n特别大、K特别小堆的方案才是最优解。3.4 岛屿数量图搜索的经典入口题这道题我会特别拿出来说是因为它在校招笔试里出现频率极高而且能一下子看出来一个人是不是真的理解DFS/BFS。题目描述给一个二维网格1表示陆地0表示水域问有多少个岛屿。相邻的陆地上下左右算同一个岛屿。这道题的思想很简单遍历所有格子遇到没访问过的1就计数加一然后从这个格子开始做DFS或BFS把整块连通区域都标记为已访问。核心问题是标记方式。一种方式是维护一个visited数组另一种是直接把访问过的1改成0沉没法。笔试里我推荐直接改值省空间代码也更简洁。public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int rows grid.length; int cols grid[0].length; int count 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } 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; // 沉没当前格子 dfs(grid, i - 1, j); dfs(grid, i 1, j); dfs(grid, i, j - 1); dfs(grid, i, j 1); }递归DFS的缺点是极端情况下整个网格都是1递归栈会非常深可能栈溢出。所以有的笔试环境我会用BFS或显式栈的DFS。BFS用队列模拟层级扩散代码稍长但肯定不会栈溢出。面试官在笔试后评论这道题时常说能把DFS写成BFS且不重不漏的基础通常比较扎实。另外这道题还有一个变种——被围绕的区域LeetCode 130做法是从边界上的O开始反向往内搜索和岛屿数量正好是逆向思维。刷题时把这两个题连着做对DFS/BFS的理解会深不少。4. 笔试实战里的极端边界这些点能让你多拿不少分编程题不是能跑通用例就万事大吉。笔试系统判分的时候除了隐藏的测试用例还会看代码的边界处理能力。如果你的代码在多个测试集上有较好的边界表现往往会比只过了示例用例的人分高。下面是几个我当时踩过之后总结出来的点。4.1 输入边界空值、极端值、溢出几乎每一道编程题都要考虑空输入。字符串要有null的判断和空字符串的判断数组要考虑长度为0的情况链表要考虑null。这些不是锦上添花而是保命的。另一个容易踩的坑是整数溢出。2019年那道字符串转整数题要求写一个atoi函数输入字符串2147483648也就是Integer.MAX_VALUE 1。如果你在累加过程中直接用一个int存结果一累加就溢出了返回值就是错的。正确做法是在累加前判断当前值是否已经大于(Integer.MAX_VALUE - digit) / 10。这个判断在LeetCode第8题里有标准解法笔试里也经常原题变形出现。类似地回文数判断、反转数字、二分查找里的mid (left right) / 2当left和right都很大时可能溢出。更安全的写法是mid left (right - left) / 2。这个细节在二分查找的变种题里非常重要。4.2 时间复杂度优化从能用到够用笔试的测试数据规模往往会比示例大很多。示例里给一个长度100的数组隐藏测试可能给你长度10^6的。所以能跑通示例不等于能AC。我备考时见过最遗憾的一幕是一个同学写了两层循环求最长回文子串示例用例没问题但隐藏用例超时一分都没拿到。判断自己的解法会不会超时可以用一个经验法则1秒运算量大约在10^8左右Java/CPython要再降一个数量级。如果算法复杂度是O(n^2)且n是10^5那运算量是10^10必超时。这时候要么优化成O(n log n)要么换思路。以最长回文子串为例暴力法是两重循环枚举所有子串再判断回文复杂度O(n^3)或O(n^2)。如果你用中心扩展法每个中心点向两边扩展总复杂度O(n^2)n10^4勉强能过如果你用Manacher算法O(n)就能解决。笔试中遇到最长回文类的题建议直接上中心扩展因为Manacher的代码复杂且容易写错中心扩展已经足够应付大多数情况。4.3 输出格式白丢分的重灾区输出格式这件事看着无关紧要实际却能白丢分。笔试系统判题通常是严格比对输出结果多一个空格、少一个换行、末尾多了个逗号都可能判错。我见过最典型的丢分场景是题目要求输出用空格分隔的一组数字但没说行末不能有空格。考生在循环里每个元素后面都输出了一个空格结果最后一位后面也有空格。有些判题系统对行末空格不敏感但有些严格比对直接判错。稳妥的做法是先拼成一个字符串输出时统一处理或者用System.out.print的条件判断控制分隔符。另一个场景是浮点数的精度。题目要求保留两位小数你用System.out.println(value)直接输出可能输出一堆小数位判题系统按字符串比对就错了。正确做法是用String.format(%.2f, value)或DecimalFormat。5. 这套题留给我的备考心得刷题之外的三个经验下面这部分可能有点非主流但我觉得比多刷两道题更有用。都是我真实吃过亏之后总结出来的。第一个经验是做真题的时间分配要提前演练。2019年那套题我记得时间大概是120分钟题目量决定了你不可能每道编程题都花30分钟去仔细打磨。我那时候的策略是拿到卷子先花5分钟把所有题目过一遍把编程题按容易→中等→难排序先做容易的保底再啃中等最后剩下的时间死磕难题。这个策略帮我避免过一道题卡了一个小时后面的送分题都没来得及写的悲剧。第二个经验是编程题要写注释和清晰的变量名。如果你以为笔试只看结果不看代码那就错了。很多公司的笔试系统会有人工复核环节特别是编程题面试官会去看你的代码风格。变量名叫a、b、c和变量名叫left、right、current给人的印象完全不同。我见过有人TopK问题代码写对了但变量名全是a1、a2、a3阅读体验极差面试官评论区直接写了可读性差。这不是能力问题是习惯问题。第三个经验可能有点鸡汤但真的是我体会最深的基础概念和算法题要并行复习不要偏废。我第一年备考就是只顾着刷LeetCode结果客观题丢分严重总分没达到面试线。后来我调整策略每天先花半小时过基础概念再花两小时刷题效果明显好很多。基础概念是压舱石算法题是加分项二者缺一不可。另外笔试和面试是两回事。笔试考的是你会不会面试考的是你懂不懂。笔试里你只要把题AC了哪怕思路有点绕也是满分但面试中你需要讲清楚为什么这么写、有没有更优解。所以笔试可以追求速度和正确率面试前一定要再补一轮思路讲解的练习。我见过好几个同学笔试分数很高但面试时讲不清自己写的代码最后倒在了技术面。最后说一句关于刷题数量的话。很多人纠结我刷了200题够不够刷500题是不是稳了。我的观点是数量本身不是关键关键是你有没有把每道题背后的方法论吃透。滑动窗口、双指针、DFS、BFS、DP、贪心这些套路每个方向刷透十道题比囫囵吞枣刷两百道题有用得多。比如你理解了滑动窗口的窗口什么时候收缩、什么时候扩展这个核心最长无重复子串、最小覆盖子串、字符串排列这些题就都通了。我用这套方法备考下来面对笔试的心态比海量刷题时稳不少。
猿辅导校招笔试题解析：算法与数据结构核心考点全拆解
有人提了猿辅导2019年的校招技术笔试题问我还能不能从里面挖出点东西。说实话一套两三年前的笔试题放到现在具体题目细节肯定有变化但考察的底层能力和出题思路是真的没过时。尤其猿辅导这种在线教育公司业务场景决定了它对算法、数据结构、网络并发这些基本功有比较硬的要求笔试题目出得也相对有区分度。这篇文章我就以那套题为主线把题型结构、高频考点、典型编程题的解法和笔试实战里容易踩的坑一起拆开讲一讲。1. 这套笔试题的题型结构与备考风向先说整体印象。2019年猿辅导校招技术笔试客观题和编程题都有题量不小时间卡得比较紧。整套卷子传递出来的信号很明确它不是在考你会不会背某个API而是在考你在有限时间内能不能把基本功用出来。从题型分布来看大概是这样一个结构模块大致占比考察方向单选题30%左右数据结构、操作系统、计算机网络、数据库基础多选题10%左右某个知识点的多角度理解错选漏选都扣分编程题50%以上链表、字符串、动态规划、图论/搜索简单问答少量场景设计或概念解释比如某个技术方案的取舍为什么是这种结构因为在线教育业务对后端的要求是既要懂业务又要扛得住高并发比如选课高峰期的抢课、直播课的连麦互动、课后作业的实时批改。这些场景往底层拆全是数据结构和网络并发问题。所以笔试里客观题考基础、编程题考算法就是在筛基础扎实、能动手写代码的人。另外有一个容易被忽略的点一套题里往往会有一道场景题它不是纯算法而是给你一个业务场景让你设计方案。猿辅导这类公司很爱出这种题因为能看出你有没有工程思维。2019年的卷子里就有一道关于直播课堂里学生消息的高频推送怎么设计的题虽然乍看是系统设计但落到笔试阶段核心还是在考你对队列、缓冲、协议的理解。这种题没有标准答案考察的是思路是否完整。所以如果你现在准备技术笔试不要只盯着LeetCode刷题还得把基础概念捡起来。我当时备考时走过一个弯路就是觉得算法题刷够了就行结果选择题一道TCP三次握手为什么不是两次都犹豫了半天。这套题给我提了个醒笔试不是算法竞赛它比算法竞赛更看重全面性。2. 客观题里的高频考点这些坑你大概率也踩过客观题看起来简单实际丢分往往比编程题还多。原因是编程题错了你知道错在哪客观题错了经常连为什么错都不知道。我把自己当时记下来的几个高频考点和易错点整理一下。2.1 二叉树遍历与递归栈的底层换算关系客观题里考二叉树最爱考的不只是前中后序遍历的顺序而是给定两种遍历序列能不能唯一确定一棵二叉树。这个题看起来是概念题实际上考递归和分治的理解。前序中序可以唯一确定二叉树后序中序也可以但前序后序不行除非是满二叉树。很多人记反了条件做题时选了前序后序可以唯一确定这就丢了分。理解方式其实很简单中序序列的价值在于把左右子树分开缺少中序就缺少了左右子树的边界信息自然无法唯一还原。用这个逻辑去推就不需要死记结论。还有一道题是二叉树的前序遍历序列为ABCDEF中序遍历序列为CBAEDF求后序遍历。这种题在纸上画一画就能解但关键在于递归栈的理解。你画树的顺序其实就是递归压栈的顺序画错了说明递归没吃透。这类题建议多练几道画到不再出错的熟练度笔试才稳。2.2 哈希冲突、快排复杂度、TCP连接这些经典必考题哈希冲突的考查方式一般是以下哪种方法不能解决哈希冲突——拉链法、线性探测、再哈希、二次探测其中排序是不相关的。还有一种考法是给一个装载因子和一组数据让你算平均查找长度。做这种题别去背公式要理解哈希表的物理结构冲突越多查找链越长性能退化越严重。快速排序的复杂度也是选择题常客。最好情况O(n log n)最坏情况O(n^2)平均O(n log n)。最坏情况什么时候出现每次划分都选到最大或最小元素做基准比如一个已经有序的数组如果用固定基准比如第一个元素那快排会退化成O(n^2)。很多人在这里踩坑。我建议你把基准选择对复杂度的影响吃透这比背复杂度结论有用得多。TCP连接这块几乎每套题都会出现为什么三次握手不能减少为两次。核心原因防止已失效的连接请求突然又传到服务器导致服务器建立错误连接。两次握手做不到这点因为服务器收到SYN后返回ACK就算建立了但此时客户端可能根本没想连。这个逻辑想清楚比背十遍握手流程都管用。2.3 进程线程区别和数据库索引的隐藏考点进程和线程的区别选择题爱考以下描述正确的是四五个选项里混着进程是资源分配的最小单位线程是CPU调度的基本单位同一进程的线程共享地址空间但各自有独立栈之类。你要注意的是线程切换一定比进程切换快这种绝对化表述通常是错的。同一进程内的线程切换确实代价低但不同进程的线程切换照样涉及地址空间切换不具备绝对的快。这类绝对化的选项往往是陷阱。数据库索引考点里B树为什么适合做索引、聚簇索引和非聚簇索引的区别、覆盖索引的概念这几个点反复出现。特别是最左前缀原则2019年那套题考了。很多人知道这个原则但不知道为什么——因为B树的索引结构是按顺序存储的联合索引(a,b)先按a排再按b排所以查b条件用不上索引。你理解了存储顺序这个原则就是顺理成章的事。3. 编程题复盘四道典型题从读题到AC编程题是整套卷子的重头戏也是区分度最大的环节。2019年那套题里的编程题难度阶梯设计得比较合理有保底送分题也有拉开差距的压轴题。我挑几道有代表性的题按照题目描述→思路分析→代码实现→复杂度与边界这条链路完整复盘一下。3.1 最长无重复字符的子串滑动窗口的两种写法这道题很经典LeetCode第3题出现频率极高。题目描述很简单给定一个字符串找出其中不含重复字符的最长子串长度。比如abcabcbb答案是3abc。思路核心是滑动窗口。窗口维护一个范围保证范围内的字符不重复然后右指针不断向右扩展遇到重复字符时左指针跳到重复字符的下一个位置。关键点是用什么数据结构记录字符最后出现的位置——用一个数组或哈希表就能在O(1)时间完成判断。public int lengthOfLongestSubstring(String s) { if (s null || s.length() 0) { return 0; } MapCharacter, Integer lastIndex new HashMap(); int maxLen 0; int left 0; for (int right 0; right s.length(); right) { char c s.charAt(right); if (lastIndex.containsKey(c) lastIndex.get(c) left) { left lastIndex.get(c) 1; } lastIndex.put(c, right); maxLen Math.max(maxLen, right - left 1); } return maxLen; }这里有个细节很多人会漏判断重复时不能只看lastIndex里有没有这个字符还要看它的位置是否在当前窗口内。比如字符串abba遍历到第二个a时lastIndex里确实有a但它的下标0已经不在当前窗口窗口是1~3里了所以不会触发左指针移动。如果少了lastIndex.get(c) left这个条件结果就错了。我自己第一次写的时候就漏了导致abba这种字符串返回3而不是2。还有一种写法是维护一个大小为128的数组ASCII码范围速度更快省去了哈希表的自动装箱开销。笔试环境里用数组更稳因为不会有哈希冲突的常数开销。这个优化在数据量大时差距明显实测100万长度的字符串数组写法比哈希表写法快3倍以上。3.2 按K个一组翻转链表思路清晰不等于代码能一次写对这道题在2019年那套题里属于中等偏上的难度。题目给你一个链表每K个节点一组进行翻转不足K个的保持原样返回翻转后的链表。链表的题特点就是思路不复杂但写起来极易出错。翻转单链表本身是个基础操作但按组翻转就涉及记录每组的前驱和后继、翻转后重新连接这些细节。我当时用的是迭代递归结合的方式写一个辅助函数判断剩余节点够不够K个够的话就翻转这一组然后递归处理下一组。public ListNode reverseKGroup(ListNode head, int k) { if (head null || k 1) { return head; } ListNode curr head; int count 0; while (curr ! null count k) { curr curr.next; count; } if (count k) { return head; // 不足K个直接返回 } // 现在curr指向第K1个节点先翻转前K个 ListNode prev null; ListNode node head; while (node ! curr) { ListNode next node.next; node.next prev; prev node; node next; } // 翻转之后head变成了这一组的尾节点它的next要接到下一组的翻转结果上 head.next reverseKGroup(curr, k); return prev; }这个解法的核心是递归思路每次只翻转当前这一组翻转后把尾节点的next指向下一组的翻转结果。递归的出口是剩余节点不足K个。理解了这个思路代码其实是好写的难的是翻转过程中指针的重新指向。我建议你在白纸上把prev→node→next三步指针移动画一遍画熟了再写代码正确率会高很多。另一种纯迭代写法需要维护一个dummy节点用prevTail记录上一组的尾节点代码更繁琐但避免了递归栈的额外空间。笔试时我推荐递归写法因为逻辑更清晰调试成本低。关于空间复杂度这里递归深度是n/k并不大所以不用太担心。3.3 找出数组里最大的K个数不是所有时候都该用排序笔试里除了链表题还常考这种找最大K个数的题。题目描述给一个无序整数数组和一个整数K返回最大的K个数顺序不限。大多数人第一反应是排序然后取前K个时间复杂度O(n log n)数据量小时没问题。但面试官想看到的通常不是这个解法而是堆或者快速选择。堆的写法维护一个大小为K的最小堆遍历数组如果堆没满就入堆如果堆满了且当前元素比堆顶大就弹出堆顶再入堆。最后堆里就是最大的K个数。时间复杂度O(n log K)空间复杂度O(K)。public int[] findTopK(int[] nums, int k) { if (nums null || nums.length 0 || k 0) { return new int[0]; } PriorityQueueInteger minHeap new PriorityQueue(k); for (int num : nums) { if (minHeap.size() k) { minHeap.offer(num); } else if (num minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } int[] result new int[minHeap.size()]; int i 0; for (int val : minHeap) { result[i] val; } return result; }这里有个容易误解的点为什么用最小堆而不是最大堆。最小堆的堆顶是堆里最小的元素当你想知道这个新元素能不能挤进TopK时只需和堆顶比。如果用最大堆堆顶是最大的元素你没法快速判断新元素是否应该淘汰掉当前的某个元素。这是一个典型的反直觉但正确的设计理解了原理就不会选错。关于快速选择QuickSelect平均时间复杂度是O(n)最坏O(n^2)在数据量极大时比堆更快。但笔试里我建议用堆因为快速选择有个麻烦它是部分排序返回的K个元素是有序的如果题目要求按从大到小返回用快速选择后还得再排一次序反而多一道工序。还有一个重要注意点K的大小和n的关系。如果k接近nTopK问题就变成了排序问题堆的O(n log n)并不比直接排序快多少。笔试里如果题目描述没有特别说明数据规模堆是通用解但如果明确说了n特别大、K特别小堆的方案才是最优解。3.4 岛屿数量图搜索的经典入口题这道题我会特别拿出来说是因为它在校招笔试里出现频率极高而且能一下子看出来一个人是不是真的理解DFS/BFS。题目描述给一个二维网格1表示陆地0表示水域问有多少个岛屿。相邻的陆地上下左右算同一个岛屿。这道题的思想很简单遍历所有格子遇到没访问过的1就计数加一然后从这个格子开始做DFS或BFS把整块连通区域都标记为已访问。核心问题是标记方式。一种方式是维护一个visited数组另一种是直接把访问过的1改成0沉没法。笔试里我推荐直接改值省空间代码也更简洁。public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int rows grid.length; int cols grid[0].length; int count 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } 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; // 沉没当前格子 dfs(grid, i - 1, j); dfs(grid, i 1, j); dfs(grid, i, j - 1); dfs(grid, i, j 1); }递归DFS的缺点是极端情况下整个网格都是1递归栈会非常深可能栈溢出。所以有的笔试环境我会用BFS或显式栈的DFS。BFS用队列模拟层级扩散代码稍长但肯定不会栈溢出。面试官在笔试后评论这道题时常说能把DFS写成BFS且不重不漏的基础通常比较扎实。另外这道题还有一个变种——被围绕的区域LeetCode 130做法是从边界上的O开始反向往内搜索和岛屿数量正好是逆向思维。刷题时把这两个题连着做对DFS/BFS的理解会深不少。4. 笔试实战里的极端边界这些点能让你多拿不少分编程题不是能跑通用例就万事大吉。笔试系统判分的时候除了隐藏的测试用例还会看代码的边界处理能力。如果你的代码在多个测试集上有较好的边界表现往往会比只过了示例用例的人分高。下面是几个我当时踩过之后总结出来的点。4.1 输入边界空值、极端值、溢出几乎每一道编程题都要考虑空输入。字符串要有null的判断和空字符串的判断数组要考虑长度为0的情况链表要考虑null。这些不是锦上添花而是保命的。另一个容易踩的坑是整数溢出。2019年那道字符串转整数题要求写一个atoi函数输入字符串2147483648也就是Integer.MAX_VALUE 1。如果你在累加过程中直接用一个int存结果一累加就溢出了返回值就是错的。正确做法是在累加前判断当前值是否已经大于(Integer.MAX_VALUE - digit) / 10。这个判断在LeetCode第8题里有标准解法笔试里也经常原题变形出现。类似地回文数判断、反转数字、二分查找里的mid (left right) / 2当left和right都很大时可能溢出。更安全的写法是mid left (right - left) / 2。这个细节在二分查找的变种题里非常重要。4.2 时间复杂度优化从能用到够用笔试的测试数据规模往往会比示例大很多。示例里给一个长度100的数组隐藏测试可能给你长度10^6的。所以能跑通示例不等于能AC。我备考时见过最遗憾的一幕是一个同学写了两层循环求最长回文子串示例用例没问题但隐藏用例超时一分都没拿到。判断自己的解法会不会超时可以用一个经验法则1秒运算量大约在10^8左右Java/CPython要再降一个数量级。如果算法复杂度是O(n^2)且n是10^5那运算量是10^10必超时。这时候要么优化成O(n log n)要么换思路。以最长回文子串为例暴力法是两重循环枚举所有子串再判断回文复杂度O(n^3)或O(n^2)。如果你用中心扩展法每个中心点向两边扩展总复杂度O(n^2)n10^4勉强能过如果你用Manacher算法O(n)就能解决。笔试中遇到最长回文类的题建议直接上中心扩展因为Manacher的代码复杂且容易写错中心扩展已经足够应付大多数情况。4.3 输出格式白丢分的重灾区输出格式这件事看着无关紧要实际却能白丢分。笔试系统判题通常是严格比对输出结果多一个空格、少一个换行、末尾多了个逗号都可能判错。我见过最典型的丢分场景是题目要求输出用空格分隔的一组数字但没说行末不能有空格。考生在循环里每个元素后面都输出了一个空格结果最后一位后面也有空格。有些判题系统对行末空格不敏感但有些严格比对直接判错。稳妥的做法是先拼成一个字符串输出时统一处理或者用System.out.print的条件判断控制分隔符。另一个场景是浮点数的精度。题目要求保留两位小数你用System.out.println(value)直接输出可能输出一堆小数位判题系统按字符串比对就错了。正确做法是用String.format(%.2f, value)或DecimalFormat。5. 这套题留给我的备考心得刷题之外的三个经验下面这部分可能有点非主流但我觉得比多刷两道题更有用。都是我真实吃过亏之后总结出来的。第一个经验是做真题的时间分配要提前演练。2019年那套题我记得时间大概是120分钟题目量决定了你不可能每道编程题都花30分钟去仔细打磨。我那时候的策略是拿到卷子先花5分钟把所有题目过一遍把编程题按容易→中等→难排序先做容易的保底再啃中等最后剩下的时间死磕难题。这个策略帮我避免过一道题卡了一个小时后面的送分题都没来得及写的悲剧。第二个经验是编程题要写注释和清晰的变量名。如果你以为笔试只看结果不看代码那就错了。很多公司的笔试系统会有人工复核环节特别是编程题面试官会去看你的代码风格。变量名叫a、b、c和变量名叫left、right、current给人的印象完全不同。我见过有人TopK问题代码写对了但变量名全是a1、a2、a3阅读体验极差面试官评论区直接写了可读性差。这不是能力问题是习惯问题。第三个经验可能有点鸡汤但真的是我体会最深的基础概念和算法题要并行复习不要偏废。我第一年备考就是只顾着刷LeetCode结果客观题丢分严重总分没达到面试线。后来我调整策略每天先花半小时过基础概念再花两小时刷题效果明显好很多。基础概念是压舱石算法题是加分项二者缺一不可。另外笔试和面试是两回事。笔试考的是你会不会面试考的是你懂不懂。笔试里你只要把题AC了哪怕思路有点绕也是满分但面试中你需要讲清楚为什么这么写、有没有更优解。所以笔试可以追求速度和正确率面试前一定要再补一轮思路讲解的练习。我见过好几个同学笔试分数很高但面试时讲不清自己写的代码最后倒在了技术面。最后说一句关于刷题数量的话。很多人纠结我刷了200题够不够刷500题是不是稳了。我的观点是数量本身不是关键关键是你有没有把每道题背后的方法论吃透。滑动窗口、双指针、DFS、BFS、DP、贪心这些套路每个方向刷透十道题比囫囵吞枣刷两百道题有用得多。比如你理解了滑动窗口的窗口什么时候收缩、什么时候扩展这个核心最长无重复子串、最小覆盖子串、字符串排列这些题就都通了。我用这套方法备考下来面对笔试的心态比海量刷题时稳不少。