刷 LeetCode Hot100 这件事,我前后完整过了三遍。第一遍是照着题解抄,抄完感觉自己懂了,合上题解发现一个字写不出来;第二遍是合上题解自己写,写是写出来了,但提交总是差几个用例,不是边界错就是超时;第三遍是掐着时间先在纸上写伪代码,再上机敲,这一遍才算真正把题吃进去。三遍下来最大的感受是:卡住我的地方往往不是算法思路,而是 Java 的一些细节——Integer用比较翻车、Arrays.asList返回的列表不能add、PriorityQueue忘了写比较器结果大顶堆写成了小顶堆、char和int之间悄悄发生了隐式转换。这些坑题解里基本不会提,但笔试面试现场会让你当场卡壳。这篇笔记就是把两件事放一起整理:一半是 Hot100 里高频题型的思路拆解,讲清楚为什么这一步能省掉一层循环为什么这里该用单调栈而不是双重 for;另一半是 Java 在刷题场景下的易错点和语法积累,把那些平时写业务代码根本遇不到、但算法题里天天出现的东西记下来。适合刚接触算法、打算用 Java 刷 Hot100 的朋友,也适合已经刷过一轮、总觉得会做但写不对的同学。所有代码都是 Java,可以直接复制去跑。1. Hot100 怎么刷才不白刷:先定策略再动手1.1 按题号顺序从头刷,是最容易半途而废的方式Hot100 这个题单的排列顺序大致按知识点归类,但难度并不是单调递增的。前面是哈希和双指针,中间突然插进来一道困难的动态规划,再往后又是相对温和的链表。如果你严格按题号从头刷,大概率会在第 4、5 题附近被卡住,心态一崩就放弃了。我的做法是按知识点聚类重新排一遍:先把同一类题(比如所有滑动窗口)集中刷 5 到 8 道,刷到你能在看到题目的 30 秒内判断出这是滑动窗口为止。这种集中轰炸的好处是,同一类题的套路会互相印证,你会发现最小覆盖子串和找到字符串中所有字母异位词的窗口框架几乎一模一样,区别只在收缩条件和记录答案的时机。具体的执行节奏我建议这样安排:第一天到第二天:集中攻克哈希表、双指针、滑动窗口这三类,加起来大概 15 道题,难度都不高,适合建立信心。第三天到第五天:链表和二叉树。这两类题是手写能力的重灾区,必须真的在编辑器里敲一遍,不能只看。第六天到第九天:动态规划和回溯。这是最耗时间的部分,单道题想不出来很正常,允许自己看题解,但看完必须立刻关掉再写一遍。第十天往后:图论、二分、栈与堆、贪心。这几类题数量少但套路固定,过一遍就行。剩下的时间全部用来二刷和三刷错题。注意:第一遍的目标不是每道题都独立做出来,而是建立题型识别能力。看到一道题能说出这大概是什么类型、该用什么数据结构,第一遍就算合格了。1.2 我给 Hot100 分的四个梯队按通关难度和出现频率,我把 Hot100 里的题粗分成了四个梯队。这个分法不是官方标准,纯粹是我自己刷完之后按面试被问到的概率 × 当场写出来的难度排的:梯队代表的题目类型通关标准建议投入第一梯队:必须闭眼写两数之和、反转链表、有效的括号、合并两个有序链表、二叉树的中序遍历不看题解、5 分钟内写完并一次通过反复默写,直到形成肌肉记忆第二梯队:必须会思路三数之和、无重复字符的最长子串、环形链表、最大子数组和、爬楼梯能说清每一步为什么这么做,代码允许有小瑕疵每题至少手写两遍第三梯队:能讲清楚就行最长递增子序列、单词拆分、岛屿数量、最小栈、LRU 缓存知道用什么方法、时间复杂度是多少理解为主,不必默写全部第四梯队:见过有印象各种困难题、需要组合多种技巧的题能复述核心步骤和关键数据结构过一遍留个印象即可这个梯队表最大的价值是:当你时间不够的时候,你能清楚地知道该放弃什么。很多人刷题的焦虑来源于什么都想会,结果什么都没会。宁可第一梯队 20 道题滚瓜烂熟,也不要 100 道题全是半吊子。1.3 复盘机制:错题本到底要记什么刷题不复盘,等于白刷。但复盘不是把题解抄一遍,那样毫无意义。我的错题本只记三样东西:第一样是卡住的点。比如最长连续序列这题,我卡在怎么做到 O(n)。后来想明白了:关键在于用哈希集合快速判断num - 1是否存在,只有num - 1不存在时,num才可能是某个连续序列的起点。这个只从起点开始枚举的思路,才是这道题真正的考点。第二样是错误的假设。比如我一开始以为盛最多水的容器必须双层循环遍历所有组合,这就是一个错误假设。移动较短的那一侧之所以安全,是因为另一侧的高度已经固定,宽度又只会变小,面积不可能再增加。第三样是Java 层面的坑。这个最容易被忽略,也最容易在面试现场翻车。提示:错题本用纯文本就行,别搞太复杂。每道题两三行,写错在哪、正确的关键是什么就够了。真正值钱的是你写这几行时的思考过程,不是你记了多少字。2. 高频题型思路拆解:从暴力到最优的那一步2.1 哈希表:用空间换时间最划算的战场哈希表类题目的共同特征是:题目里出现了是否存在是否出现过计数这类字眼。看到这些信号,第一反应就该是我能不能用一个额外的 Map 把查找从 O(n) 降到 O(1)。典型的是两数之和。暴力解法是双层循环,O(n²)。用哈希表之后,思路变成:遍历数组,对每个nums[i],先检查target - nums[i]是否已经在表里,不在就把nums[i]存进去。注意这里的顺序很关键——先查再存,能天然避免同一个元素被用两次。public int[] twoSum(int[] nums, int target) { MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int need target - nums[i]; if (map.containsKey(need)) { return new int[]{map.get(need), i}; } map.put(nums[i], i); } return new int[0]; }字母异位词分组是另一个角度。它的关键是找到一个能代表整组字符串的指纹。有两个选择:把字符串排序后的结果作为 key,或者把每个字符出现的次数拼成一个字符串作为 key。前者实现简单但每次都要排序,后者更快但代码稍长。面试时优先写排序版本,除非面试官明确要求优化。最长连续序列则考验你有没有意识到集合的查找是 O(1)这个特性可以用来做跳跃式遍历。这三道题放在一起刷,你会对哈希表的用法形成一个完整认知:它不只是查得快,更重要的是它能帮你把两两比较这种 O(n²) 的结构改造成一次遍历 一次查找。2.2 双指针与滑动窗口:什么时候该想到它双指针的触发信号是:数组有序,或者需要在两端同时做决策。盛最多水的容器是经典的两端收缩。左右指针从两端向中间走,每次移动高度较小的那一侧。我第一次做的时候不理解为什么这样是对的,后来用反证法想通了:如果移动的是较高的一侧,那么新的面积一定不会比原来大——因为宽度变小了,而高度受限于较短的那一侧,并没有变高。所以移动较高的一侧是无用功,只有移动较矮的一侧才有可能找到更大的面积。public int maxArea(int[] height) { int left 0, right height.length - 1, ans 0; while (left right) { int h Math.min(height[left], height[right]); ans Math.max(ans, h * (right - left)); if (height[left] height[right]) { left; } else { right--; } } return ans; }滑动窗口的触发信号是:连续子数组/子串,并且要求满足某个连续区间的性质。窗口的写法有一个固定骨架:int left 0, right 0; while (right n) { // 1. 把 s[right] 加入窗口 // 2. 当窗口不满足条件时,收缩左边界 while (窗口不合法) { // 把 s[left] 移出窗口 left; } // 3. 更新答案 right; }最容易写错的是第二步什么时候收缩和第三步什么时候记录答案。我的经验是:先想清楚窗口代表什么,比如无重复字符的最长子串里,窗口代表的就是当前这段没有重复字符的区间。想明白了这一点,收缩条件自然就出来了——一旦新加入的字符让窗口出现重复,就得一直收缩到重复消失为止。注意:很多人会把窗口写成right在循环体外面,结果死循环。记住right一定要在每一轮外层循环里往前推一格。2.3 链表:指针操作的三个自保动作链表题翻车的原因基本都是空指针和指针丢失。我自己总结了三个自保动作,写链表题之前先在脑子里过一遍:加虚拟头结点。凡是涉及到删除头结点合并两个链表把头插进去这类操作,先在真正的头前面接一个dummy,最后返回dummy.next。这样能省掉一大堆if (head null)的判断。改指针之前先保存 next。这是链表题的核心纪律。比如反转链表,你必须先把cur.next存到一个临时变量里,再改cur.next,否则后半段链就丢了。快慢指针用于找中点和判环。找中点时,快指针每次走两步,慢指针每次走一步,快指针到头时慢指针就在中间。判环时,如果快慢指针能相遇,就说明有环。public ListNode reverseList(ListNode head) { ListNode prev null; ListNode cur head; while (cur ! null) { ListNode next cur.next; // 先保存 cur.next prev; // 再改指针 prev cur; cur next; } return prev; }K 个一组翻转链表是这类题里最能拉开差距的。它的难点在于要处理好不足 K 个怎么办这个边界。我的做法是每次先往后数 K 个,如果数不满就直接返回当前部分,不再翻转。2.4 二叉树:递归三问 迭代写法的必要性二叉树题的递归写法有个万能三问:这个函数要返回什么信息给父节点?当前节点需要用到子节点的什么信息?终止条件是什么(通常是root null时返回什么)?以二叉树的最大深度为例,函数返回的是以当前节点为根的子树最大深度,父节点需要的是两个子树的深度最大值加一,终止条件是空节点返回 0。再比如最近公共祖先,函数的返回值要从深度换成找到的节点。如果左右子树都找到了,说明当前节点就是最近公共祖先;如果只找到一边,就把那一边的结果往上传递。这种返回值的语义变了的题目,正是考察你有没有真的理解递归。但有些题必须会迭代写法,尤其是中序遍历和层序遍历。层序遍历用队列,BFS 模板:public ListListInteger levelOrder(TreeNode root) { ListListInteger ans new ArrayList(); if (root null) return ans; QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int size queue.size(); // 关键:先固定当前层的节点数 ListInteger level new ArrayList(); for (int i 0; i size; i) { TreeNode node queue.poll(); level.add(node.val); if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } ans.add(level); } return ans; }这里的int size queue.size()极其关键。我见过很多人直接写for (int i 0; i queue.size(); i),结果queue.size()在循环里一直在变,导致同一层和下一层混在一起。这是个非常典型的错误。2.5 动态规划:状态定义才是真正的门槛动态规划难的不是写转移方程,而是定义状态。状态定义对了,方程基本自己会浮现;状态定义错了,怎么推都是乱的。我的判断方法是:先问自己这道题在某个阶段需要记住什么信息。爬楼梯需要记住的是走到第 i 阶有几种走法;打家劫舍需要记住的是偷到第 i 家的最大收益;最长递增子序列需要记住的是以 nums[i] 结尾的最长长度——注意这里必须是以 i 结尾,不能是前 i 个里最长的,因为后者无法做转移。以最长递增子序列为例,它的转移方程是:public int lengthOfLIS(int[] nums) { int n nums.length; int[] dp new int[n]; Arrays.fill(dp, 1); int ans 1; for (int i 1; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] Math.max(dp[i], dp[j] 1); } } ans Math.max(ans, dp[i]); } return ans; }注意最后的答案是遍历dp数组取最大值,而不是直接返回dp[n-1]。这个细节很多人第一次写会错。背包类问题(零钱兑换、完全平方数、单词拆分)的关键是物品能不能重复取。能重复取就是完全背包,遍历顺序是正序;不能重复取就是 01 背包,遍历顺序是倒序。这个差别一定要记住,背错方向会导致结果完全错误。2.6 回溯与图论:模板之外的状态恢复回溯的模板非常固定:void backtrack(路径, 选择列表) { if (满足结束条件) { 结果集.add(路径的副本); return; } for (选择 : 选择列表) { 做选择; backtrack(路径, 新选择列表); 撤销选择; } }真正容易出错的是两个地方。第一是路径要传副本。result.add(path)和result.add(new ArrayList(path))差别巨大,前者加进去的是同一个列表的引用,后面path一改,结果集里的内容也跟着变了,最后输出的全是空列表。第二是去重。组合总和 II和子集 II这类题里数组有重复元素,需要先排序,然后在同一层里跳过重复元素:if (i start nums[i] nums[i - 1]) continue;这个i start的判断是精髓:它保证了同一层不重复,同时允许不同层重复(也就是允许[1,1,2]这种组合出现)。图论部分,岛屿数量用 DFS 或者并查集都可以,DFS 写得快;腐烂的橘子是最典型的多源 BFS——一开始把所有腐烂橘子一起入队,而不是一个个单独跑 BFS。多源 BFS 的关键点在于:初始队列里要放多个起点,其他步骤和普通 BFS 完全一样。int[][] dirs {{1,0},{-1,0},{0,1},{0,-1}}; Queueint[] queue new LinkedList(); // 把所有腐烂橘子一次性入队 for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 2) queue.offer(new int[]{i, j}); } }3. Java 易错点实录:那些看起来对但不通过的坑3.1 基本类型与包装类型的相等判断这是 Java 刷题最常见、也最隐蔽的坑。Integer是对象,用比较的是引用地址,不是值。Integer a 127, b 127; System.out.println(a b); // true Integer c 128, d 128; System.out.println(c d); // false原因在于Integer内部有个缓存池,默认缓存-128到127。在这个范围内,Integer.valueOf()返回的是同一个对象;超出范围就会new一个新对象,自然就不相等了。注意:凡是比较两个Integer的值,一律用equals()或者先转成int。更稳妥的做法是直接用int变量接收,避免包装类型参与运算。反过来,如果你在MapInteger, Integer里存值,取出来的是Integer,这时候map.get(x) map.get(y)也是不可靠的。要么用intValue()拆箱,要么用equals()。3.2 集合工具的隐式陷阱Arrays.asList()返回的是一个固定长度的列表,底层还是原数组。你调add()或者remove()会直接抛UnsupportedOperationException。ListInteger list Arrays.asList(1, 2, 3); list.add(4); // 抛异常要一个可变的列表,得包一层:ListInteger list new ArrayList(Arrays.asList(1, 2, 3));还有一个坑是List.of()(Java 9 及以上)返回的也是不可变集合,而且不接受null元素。刷题的时候我一般统一用new ArrayList(),简单可靠,不会踩这种雷。另一个常见问题:HashMap的遍历顺序是不保证的。刷题时如果需要按插入顺序输出,要用LinkedHashMap;如果需要按 key 排序,用TreeMap。3.3 字符串与字符数组的转换String和char[]之间的转换,toCharArray()和new String(char[])是最常规的。但有几个细节要注意。第一,String是不可变的,做题时如果需要频繁修改字符,先转成char[]或者用StringBuilder,不要用s c这种写法,那样每次都会创建新对象。第二,char和int之间的转换是隐式的。1 - 0得到的是数字 1,但1本身打印出来还是字符。这个技巧在处理数字字符串时非常常用,比如把123转成数字 123 可以这样写:String s 123; int num 0; for (char c : s.toCharArray()) { num num * 10 (c - 0); }第三,StringBuilder反向输出用reverse(),但要注意reverse()是就地修改的,没有返回值;如果想拿到反转后的字符串,得再调用toString()。3.4 排序与比较器的写法Arrays.sort()对基本类型数组是升序排的,这个没问题。但对二维数组或者自定义对象排序,就必须写比较器:// 按第一列升序,第一列相同按第二列降序 Arrays.sort(intervals, (a, b) - { if (a[0] ! b[0]) return a[0] - b[0]; return b[1] - a[1]; });这里有个经典陷阱:a[0] - b[0]在数值较大时会溢出。比如a[0] 2_000_000_000,b[0] -2_000_000_000,a[0] - b[0]就溢出了,排序结果会完全错乱。安全的写法是用Integer.compare(a[0], b[0])。PriorityQueue默认是小顶堆。想要大顶堆,要么传Comparator.reverseOrder(),要么写(a, b) - b - a(同样有溢出风险,推荐(a, b) - Integer.compare(b, a))。提示:我在面试里被问过一次为什么 PriorityQueue 的删除是 O(log n) 而不是 O(1),答案是它底层是二叉堆,删除堆顶后要重新调整堆结构。这个知识点顺手记一下。3.5 数值溢出与边界处理刷题时最容易被忽略的就是溢出。几个高频场景:两数相加得负数:int最大值约 21 亿,两个大数相加会溢出。涉及大数运算时用long,或者先用减法判断。二分查找的mid计算:(left right) / 2在left和right都很大时会溢出。标准写法是left (right - left) / 2。这个写法我第一次见到的时候还不理解为什么要这么麻烦,后来算了一下才发现问题。快速幂里的乘法:base * base可能溢出,需要提前取模。边界处理方面,数组题永远要检查:数组为空怎么办?长度为 1 怎么办?全是同一个元素怎么办?二分查找里left right还是left right,也一定要结合具体场景推一遍,不能靠记忆。4. Java 语法积累:刷题顺手补齐的基础4.1 集合框架常用 API 速查刷题高频用到的集合方法,我整理成一张表,背下来能省不少查文档的时间:集合类型常用方法使用场景注意事项HashMapgetOrDefault(k, v)统计计数避免手写containsKey判断HashMapputIfAbsent(k, v)初始化映射已存在时不会覆盖HashSetadd返回 boolean判重返回 false 说明已存在ArrayListget(i)/set(i, v)随机访问下标越界会直接抛异常ArrayDequeofferFirst/pollLast双端操作比LinkedList更快,推荐用PriorityQueueoffer/poll堆结构默认小顶堆,大顶堆要传比较器StringBuilderappend/reverse字符串拼接reverse()无返回值特别说一下ArrayDeque。很多人写栈和队列习惯用Stack和LinkedList,但其实Stack是遗留类,LinkedList作为队列使用时每个节点都有额外的指针开销。ArrayDeque在性能和内存上都更优,官方文档也推荐用它替代Stack。刷题时我一般直接写DequeInteger stack new ArrayDeque();,入栈用push,出栈用pop。4.2 工具类的那些高频静态方法Arrays和Collections这两个工具类刷题时用得非常多,几个必须记住的:Arrays.sort(arr):基本类型数组排序。Arrays.sort(arr, from, to):指定区间排序,左闭右开。Arrays.fill(arr, val):填充整个数组,初始化dp数组时很好用。Arrays.stream(arr).sum():数组求和,但要先确认没有溢出的可能。Collections.sort(list):列表排序。Collections.swap(list, i, j):交换元素,写洗牌算法时常用。还有Math类:Math.max、Math.min、Math.abs、Math.pow。注意Math.pow返回的是double,参与整数运算时一定要显式转成int或long,否则会有精度问题。4.3 语法细节:容易被忽略的那几行刷题时踩过的一些语法小坑,单独记一下:第一,switch语句里的case如果不写break,会一直往下穿透执行。这是新手很容易犯的错误。第二,增强 for 循环里删除元素会抛ConcurrentModificationException。要删除必须用迭代器:IteratorInteger it list.iterator(); while (it.hasNext()) { if (it.next() 0) it.remove(); }第三,final修饰的引用变量,内容可以改,但引用本身不能改。这对理解一些题解里的写法有帮助。第四,泛型不支持基本类型。Listint是错的,必须写ListInteger。这个限制导致装箱和拆箱会带来性能开销,在大数据量场景下要注意。5. 常见问题与调试技巧实录5.1 本地怎么调试算法题我的本地调试流程是这样的:在 IDE 里建一个Main类,把题目要求的Solution类放进去,然后写一个main方法构造测试数据。关键是不要只测题目给的样例,一定要补边界用例。我一般准备三组数据:题目样例、极端小数据(空数组、单个元素)、极端大数据(手写一个长度 10 万的数组跑一遍,看有没有超时)。特别是超时问题,只要在本地跑一次大数据就能提前发现,不用等到提交。如果某道题写完之后结果不对,我的排查顺序是:先打印中间状态(数组、指针位置、dp 表),再逐步缩小范围,最后才怀疑算法思路。顺序不能反,不然很容易在错误的方向上浪费大量时间。5.2 常见报错速查表报错信息常见原因排查方向NullPointerException链表节点或数组元素为 null检查next、left、right是否可能为空IndexOutOfBoundsException下标越界检查循环边界是还是UnsupportedOperationException修改了不可变集合是不是用了Arrays.asList直接 addConcurrentModificationException遍历中修改集合改用迭代器或者收集后再删StackOverflowError递归层数太深改成迭代写法,或者检查递归终止条件Time Limit Exceeded复杂度太高检查有没有可以换成哈希的嵌套循环Wrong Answer边界没覆盖补测空输入、单元素、全相同元素5.3 复杂度的自我检验写完一道题,一定要能说出它的时间和空间复杂度。这个过程不只是应付面试,更是帮你判断这道题有没有更优解。我的自检方法是:先数有几层循环,再看每层循环里有没有隐藏的代价。比如双层循环里如果调用了list.contains(),那是 O(n),总复杂度就变成 O(n³) 了。很多人写出来的代码看起来是两层循环,实际复杂度远超预期,就是因为忽略了隐藏的线性操作。空间复杂度方面,递归的栈深度要算进去。一个写得很漂亮的二叉树递归,空间复杂度可能是 O(h),h是树高,不能简单说成 O(1)。6. 最后再聊两句刷题之外的事Hot100 刷到这个阶段,我最大的体会是:刷题的价值其实分成两层。第一层是题目本身,你学会了哈希、双指针、动态规划这些套路;第二层是解决问题的能力,你学会了怎么把一个模糊的问题拆成输入是什么、输出是什么、中间要维护什么状态。第二层才是真正能迁移到工作里的。我自己在写业务代码的时候,好几次遇到怎么判断两批数据有没有交集这类问题,脑子里第一反应就是能不能用集合把查找降到 O(1)。这种思维习惯,就是刷题刷出来的。再分享一个我自己用着很顺的小方法:每刷完一个知识点,试着不看任何资料,把它讲给一个完全不懂算法的人听。如果你能把滑动窗口讲成一个两只手在绳子上滑动的故事,说明你真的懂了;如果讲着讲着自己卡壳了,那说明这个知识点还有盲区,回去再补一遍。这个方法我用了大半年,效果比单纯重复刷题好得多。还有一点想提醒的是,别把 Hot100 当成终点。它更像是一张地图,告诉你有哪些常见的题型和套路。真正重要的是刷完之后的那个状态——你能不能面对一道完全没见过的新题,冷静地分析它的结构,找到合适的工具。这才是这套题单想训练的东西。
