算法手撕面试题精选
Java 后端真实面试专题 · 算法手撕篇
中大厂（虾皮、BOSS、天猫、爱奇艺、日志易…）现场会让你手写算法。这一篇是真实面经里出现过的高频手撕题，每题三段： ① 思路（怎么想、复杂度）→ ② 关键代码/拓展（写法要点、变体、最优解）→ ③ 它考你什么 / 用在哪。
年限标签：
🟢 3年内🔴 3年+⭐ 手撕题别只背答案，讲清思路 + 复杂度 + 边界，比默写代码更重要。
1. 🔴 一亿个数，找出最大的前 K 个（TopN）
思路：不能全排序（内存放不下、O(nlogn) 浪费）。用小顶堆：维护一个大小为 K 的小顶堆，遍历数据，比堆顶大就替换堆顶。时间 O(n·logK)、空间 O(K)。
关键代码/拓展：
PriorityQueue<Integer> heap = new PriorityQueue<>(); // 小顶堆
for (int x : nums) {
if (heap.size() < k) heap.offer(x);
else if (x > heap.peek()) { heap.poll(); heap.offer(x); }
}
- 数据量超内存：分批/分片读，每片求 TopK，再归并（MapReduce 思想）。
- 找最小 K 个就用大顶堆，反过来。
它考你什么：海量数据处理思维 + 堆的运用。⭐这是 TopN 经典题，几乎大厂必考。可接到项目"实时热销榜 TopN（Redis ZSet）"。
2. 🔴 手写一个 LRU 缓存
思路：LRU（最近最少使用）要 O(1) 的 get/put。用 HashMap + 双向链表：HashMap 存 key→节点（O(1) 查），双向链表按访问顺序排（最近用的放头、淘汰尾部）。
关键代码/拓展：
- get：存在则移到链表头、返回值；put：存在则更新移到头、不存在则插头，超容量删尾。
- Java 偷懒写法：继承
LinkedHashMap，重写removeEldestEntry，构造时 accessOrder=true。
class LRU extends LinkedHashMap<Integer,Integer> {
int cap;
LRU(int cap){ super(cap,0.75f,true); this.cap=cap; }
protected boolean removeEldestEntry(Map.Entry e){ return size()>cap; }
}
- 面试一般要你手写双向链表版，体现你懂原理。
它考你什么：数据结构组合（哈希 + 链表）。⭐高频，且直接对应 Redis 的 LRU 淘汰策略，能往项目引。
3. 🟢 三个线程交替打印，把数字累加到 100（或交替打印 ABC）
思路：线程间协调顺序——用 synchronized + wait/notifyAll 判断"是否轮到自己"，或用 ReentrantLock + 多个 Condition，或 Semaphore 串起来。
关键代码/拓展：
- 核心：每个线程循环里判断"当前该不该我做"，不该就 wait，做完唤醒下一个。
- 变体：交替打印奇偶数、ABC、生产者消费者。
它考你什么：多线程协调/通信（wait-notify、Condition）。⭐能接到"怎么保证多线程有序"这道并发题。
4. 🟢 反转一个链表
思路：双指针迭代——prev、cur，遍历时把 cur.next 指向 prev，逐个反转。时间 O(n)、空间 O(1)。
关键代码/拓展：
ListNode prev = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev; prev = cur; cur = next;
}
return prev;
- 变体：递归反转、反转部分区间、K 个一组反转。
它考你什么：链表指针操作基本功。最基础的手撕题，一定要写得熟。
5. 🟢 两数之和（给数组和目标，找两个数和为 target）
思路：用 HashMap 边遍历边存——对每个数 x，查 map 里有没有 target - x，有就找到，没有就把 x 存入。时间 O(n)。
关键代码/拓展：
Map<Integer,Integer> map = new HashMap<>();
for (int i=0;i<nums.length;i++){
if (map.containsKey(target-nums[i])) return new int[]{map.get(target-nums[i]), i};
map.put(nums[i], i);
}
- 暴力是 O(n²)，用哈希换空间降到 O(n)——典型"空间换时间"。
它考你什么：哈希表的运用、把 O(n²) 优化到 O(n) 的意识。
6. 🟢 统计一组数据里出现频率最高的前 N 个
思路：先用 HashMap 统计每个元素的频率，再用小顶堆取频率 Top N（结合了 TopN）。时间 O(n + m·logN)。
关键代码/拓展：
- map.entrySet 进堆，堆按频率比较，维护大小 N。
- 这就是真实面经里"找最常听的 3 首歌""top5 单词"。
它考你什么：哈希统计 + 堆，是 TopN 的变体。
7. 🔴 二叉树的最近公共祖先（LCA）
思路：递归——从根往下找，如果当前节点是 p 或 q 就返回它；递归左右子树，如果左右都返回了非空，说明 p、q 分别在两侧，当前节点就是 LCA；否则返回非空的那一边。
关键代码/拓展：
TreeNode lca(TreeNode root, TreeNode p, TreeNode q){
if(root==null||root==p||root==q) return root;
TreeNode l=lca(root.left,p,q), r=lca(root.right,p,q);
if(l!=null&&r!=null) return root;
return l!=null?l:r;
}
- 变体：二叉搜索树的 LCA（利用有序性更简单）。
它考你什么：二叉树递归 + 分治思维。
8. 🟢 校验一个字符串/char 数组是否是合法 IPv4 地址
思路：按 . 分成 4 段，校验：① 正好 4 段；② 每段是数字、0~255；③ 没有前导零（"01" 非法）；④ 不为空。
关键代码/拓展：
split("\\.")后逐段判断（注意 split 末尾空串问题）。- 不让用自带 API 时，手动遍历计数点号、逐字符判断。
它考你什么：字符串处理 + 边界考虑（前导零、空段、越界）——边界是这题的坑。
9. 🔴 买可乐：n 元买 n 瓶，2 个空瓶换 1 瓶，n 元能喝几瓶？
思路：模拟——初始 n 瓶，喝完有 n 个空瓶，每 2 个空瓶换 1 瓶继续喝……循环到空瓶不足 2 个。或数学归纳出结果是 2n-1。
关键代码/拓展：
int total=n, empty=n;
while(empty>=2){ int newOne=empty/2; total+=newOne; empty=empty%2+newOne; }
- 数学法：除最后一瓶外每瓶都能"循环"产生价值，结论 2n-1。
- 面试官常要"模拟 + 数学"两种解法。
它考你什么：模拟能力 + 找数学规律。
10. 🟢 冒泡排序 / 快速排序手写
标准答：
- 冒泡：相邻比较交换，每轮把最大的冒到末尾，O(n²)。
- 快排：选基准、分区（小的左、大的右）、递归，平均 O(nlogn)。
// 快排分区核心
void quickSort(int[] a,int l,int r){
if(l>=r)return; int p=partition(a,l,r);
quickSort(a,l,p-1); quickSort(a,p+1,r);
}
拓展：
- 常见排序复杂度、稳定性要记（归并稳定 O(nlogn)、快排不稳定）。
- 快排最坏 O(n²)（有序数组），随机选基准优化。
它考你什么：基础排序 + 复杂度。冒泡几乎送分，快排考分治。
11. 🟢 二分查找
思路：有序数组里查目标，每次比中间值、折半缩小范围，O(logn)。
关键代码/拓展：
int l=0,r=n-1;
while(l<=r){ int m=l+(r-l)/2;
if(a[m]==target)return m;
else if(a[m]<target)l=m+1; else r=m-1; }
return -1;
- 坑：
mid=l+(r-l)/2防溢出；边界<=还是<要想清。 - 变体：找左/右边界、旋转数组查找。
它考你什么：二分边界处理——最容易写错边界的题。
12. 🔴 约瑟夫环：100 人围圈报数，剔除奇数位，循环到剩一人
思路：可以用队列/链表模拟，也可以数学推导。题里"剔除奇数位"反复进行，最后剩下的是 ≤100 的最大 2 的幂（这类"每轮剔一半"的变体规律）。
关键代码/拓展：
- 标准约瑟夫环（每数到 m 出局）有递推公式
f(n)=(f(n-1)+m)%n。 - 用循环链表模拟最直观。
它考你什么：模拟 + 找规律 / 递推。
13. 🔴 36 进制（0-9 a-z）两个数相加
思路：和"字符串大数相加"一样——从末尾对齐逐位相加、处理进位，只是逢 36 进 1，字符和数值要互转（0-9→09，a-z→1035）。
关键代码/拓展：
- 用一个函数做 char↔int 转换，逐位加 + 进位，结果反转。
- 变体：二进制/十进制大数相加、字符串相乘。
它考你什么：进制转换 + 大数模拟 + 进位处理。
14. 🟢 删除链表中值为 n 的节点
思路：用**虚拟头节点（dummy）**简化头节点删除的边界，遍历时 prev.next = cur.next 跳过目标节点。
关键代码/拓展：
ListNode dummy=new ListNode(0); dummy.next=head;
ListNode prev=dummy;
while(prev.next!=null){
if(prev.next.val==n) prev.next=prev.next.next;
else prev=prev.next;
}
return dummy.next;
- dummy 头节点是链表题去边界的通用技巧。
它考你什么：链表操作 + 虚拟头节点技巧。
15. 🟢 一个数组包含 0-9，统计每个数字出现的次数
思路：用一个长度 10 的计数数组，遍历一遍 count[num]++。O(n) 时间、O(1) 空间（桶计数）。
关键代码/拓展：
- 这是"计数排序"的思想，值域小时用桶/计数数组最快。
- 扩展：字符统计用
int[26]/int[128]。
它考你什么：计数/桶思想，值域有限时空间换时间。
16. 🔴 给一亿个数找最大 100 个，用数组还是链表？为什么？
思路：用数组（构建堆）。原因：数组随机访问 O(1)、内存连续、缓存友好，堆操作要频繁按下标访问；链表随机访问 O(n)、有指针开销，不适合。
拓展：
- 这题是 TopN + "数据结构选型"的结合，考你理解数组和链表的本质差异。
它考你什么：数据结构选型的判断力——不只是会写，还要会选。
17. 🟢 判断一个链表是否有环 / 找环入口
思路：快慢指针——慢指针走一步、快指针走两步，相遇说明有环。找入口：相遇后，一个指针回到头、和慢指针同速走，再次相遇点就是环入口。
关键代码/拓展：
ListNode slow=head,fast=head;
while(fast!=null&&fast.next!=null){
slow=slow.next; fast=fast.next.next;
if(slow==fast) return true; }
return false;
- 快慢指针还能求中点、求倒数第 k 个。
它考你什么：双指针技巧（快慢指针）。
18. 🟢 实现一个生产者-消费者模型
思路：用阻塞队列 BlockingQueue 最简单——生产者 put（满了阻塞）、消费者 take（空了阻塞），队列内部已处理同步。手写则用 synchronized + wait/notify 或 ReentrantLock + Condition。
关键代码/拓展：
- BlockingQueue 是首选，体现"用对工具"。
- 手写版考 wait/notify 的正确使用（while 判断、notifyAll）。
它考你什么：并发协调 + 阻塞队列。⭐能接到项目"用阻塞队列做缓冲削峰"。
给学员的手撕题心法
- 先说思路再写代码：讲清解法、复杂度、边界，面试官就知道你会了——很多时候思路对了代码细节面试官不苛求。
- 必背的几道：反转链表、两数之和、二分、快排、TopN（堆）、LRU、快慢指针——这几道覆盖大部分场景。
- 边界是高频扣分点：空输入、单元素、越界、链表头节点、二分的
<=，写完口头过一遍边界。 - 数据结构选型也是考点：TopN 用堆、O(1) 查用哈希、有序查找用二分、缓存用哈希+链表。
你能答到第几层？
- 思路 + 代码 + 边界 + 复杂度都能讲清：中大厂手撕这关你能过。
- 有思路写不利索：多动手写几遍，手撕靠肌肉记忆。
- 没思路：先把上面"必背的几道"练熟，覆盖 80% 场景。
这是面试专题的「算法手撕篇」，网站上还有并发、MySQL、Redis、Spring、微服务、消息队列、JVM、安全认证、Java基础、计基与Linux、设计模式、项目场景等系统整理。 🌐 更多真实面试专题与资料：smallredtech.com 💬 想系统学 / 简历与辅导咨询，加微信：Ahongbb666（备注「面试题」）