算法-手撕代码

大类:算法手撕 · 共 80 题 · 检索页定位

手撕题(80)

q174 · 中等

手写 LRU 缓存:实现 LRUCache 类,支持 get(key) 和 put(key, value),要求 get/put 均为 O(1),容量超出时淘汰最久未使用的 key。请写出完整代码(语言不限),并说明你选择的数据结构。

参考答案要点

• 哈希表 + 双向链表:哈希表 O(1) 定位节点,双向链表维护新旧顺序
• get:命中后把节点移到链表头部,未命中返回 -1
• put:key 已存在则更新值并移到头部;不存在则新建节点插入头部,超容量时删除尾部节点并同步删除哈希表项
• 使用 dummy 头尾哨兵节点简化边界处理
• 可说明 Java LinkedHashMap(accessOrder=true) 或 Python OrderedDict 的等价实现
• 复杂度:get/put 均摊 O(1),空间 O(capacity)

来源:[javaguide.cn](https://javaguide.cn/cs-basics/data-structure/lru-cache.html)

q175 · 中等

三个线程分别只负责打印字母 A、B、C,要求按 ABCABCABC... 的顺序交替打印 10 轮。请手写实现(语言不限,至少一种写法),并说明如何避免虚假唤醒。

参考答案要点

• 方案一:synchronized + wait/notifyAll,用共享状态变量 state(0/1/2) 标记轮到谁,条件不满足用 while 循环 wait
• 方案二:ReentrantLock + 三个 Condition,各自 await/signal 实现精准唤醒
• 方案三:Semaphore 链式获取,初始许可数 1、0、0,打印完 release 下一个
• 必须用 while 而不是 if 判断等待条件,防止虚假唤醒
• 加分:说明 wait 会释放锁而 sleep 不会;两线程交替打印 1-100 奇偶数是同一模式

来源:[zhuanlan.zhihu.com](https://zhuanlan.zhihu.com/p/370130458)

q176 · 中等

手写生产者-消费者模型:一个容量为 10 的共享缓冲区,多个生产者放入数据、多个消费者取数据,要求缓冲区满时生产者阻塞、空时消费者阻塞,不能丢数据、不能重复消费。请写出实现并说明唤醒粒度设计。

参考答案要点

• 方案一:ReentrantLock + 两个 Condition(notFull/notEmpty),put 时满则 notFull.await(),放入后 signal(notEmpty)
• 方案二:synchronized + wait/notifyAll,判满判空必须用 while 循环再检查
• 方案三:直接使用 BlockingQueue(ArrayBlockingQueue 的 put/take 自带阻塞语义)
• 缓冲区用循环数组(下标取模)或链表实现
• 两个条件变量分离生产者与消费者的唤醒,减少无效唤醒;notify 可能唤醒同类线程导致死等,所以用 notifyAll 或 Condition
• 能指出检查条件必须在持锁状态下进行(检查与动作原子化)

来源:[smallredtech.com](https://www.smallredtech.com/resources/algorithm-interview)

q177 · 简单

给定单链表头节点,请将链表反转。迭代和递归两种写法都要写出,并分析各自的时间、空间复杂度。

参考答案要点

• 迭代:prev/cur 双指针,先暂存 cur.next,再反转指向,同步后移,最终 prev 为新头节点
• 递归:先递归反转 head 之后的部分,再令 head.next.next = head、head.next = null
• 时间均为 O(n);迭代空间 O(1),递归空间 O(n)(调用栈)
• 边界:空链表、单节点直接返回
• 加分:每 k 个一组反转链表是同一思想的扩展

来源:[nowcoder.com](https://www.nowcoder.com/feed/main/detail/6f1383e872c44029824e6b46d4c97795)

q178 · 中等

给定单链表头节点,判断链表是否有环;如果有环,返回入环节点,没有环返回 null。要求时间 O(n)、空间 O(1)。请写代码并简述入环节点的推导过程。

参考答案要点

• 快慢指针:slow 每次走一步、fast 每次走两步,fast 追上 slow 说明有环,fast 或 fast.next 到 null 说明无环
• 入口推导:设头到入口距离 a、入口到相遇点 b、环剩余 c,由 fast 路程是 slow 两倍推出 a = c + (k-1)(b+c),即一个指针从 head、一个从相遇点同速前进,再次相遇处就是入环节点
• 循环条件 fast != null && fast.next != null 防止空指针
• 全程空间 O(1);对照哈希表记录访问节点法为 O(n) 空间

来源:[zhuanlan.zhihu.com](https://zhuanlan.zhihu.com/p/396239051)

q179 · 中等

给定一个非递减排序数组和一个目标值,返回目标值在数组中的开始位置和结束位置(下标),不存在返回 [-1, -1]。要求时间复杂度 O(log n)。请写出代码,重点说明两次二分的边界处理。

参考答案要点

• 两次二分:一次找第一个大于等于 target 的位置(左边界),一次找第一个大于 target 的位置再减一(右边界)
• 二分模板要统一:左闭右闭配 while(l<=r) 与左闭右开配 while(l<r),mid 收缩写法必须配套
• 中间点写成 l + (r - l) / 2 防止整数溢出
• 找左边界时等于 target 也要继续向左收缩,找右边界时等于则继续向右收缩
• 边界用例:目标不在数组中、目标在数组两端、数组全部等于目标、单元素数组

来源:[smallredtech.com](https://www.smallredtech.com/resources/algorithm-interview)

q180 · 中等

有一个包含 1 亿个整数的大文件,内存放不下全部数据,要找出其中最大的 100 个数。请给出方案并手写核心代码(可先用小规模数组演示),并分析复杂度。

参考答案要点

• 小顶堆方案:维护大小为 100 的小顶堆,新元素大于堆顶则替换并下沉,一遍扫描 O(n log k),内存只需 O(k)
• 说清楚为什么求最大 topK 用小顶堆:堆顶是当前第 100 大,是入围门槛,最小的先被淘汰
• 对照方案:快速选择 partition 平均 O(n) 但要求全量数据在内存,本题不适用,内存够时可用
• 海量文件加分项:哈希取模分桶拆成小文件再逐个堆排/归并(外部归并)
• 边界说明:重复元素、k 为 1 等情况

来源:[smallredtech.com](https://www.smallredtech.com/resources/algorithm-interview)

q181 · 中等

手写线程安全的单例模式,要求给出双重检查锁(DCL)完整写法,并解释为什么实例字段必须加 volatile;再给出一种更简洁的替代写法。

参考答案要点

• 三要素:私有构造器、私有静态实例、公有静态 getInstance
• DCL:第一次判空避免不必要加锁,进入锁后第二次判空防止重复创建
• volatile 原因:防止分配内存-初始化-赋值引用的指令重排,避免其他线程拿到未初始化完成的半成品对象
• 替代写法:静态内部类(借助类加载机制保证线程安全且懒加载)或枚举(天然防反射和反序列化破坏)
• 加分:能对比饿汉/懒汉、说明 CAS 方案

来源:[seven97.top](https://www.seven97.top/algorithms/)

q182 · 中等

给定一个字符串,求其中不含重复字符的最长子串的长度。例如 abcabcbb 的答案是 3(abc),bbbbb 的答案是 1。请写代码并分析复杂度。

参考答案要点

• 滑动窗口:左右指针 left/right 维护当前无重复字符区间
• 哈希表(或数组)记录每个字符最后出现的下标,right 右移遇到重复字符时,left 直接跳到该字符上次出现位置 +1
• left 只前进不回退,整体 O(n) 单趟扫描
• 边界:空串、全部相同字符、全部不同字符
• 对照:暴力双重循环判重 O(n^2) 可作为引入

来源:[zhuanlan.zhihu.com](https://zhuanlan.zhihu.com/p/396239051)

q183 · 简单

将两个升序链表合并为一个新的升序链表并返回新链表头节点。请写出迭代和递归两种实现,并分析复杂度。

参考答案要点

• 迭代:建立 dummy 哨兵节点和尾指针,每次取两链表中值较小者接到尾部,最后把非空残余链表拼上
• 递归:比较两个头节点,较小者的 next 指向其余两个链表合并的递归结果
• 时间 O(n+m);迭代空间 O(1),递归空间 O(n+m) 调用栈
• 边界:其中一个链表为空直接返回另一个
• 加分:合并 k 个升序链表(小顶堆或分治)是其扩展

来源:[zhuanlan.zhihu.com](https://zhuanlan.zhihu.com/p/396239051)

q184 · 简单

用两个栈实现一个队列,支持 push(入队)和 pop(出队)操作。请写出代码,并说明为什么均摊复杂度是 O(1)。

参考答案要点

• in 栈只负责入队,out 栈只负责出队
• pop 时若 out 栈为空,先把 in 栈全部元素倒入 out 栈,顺序即完成反转
• 关键点:只在 out 栈为空时才倒栈,否则会打乱顺序
• 均摊分析:每个元素全程最多经历入栈两次、出栈两次,操作总数与元素数线性相关,均摊 O(1)
• 边界:队列空时 pop 的处理(返回 -1 或抛异常,需说明)

来源:[smallredtech.com](https://www.smallredtech.com/resources/algorithm-interview)

q185 · 中等

给定一个可能包含重复数字的数组,返回其所有不重复的全排列。例如 [1,1,2] 应输出 3 种排列。请写代码,并说明去重剪枝的条件为什么那样写。

参考答案要点

• 回溯框架:路径 + 选择列表 + 撤销选择,used 数组标记已被选的元素
• 去重前提:先对数组排序,让相同数字相邻
• 同层去重剪枝:if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) 则 continue,即同一层跳过重复分支
• 能讲清同层去重与同枝去重的区别(剪的是兄弟分支不是纵向重复使用)
• 复杂度 O(n·n!),收集结果时注意复制路径列表

来源:[zhuanlan.zhihu.com](https://zhuanlan.zhihu.com/p/396239051)

q186 · 简单

给定单链表头节点,删除链表的倒数第 n 个节点并返回头节点,要求只遍历链表一次。请写代码。

参考答案要点

• 建立 dummy 节点指向 head,统一处理删除头节点的边界
• fast 先走 n+1 步,然后 fast/slow 同速前进,fast 到 null 时 slow 恰停在待删节点的前驱
• 执行 slow.next = slow.next.next 完成删除
• 一次遍历 O(n),空间 O(1)
• 边界:n 等于链表长度(删头节点)、链表仅 1 个节点

来源:[smallredtech.com](https://www.smallredtech.com/resources/algorithm-interview)

q187 · 简单

三个窗口同时售卖 100 张票,请手写多线程模拟程序,要求票不超卖、不重复卖(每张票只被卖出一次),并说明你用哪种方式保证线程安全。

参考答案要点

• 共享余票变量的判断与扣减必须放在锁内,保证检查与动作的原子性
• 方案一:synchronized 同步代码块包裹取票逻辑;方案二:ReentrantLock 且在 finally 中 unlock
• 方案三:AtomicInteger 配合循环 CAS,或 getAndDecrement 原子扣减并检查返回值是否大于 0
• 能指出错误示范:ticket-- 非原子,先检查后扣减存在竞态,会超卖或重复卖同一张票
• 输出线程名和票号便于验证正确性

来源:[smallredtech.com](https://www.smallredtech.com/resources/algorithm-interview)

q188 · 中等

手写快速排序,并回答:最坏时间复杂度在什么情况下出现?工程上有哪些常用优化手段?

参考答案要点

• partition 过程:选基准(随机/三数取中/端点),把小于基准的元素换到左侧,返回基准的最终位置
• 递归排序基准左右两段,递归终止条件 left >= right
• 平均 O(n log n),最坏 O(n^2) 出现在数组已有序或逆序且基准固定取端点时
• 优化:随机选基准或三数取中、小区间切换插入排序、三路划分应对大量重复元素
• 空间为递归栈平均 O(log n);能说明快排是不稳定排序

来源:[seven97.top](https://www.seven97.top/algorithms/)

q373 · 困难

手写一个简化版线程池 SimpleThreadPool:构造参数含核心线程数 corePoolSize、最大线程数 maxPoolSize、有界工作队列、非核心线程存活时间;实现 execute(Runnable),语义与 JDK 对齐——线程数小于 core 直接建核心线程,超过 core 入队,队列满且线程数小于 max 再建非核心线程,仍然满则触发拒绝策略。至少实现 AbortPolicy(抛异常)与 CallerRunsPolicy(由提交线程自己执行)两种拒绝策略,并实现 worker 循环取任务与空闲非核心线程的回收。

参考答案要点

• 成员:corePoolSize/maxPoolSize、BlockingQueue<Runnable> workQueue、HashSet<Worker>、AtomicInteger workerCount;Worker 实现 Runnable,持有 firstTask,run() 里循环取任务执行
• execute 三步:workerCount < core → addWorker(task, core=true);入队 offer 失败且 workerCount < max → addWorker(task, false);再失败 → handler.rejectedExecution(task)
• worker 循环:firstTask 或 getTask();getTask 里核心线程用 workQueue.take() 永久等,非核心线程用 poll(keepAliveTime, NANOSECONDS),拿不到返回 null,worker 退出并从集合移除——这就是线程回收
• 拒绝策略:Abort 抛 RejectedExecutionException;CallerRuns 直接 task.run(),用提交线程反压降速;可再补 DiscardOldest(丢队首再入队)
• 细节加分:线程命名(ThreadFactory)、shutdown 后拒绝新任务、UncaughtExceptionHandler;追问 JDK 真实实现的 ctl 高位状态位(RUNNING/SHUTDOWN/STOP/TIDYING/TERMINATED)与 int 打包设计
• 复杂度:提交 O(1),队列操作取决于所选 BlockingQueue

来源:[javaguide.cn](https://javaguide.cn/java/concurrent/java-thread-pool-summary.html)

q374 · 困难

手写有界阻塞队列 MyBlockingQueue<T>(对齐 ArrayBlockingQueue 语义):内部用数组 + ReentrantLock + 两个 Condition(notFull/notEmpty),实现 put(满则阻塞等待)、take(空则阻塞等待)、offer(e,timeout,unit) 与 poll(timeout,unit) 带超时版本。回答:为什么需要两个 Condition 而不是一个、为什么判满判空用 count 而不是比较头尾下标、对比 Object 的 wait/notify 实现有什么缺陷。

参考答案要点

• 结构:Object[] items, int putIndex/takeIndex/count;final ReentrantLock lock;Condition notFull=lock.newCondition(), notEmpty=lock.newCondition()
• put:lock.lock() → while(count==items.length) notFull.await();入队 putIndex 环形前进、count++、notEmpty.signal() → finally unlock;take 完全对称(await 防虚假唤醒必须用 while)
• 两个 Condition 的意义:生产者等 notFull、消费者等 notEmpty,精确唤醒异类;单 Condition 的 notify 只能随机唤醒,notifyAll 又有惊群——notify 唤醒了同类线程会丢失唤醒导致死锁
• count 判满空是 O(1) 且语义清晰;若只靠 (putIndex+1)%n==takeIndex 无法区分满与空(除非牺牲一个槽位)
• 超时版用 awaitNanos 返回剩余时间,超时返回 false/null;延伸:这就是生产者消费者的基础设施,对比 LinkedBlockingQueue 两把锁读写分离的吞吐差异

来源:[javaguide.cn](https://javaguide.cn/java/concurrent/java-concurrent-collections.html)

q375 · 中等

两个线程交替打印 1~100:线程 A 只打印奇数、线程 B 只打印偶数,要求输出严格为 1,2,3,...,100。给出至少两种实现(如 synchronized+wait/notify 与 Semaphore,鼓励再写 ReentrantLock+Condition),对比两种写法的唤醒粒度与开销,并说明如何防虚假唤醒、最后一轮如何避免对方线程永久等待。

参考答案要点

• 方案一 synchronized+wait/notify:共享锁对象,循环体 while(count 判断:不归我打 || count>100) lock.wait();打印后 count++、notifyAll();while 而不是 if 是防虚假唤醒的标准写法
• 方案二 Semaphore:oddSem 初始 1 个许可、evenSem 初始 0;打印前 acquire 自己的信号量,打印后 release 对方的——无锁竞争、精确唤醒、吞吐最好
• 方案三 ReentrantLock + odd/even 两个 Condition,精确 signal 对应条件队列,原理与信号量等价,更贴近 JUC 风格
• 终止防死锁:count 超过 100 后必须 notifyAll(或 release 对方)让另一线程也能走到退出判断,否则它永远 wait
• 复杂度均为 O(n) 次打印;追问扩展:三线程按 ABCABC 打印、多线程循环打印就是同一模板多条件;自旋 volatile+CAS 版可写但忙等浪费 CPU

来源:[javaguide.cn](https://javaguide.cn/java/concurrent/java-concurrent-questions-01.html)

q376 · 中等

手写两种公认最优的线程安全单例:静态内部类(Holder)模式与枚举模式,说明两者如何同时做到懒加载与线程安全;再演示如何用反射破坏普通私有构造的单例(setAccessible 调用私有构造器),枚举为什么反射不了;序列化反序列化为什么会破坏单例、readResolve 如何防住。

参考答案要点

• 静态内部类:getInstance() 首次调用才触发 Holder 类初始化,JVM 保证 <clinit> 在类锁下只执行一次——天然懒加载+线程安全,不加 volatile 也不怕重排
• 枚举:enum Singleton { INSTANCE; } JVM 保证枚举实例唯一,Effective Java 推荐写法,一行都不用写同步
• 反射破坏:Constructor.setAccessible(true).newInstance() 可对普通私有构造类反复建实例;防御可私有构造里加已存在即抛异常;对枚举,反射 Constructor.newInstance 检查到 ENUM 修饰直接抛 IllegalArgumentException——反射不了
• 序列化破坏:反序列化不走构造器会生成新对象;实现 readResolve() 返回 INSTANCE 防住;枚举反序列化天然走 valueOf 不破坏
• 对比 DCL:DCL 必须 volatile(分配→初始化→赋引用可能重排暴露半初始化对象);追问:静态内部类Holder 与 DCL 的使用取舍

来源:[javaguide.cn](https://javaguide.cn/java/concurrent/java-concurrent-questions-01.html)

q377 · 困难

手写 LFU 缓存(LRU 的进阶版,LeetCode 460):实现 get/put 均摊 O(1),容量满时淘汰访问频次最低的 key,频次相同淘汰最久未使用的。要求用频次桶思路:每个频次一条双向链表,配合 minFreq 指针;也允许给出 TreeMap/堆的 O(log n) 解法并说明取舍。

参考答案要点

• 数据结构:HashMap<K,Node> keyMap;HashMap<Integer,DoubleLinkedList> freqMap(频次→桶);全局 minFreq;Node 含 key/value/freq
• get:命中 → 从 freq 桶摘出,freq+1 放入下一桶;若原桶空且 minFreq==freq 则 minFreq++;未命中返回 -1
• put:已存在则更新值并升频(同 get);不存在且满 → 删 minFreq 桶的尾节点(同频次按 LRU),再以 freq=1 插入并把 minFreq 重置为 1
• 复杂度:全 O(1);O(log n) 备选:TreeMap<freq, LinkedHashMap> 或堆按(freq,时间)序,代码短但不是最优解,面试要能说清取舍
• 追问:LFU 缺点——历史高频 key 长期占坑,新热点进不来;老化方案(周期性整体频次衰减或新 key 初始频次加权),Redis 的 LFU 就用了 lfu-log-factor 衰减

来源:[leetcode.cn](https://leetcode.cn/problems/lfu-cache/)

q378 · 中等

手写单机令牌桶限流器 TokenBucketRateLimiter:构造传入容量 capacity 与速率 rate(个/秒),实现 tryAcquire(n)——令牌不足 n 返回 false 不阻塞不等待。要求不启动后台线程刷新令牌(用惰性计算:记录上次补充时间,取令牌时按流逝时间一次性补充,上限 capacity);说明它与漏桶算法的区别,以及为什么令牌桶允许突发流量。

参考答案要点

• 字段:capacity、rate、double tokens、long lastRefillNanos;线程安全用 synchronized 或 AtomicReference+CAS 整体更新状态
• tryAcquire:now 距上次补充的 elapsed 秒数;tokens = min(capacity, tokens + elapsed*rate);若 tokens >= n 则 tokens-=n、更新 lastRefill 并返回 true,否则返回 false(不预支)
• 无后台线程的关键:把『持续生成』转化为『按需按时间差补发』,任何时刻的令牌数都可由公式推出,省一个定时线程且无并发刷新问题
• 与漏桶对比:漏桶请求以恒定速率流出(整流,输出绝对平滑);令牌桶恒速生成但可积攒,桶满时瞬间可通过 capacity 个请求——允许突发到桶容量,适合应对毛刺流量
• 延伸:Guava RateLimiter 就是令牌桶(SmoothBursty/SmoothWarmingUp);分布式版用 Redis+Lua 原子执行补发+扣减;对比固定窗口(临界突刺)与滑动窗口

来源:[javaguide.cn](https://javaguide.cn/high-availability/limit-request.html)

q379 · 困难

手写一致性哈希:构造 2^32 的哈希环,对节点与 key 分别取哈希落到环上,key 顺时针找最近的节点;实现 addNode/removeNode,并说明增删节点影响的数据范围;为解决数据倾斜,为每个物理节点映射 vNum 个虚拟节点。用 TreeMap 实现环上的顺时针查找,并说明与 Redis Cluster 哈希槽方案的对比。

参考答案要点

• 结构:TreeMap<Long,String> ring;addNode:对 node#i(i<vNum)计算哈希(FNV/MurmurHash 或 md5 取 long)put 进环;removeNode 删除该节点全部虚拟节点;权重可通过虚拟节点数体现
• getNode(key):hash = h(key);tailMap(hash) 非空取 firstKey,空则取 ring.firstKey()(环回),单次 O(log n)
• 性质:增删一个节点只影响环上它逆时针到前一节点区间的 key,迁移量约 1/N;普通 hash%N 扩容全量洗牌——这正是缓存集群扩缩容要一致性哈希的原因
• 虚拟节点:vNum 越大分布越均匀(常取 150~200),同时缓解节点宕机时压力全部顺移给下一跳的雪崩问题
• 对比:Redis Cluster 用 16384 个预分片槽,槽与节点映射可显式迁移,运维可控性更强;追问:key 倾斜监控、有界负载一致性哈希

来源:[xiaolincoding.com](https://www.xiaolincoding.com/os/8_network_system/hash.html)

q380 · 中等

手写简化布隆过滤器:一个 bit 位数组(long[] 自实现或 BitSet)+ k 个哈希函数(可用双重哈希 h_i(x)=h1(x)+i*h2(x) 生成 k 个位置),实现 add(x) 与 mightContain(x)。回答:为什么判断不存在一定准确、判断存在可能误判;误判率与哪些参数有关、给定 n 和目标误判率 p 如何反推 m 和 k;为什么标准布隆不支持删除,计数布隆和布谷鸟过滤器如何解决。

参考答案要点

• add:对 i in 0..k-1 计算 idx_i 并置位;mightContain:k 个位全为 1 才返回可能存在,任一位为 0 必然不存在(位只会被置 1 不会撤销,单向性决定不存在判断绝对可靠)
• 误判率 p ≈ (1 - e^(-kn/m))^k;最优 k = (m/n)ln2;由 n 与 p 反解 m = -n·lnp/(ln2)^2、k = (m/n)ln2——能写出公式推导是加分项
• 双重哈希技巧:两个独立哈希 h1/h2 线性组合出 k 个位置,避免维护 k 个独立哈希函数
• 不支持删除:多个元素共享位,清 0 一个位会连带误杀其他元素;计数布隆把每格换成 counter(空间×4 且可能溢出);布谷鸟过滤器支持删除、空间更优但有装填上限与踢出放大
• 应用:缓存穿透拦截、爬虫 URL 去重、海量黑名单 O(k) 判定;工程用 Guava BloomFilter 或 RedisBloom;追问:容量满后误判率上升的重建策略

来源:[javaguide.cn](https://javaguide.cn/cs-basics/data-structure/bloom-filter.html)

q381 · 中等

手写归并排序两个版本:递归版(分半→左右递归→merge 双指针借助临时数组)与自底向上非递归版(step 从 1 倍增,两两归并相邻段)。说明为什么归并最好最坏都是 O(n log n)、为什么是稳定排序、空间复杂度是多少;并回答:链表排序为什么首选归并而不是快排(LeetCode 148),链表版 merge 怎么写。

参考答案要点

• 递归版:mid=(l+r)>>1;递归排 [l,mid]、[mid+1,r];merge:双指针逐个取小放 temp,相等时取左半段——这是稳定性的来源;最后拷回原数组
• 非递归版:for step=1; step<n; step*=2,对每对 [i, i+step-1] 与 [i+step, min(i+2*step-1,n-1)] 归并;无递归栈、可先块内插入排序优化小段
• 复杂度:T(n)=2T(n/2)+O(n) 主定理得严格 Θ(n log n),与输入分布无关(快排最坏 O(n^2));空间 O(n) 临时数组(原地归并可省但不实用)
• 链表 LC148:快慢指针找中点断链,递归归并两段;链表 merge 只改 next 指针无需 temp 数组,空间 O(log n) 递归栈;链表不支持随机访问导致快排 partition 退化 O(n^2) 且 pivot 选取低效
• 延伸:外部排序——大文件按内存分块排序后 k 路归并(堆或败者树),复杂度 O(n log k);Java 对象排序 Collections.sort 用 TimSort(归并+插入混合)保稳定性

来源:[leetcode.cn](https://leetcode.cn/problems/sort-list/)

q382 · 困难

二分变体二连:(1) 旋转排序数组搜索(LC33,元素互不相同):说明如何用 nums[l] 与 nums[mid] 的比较判断哪半段有序、目标是否落在有序半段内,从而每轮安全收缩一半;(2) 寻找峰值元素(LC162):说明为什么比较 nums[mid] 与 nums[mid+1] 往更大一侧收缩必定收敛到一个峰值。最后总结:二分适用的本质条件是什么。

参考答案要点

• LC33:mid 把数组切成一段有序+一段含旋转点;if(nums[l]<=nums[mid]) 左半有序 → 目标在 [nums[l], nums[mid]) 区间则 r=mid-1 否则 l=mid+1;else 右半有序对称处理;每轮 O(log n)
• LC33 陷阱:判断有序要用 nums[l]<=nums[mid](相等时单元素段也算有序);LC81 有重复元素时相等无法判方向只能 l++,退化 O(n)
• LC162:nums[mid]>nums[mid+1] 处在下坡,峰值在含 mid 的左侧 → r=mid;反之 l=mid+1;因为边界视为 -∞,沿更大方向爬必有峰,二段性成立
• 本质总结:二分不要求整体有序,只要求搜索空间上存在一个判定谓词使其具有二段性(一半满足一半不满足),答案在分界点——lower_bound、旋转数组最小值(LC153)都是实例
• 复杂度均 O(log n)、O(1) 空间;面试先说不变量(l/r 的开闭区间含义)再写代码,边界用 l<=r 或 l<r 要与收缩逻辑配套

来源:[leetcode.cn](https://leetcode.cn/problems/search-in-rotated-sorted-array/)

q383 · 中等

三数之和(LeetCode 15):数组中找出所有满足 a+b+c=0 的不重复三元组。要求排序+固定一个数+左右双指针 O(n^2) 解法,重点讲清楚三层去重分别在哪里做(枚举的第一层、命中后左右指针的跳过),以及为什么不用哈希法;并扩展说明四数之和(LeetCode 18)如何加一层循环与剪枝。

参考答案要点

• 主流程:数组排序;for i 固定 nums[i],l=i+1、r=n-1;sum>0 则 r--,sum<0 则 l++,==0 收集三元组后双指针同时内移继续找
• 去重三层:i>0 且 nums[i]==nums[i-1] 时 continue(同层第一个数重复);命中后 while(l<r && nums[l]==nums[l+1]) l++,nums[r] 同理跳过,再 l++/r--;l 的起点天然随 i 移动,无需与 i 去重
• 剪枝:排完序若 nums[i]>0 直接 break(后面全正);可加 i 层最小和>0 break、最大和<0 continue
• 复杂度:排序 O(n log n)+ 外层 O(n)×双指针 O(n)=O(n^2),空间 O(1);哈希法找两数之和需额外集合去重,常数更大且无法利用排序的双指针剪枝
• 四数之和:两层循环(i,j)+双指针 O(n^3);注意剪枝要用当前数判断不能用 target 正负直接 break(target 可为负);变体 LC16 最接近三数之和维护 diff

来源:[leetcode.cn](https://leetcode.cn/problems/3sum/)

q384 · 困难

最小覆盖子串(LeetCode 76):返回 s 中涵盖 t 所有字符(含重复次数)的最短子串。要求滑动窗口:右指针扩张直到窗口满足,再左指针收缩到极限并记录候选答案,如此反复;用计数而非每步全量比对实现 O(1) 的窗口合法性判定。说明整体为什么是 O(|s|+|t|),并说明该模板如何迁移到无重复最长子串、至多 K 种字符的最长子串。

参考答案要点

• 状态:needMap(t 各字符需要次数)、windowMap、valid(窗口内次数已达标的字符种数)、needKind(需求种数);用 int[128] 代替 HashMap 提速
• 右扩:字符计数进窗;若该字符窗口计数恰好等于需求则 valid++;valid==needKind 时窗口第一次满足,进入收缩
• 左缩:左端字符是必需字符且移出后数量将不达标 → valid-- 破坏前记录答案(此刻 [l,r] 是以 r 结尾的最短合法窗);移出后 l++ 继续找下一个候选
• O(1) 判定靠 valid 计数维护,不需要每步遍历 needMap;左右指针各单向前进,总复杂度 O(|s|+|t|)
• 模板迁移:无重复最长子串=收缩条件改为出现重复;至多 K 种字符=收缩条件改为种类超 K;方向相反(求最短在满足后收缩,求最长在不满足时收缩)——能讲清这个对偶是加分项

来源:[leetcode.cn](https://leetcode.cn/problems/minimum-window-substring/)

q385 · 困难

N 皇后(LeetCode 51):在 N×N 棋盘放置 N 个皇后使其互不攻击(不同行、不同列、不同两条对角线),返回所有摆法。要求按行递归回溯,每行枚举列,用三个标记数组(列、主对角线 row-col+N、副对角线 row+col)做 O(1) 剪枝;写出回溯框架与撤销逻辑,再给出位运算优化版(三个位图的移位传播),分析搜索树规模。

参考答案要点

• 回溯框架:dfs(row):row==n 时把棋盘转字符串收集;for col in 0..n-1:cols[col]、diag1[row-col+n]、diag2[row+col] 均未占用 → 放置并置标记、dfs(row+1)、撤销标记(选择-递归-撤销三步)
• 按行递归天然保证每行一个皇后,冲突检查只剩列与两条对角线;同主对角线 row-col 恒定(加 n 防负下标),同副对角线 row+col 恒定;标记数组让判定 O(1) 而非每步扫棋盘 O(n)
• 位运算版:三个 int 位图 cols、leftDiag、rightDiag;可用位置 = ~(cols|ld|rd) & fullMask;lowbit=x&-x 取最低可用列递归,ld、rd 随行左移/右移一位把斜线冲突传播到下一行;只求方案数时可按列对称剪半
• 复杂度:排列树上界 O(n!),实际剪枝后远小(8 皇后 92 组解);空间 O(n) 递归栈+标记
• 迁移:与全排列、数独求解器、括号生成同属回溯模板;面试追问终止剪枝、解的构造格式(board vs 坐标列表)

来源:[leetcode.cn](https://leetcode.cn/problems/n-queens/)

q386 · 中等

数组中第 K 个最大元素(LeetCode 215):要求两种方法都写——(1) 维护大小为 K 的小顶堆,遍历数组,比堆顶大则弹出压入,结束堆顶即答案;(2) 快速选择 quickselect:partition 后只递归包含第 n-k 位的一侧。给出两者复杂度与最坏情况,说明什么场景选堆、什么场景选快选,以及如何规避快选最坏 O(n^2)。

参考答案要点

• 堆解:PriorityQueue<Integer> 小顶堆,offer 后超 K 则 poll;元素比堆顶大才 offer 可少做操作;O(n log k) 稳定,空间 O(k)——海量数据、流式、分布式的必选(TopK 内存放不下时)
• 快选:随机或三数取中选 pivot,partition 得落位 idx;idx==n-k 命中返回;idx<n-k 只递归右侧,否则只递归左侧——期望 T(n)=T(n/2)+O(n)=O(n)
• 快选最坏 O(n^2) 出现在数组已近似有序且 pivot 固定取端点;随机化或三数取中把最坏压到概率意义上极小;BFPRT(中位数的中位数)可保证最坏 O(n) 但常数大,工程少用
• 陷阱:Integer 拆箱比较用 == 出错、重复元素含在 K 计数里、partition 双指针相等元素死循环(交换前判断 l<r)
• 选型口诀:全内存一次性查询→快选平均更快;要 TopK 列表本身、数据流式或外部数据→堆;面试先写堆保底再优化到快选

来源:[leetcode.cn](https://leetcode.cn/problems/kth-largest-element-in-an-array/)

q387 · 中等

合并区间(LeetCode 56):给定若干闭区间,合并所有重叠的返回。要求按左端点排序后线性扫描:当前区间左端点不超过上一个结果区间的右端点即重叠,右端点取 max 合并。说明为什么合并时必须取 max 而不是直接沿用后者的右端点(给反例),复杂度瓶颈在哪;并简述插入区间(LeetCode 57)与区间列表交集(LeetCode 984)怎么做。

参考答案要点

• 流程:Arrays.sort(intervals, 按左端点);维护 last=[start,end] 扫描:cur[0] <= last[1] → last[1]=max(last[1], cur[1]);否则输出 last 并令 last=cur;结尾补 last
• 取 max 的反例:[1,10] 与 [2,3] 重叠,合并结果应为 [1,10];若直接用后者的右端点 3 会错误截短——嵌套区间是经典陷阱
• 复杂度:排序 O(n log n) 主导,扫描 O(n);空间 O(n) 存结果
• LC57 插入区间:新区间先吸收所有与其相交的旧区间(取 min/max 扩张),再按左端点拼接前后不交部分
• LC984 交集:双指针各指两个列表,取 [max(l1,l2), min(r1,r2)] 若有效则收集;谁的右端点小谁前进;追问会议室 II(结束时间小顶堆)与本题组合
• 追问:区间数巨大时的外部排序合并思路

来源:[leetcode.cn](https://leetcode.cn/problems/merge-intervals/)

q388 · 困难

手写简易 JSON 解析器:输入 JSON 字符串,输出 Map/List/String/Double/Boolean/null 组成的对象树。要求支持 object、array、string(处理 "、\、\n、\uXXXX 四类转义)、number(整数、负数、小数、科学计数法)、true/false/null;跳过前后空白,非法输入抛出带位置的异常。说明递归下降的整体结构与 number 解析的坑。

参考答案要点

• 结构:类内持 String src 与 int pos;parseValue 按 peek 分发:'{' → parseObject、'[' → parseArray、'"' → parseString、't/f/n' 匹配字面量、其余 parseNumber;每个入口先 skipWhitespace
• parseObject:跳 '{';peek '}' 直接返回空 Map;循环 parseString 取 key → 期望 ':' → parseValue 取 value → 遇 ',' 继续、遇 '}' 结束;parseArray 对称
• parseString:StringBuilder 拼接,读到非转义 '"' 结束;'\' 后按映射二次分发:" \ \n \t \r \b \f;\uXXXX 用 Integer.parseInt(hex,16) 转 char(注意代理对可后续处理)
• parseNumber 的坑:负号、小数点、e/E 可带正负号;简化版可把连续数字字符收集后 Double.parseDouble,注意 1e5、-0.5、前导零;严格版要按 JSON 语法逐字符验证
• 错误处理统一 ParseException(当前位置+期望字符);追问:深嵌套防栈溢出(改显式栈)、序列化 toString 的对称实现、与 Jackson 流式解析的对比;复杂度 O(n)
• 回答要点:解析器=「词法(字符消费)+递归下降文法(每个产生式一个函数)」,能把文法写出来再翻译成代码就是满分

来源:[json.org](https://www.json.org/json-zh.html)

q389 · 中等

用 Java 模拟 Redis 的过期 key 删除策略:实现一个 MiniRedis,put(key, value, ttlSeconds) 同时把绝对到期时间写入过期字典;实现两种删除——惰性删除:get 时先查过期字典,已过期立即删除并返回 null;定期删除:后台线程每 100ms 从带 TTL 的 key 里随机抽 20 个检查,删除已过期的,若过期占比超过 25% 立即再抽一轮。说明为什么 Redis 不用定时删除,以及过期删除与内存淘汰策略(maxmemory)的区别。

参考答案要点

• 数据结构:ConcurrentHashMap<String,String> data + ConcurrentHashMap<String,Long> expireAt(存绝对时间戳);put 同时写两表,put 不带 ttl 时清除过期记录
• 惰性删除:getKey 先查 expireAt,now >= 到期时间 → 同时删两表并返回 null;优点零额外 CPU,缺点过期冷 key 一直占内存
• 定期删除:循环随机抽 20 个带 TTL 的 key,删除其中已过期的并统计;expired/抽样数 > 25% 时立即再来一轮,否则退出等下个 100ms——控制每轮耗时上限,防止阻塞
• 为什么不用定时删除(每 key 一个定时器):到期即删内存最省,但海量定时器频繁触发抢占 CPU;惰性+定期是 CPU 与内存的折中,这是 Redis 官方取舍
• 与内存淘汰的区别:过期删除只清理设定了 TTL 且到期的 key;内存达到 maxmemory 后的淘汰(noeviction/allkeys-lru/allkeys-lfu/volatile-* 等)是在全局或带 TTL 的 key 里选牺牲者释放空间;手写定期删除时可顺带演示随机近似 LRU

来源:[xiaolincoding.com](https://www.xiaolincoding.com/redis/module/strategy.html)

q390 · 中等

用 ReentrantReadWriteLock 实现线程安全本地缓存 ReadWriteCache<K,V>:读走读锁、写走写锁;重点实现缓存更新时的锁降级——写线程拿到写锁、查库更新缓存后,先获取读锁再释放写锁,完成后续读操作后释放读锁。解释不降级会出什么问题、为什么支持降级不支持升级;说明读写锁的适用前提与 StampedLock 乐观读如何进一步优化。

参考答案要点

• 基础结构:ConcurrentHashMap<K,V> map + ReentrantReadWriteLock rwlock;get:读锁加锁 → map.get → 解锁;put:写锁加锁 → map.put → 解锁;读读共享、读写与写写互斥
• 锁降级标准流程:wlock → 查 DB → 更新缓存 → rlock(先拿读锁!)→ wunlock → 基于缓存做计算/返回 → runlock;若先放写锁,另一写线程可能立刻改写缓存,本线程后续读到不一致中间态
• 降级可行、升级死锁:写锁内可再获取读锁(JMM 支持并保证可见性);两个读线程同时申请升级写锁会互相等待,ReentrantReadWriteLock 明确不支持升级
• 适用前提:读多写少且读操作耗时明显,否则锁开销得不偿失;写饥饿场景用公平模式或改用写偏好结构
• StampedLock 乐观读:tryOptimisticRead() 拿版本戳后无锁读,validate(stamp) 校验期间无写则直接用,失败升级悲观读锁;吞吐更高但不可重入、不支持 Condition

来源:[javaguide.cn](https://javaguide.cn/java/concurrent/java-lock.html)

q391 · 中等

手写批量任务并行执行器:给定 100 个可能抛异常、各自返回结果的任务,用固定大小自建线程池并行执行,全部完成后按原始顺序汇总结果列表;要求单个任务失败不影响整体(异常被捕获记录或给默认值)、整体有超时(超时后能感知并取消未完成任务)、能统计单个任务耗时。给出 CompletableFuture 版实现要点,并对比 CountDownLatch 版的关键差异。

参考答案要点

• CompletableFuture 版:List<CompletableFuture<Result>> 逐个 supplyAsync(task, myPool),用数组按 index 写结果保证有序;CompletableFuture.allOf(...).get(timeout, unit) 等全部完成
• 异常与默认值:单个任务用 .whenComplete 或 exceptionally 包装成 Result(e, cost),不让异常冒泡到 allOf;整体超时用 get(timeout) 或 JDK9 的 orTimeout/completeOnTimeout
• 取消与感知:超时后遍历未完成的 future cancel(true)(中断只对响应中断的任务生效),finally 里 shutdown 线程池并命名线程(不要用 ForkJoinPool.commonPool 跑 IO 任务)
• 耗时统计:每个任务 supplyAsync 内 System.nanoTime 首尾差写入 Result;整体耗时在 get 前后统计
• CountDownLatch 版差异:手工 submit Runnable、latch.await(timeout)、结果写线程安全数组;异常处理、单个超时、任务编排全要手写,CompletableFuture 声明式组合(allOf/anyOf/thenCombine)表达力强得多;追问:只要一个成功就返回(anyOf+exceptionally)、Semaphore 限并发度

来源:[javaguide.cn](https://javaguide.cn/java/concurrent/completablefuture-intro.html)

q392 · 困难

手写延迟队列(对齐 DelayQueue 语义):任务带绝对到期时间,push(task) 入队,take() 阻塞直到最早到期的任务到期后返回它。用小顶堆(按到期时间排序的 PriorityQueue)+ ReentrantLock + Condition 实现关键点:堆顶未到期时 take 如何定时等待而不是自旋轮询、更早任务入队时如何唤醒等待线程。最后对比轮询扫描全表与时间轮(Round/HashedWheelTimer)的复杂度与适用规模。

参考答案要点

• 结构:PriorityQueue<DelayedTask>(Comparable 按 expireAt 升序)+ ReentrantLock + Condition available;DelayedTask 记录绝对到期时间戳与负载
• push:lock → offer 入堆;若新元素成为堆顶(比原堆顶更早到期) → available.signal() 唤醒沉睡的 take 重算最近到期时间 → unlock
• take:lock → 循环:堆空 available.await();堆顶 delay = expireAt - now:<=0 → poll 返回;>0 → available.awaitNanos(delay) 睡到堆顶到期;被唤醒后回到循环重看堆顶——防虚假唤醒与堆顶被替换
• 为什么不用 while+sleep 轮询:空转浪费 CPU 且精度差;awaitNanos 由操作系统精准唤醒,且更早任务入队会被 signal 打断重睡,均摊高效
• 复杂度:push/take O(log n);JDK DelayQueue 同原理;海量定时任务(百万级)用时间轮 O(1) 入队(Netty HashedWheelTimer);分布式场景 Redis zset(score=到期时间)轮询 + BRPOPLPUSH 防重复消费,注意轮询空转与时钟偏差

来源:[javaguide.cn](https://javaguide.cn/java/concurrent/java-concurrent-collections.html)

q703 · 中等

滑动窗口最大值(LeetCode 239):给定整数数组 nums 与窗口大小 k,窗口从最左滑到最右,返回每个窗口位置的最大值。要求手写单调队列解法,解释双端队列里存下标而不是存值的原因,分析复杂度;并回答:如果数组特别大且窗口数很少(k 接近 n),还有没有更合适的思路(分块 RMQ)。

参考答案要点

• 单调队列:双端队列存下标,保持对应值从队头到队尾单调递减;新元素入队前弹掉队尾所有对应值更小的下标(它们不可能再成为窗口最大值)
• 队头即答案:每步先判断队头下标是否已滑出窗口(<= i-k 则弹出),队头下标对应的值即当前窗口最大值
• 存下标的原因:需要用下标判断队头是否过期;只存值无法知道某个值何时离开窗口——这是本题最常追问的点
• 复杂度:每个元素最多入队、出队各一次,时间均摊 O(n),空间 O(k);对比暴力 O(n·k) 与堆解法 O(n log k)
• 边界:k=1 直接返回原数组;k=len 时返回全局最大;数组含负数与重复值算法不变;空数组、k<=0 做参数校验
• 追问:k 极大且窗口数少时用分块 RMQ(块内前后缀最大值预处理,任意区间 O(1) 查询)或稀疏表,O(n log n) 预处理 O(1) 查询,比单调队列更适合少量大窗口查询

来源:[leetcode.cn](https://leetcode.cn/problems/sliding-window-maximum/)

q704 · 困难

手写一个简单的线程安全内存缓存 ExpirableCache<K,V>:支持 put(key, value, ttl) 与 get(key)(过期返回 null),核心是 getOrLoad(key, loader)——未命中时回源,要求同一 key 并发未命中时只有一个线程执行 loader(防缓存击穿),其余线程等待其结果。过期清理自选惰性或后台。请写出实现,说明 per-key 等待的设计与锁粒度,以及 loader 失败时的处理。

参考答案要点

• 基础结构:ConcurrentHashMap<K, Entry>,Entry 存 value 与绝对到期时间(用 System.nanoTime 比较防时钟回拨);get 先判过期,过期惰性删除返回 null
• 防击穿核心:map 存 FutureTask<V> 而非裸值——未命中时原子地 putIfAbsent 一个 FutureTask,成功放入的线程执行 loader,其余线程 get 同一 Future 等待,保证同一 key 的 loader 单次执行
• 锁粒度:per-key 原子(ConcurrentHashMap 的 compute/computeIfAbsent 或 putIfAbsent)而非全局锁,不同 key 并发回源互不阻塞
• loader 失败处理:失败的 FutureTask 必须从 map 移除(否则后续请求永远拿到异常),移除后其他线程可重试;可加短 TTL 负缓存防穿透,失败要有异常传播(不能静默吞)
• 过期清理:惰性删除(get 时判断)+ 可选后台单线程定期扫描;不要每 key 一个定时器(线程开销);可选容量上限配合简单 LRU 淘汰
• 边界与追问:null 值要用哨兵对象区分「未命中」与「缓存了 null」;loader 耗时长要设等待超时;进阶对应 Guava LoadingCache 与 Go singleflight,以及 refresh-ahead(过期后先返旧值异步刷新)

来源:synthesized

q705 · 中等

字符串压缩(LeetCode 443,原地修改):给定字符数组 chars,把连续重复字符压缩为「字符+连续次数」(次数大于 1 才追加,如 a a b b c c c 变为 a2b2c3)。要求 O(1) 额外空间、返回新长度,数组前 write 个元素为结果。请写出代码,分析复杂度,并列出边界:次数为两位数、空数组、单字符不追加 1 的规则。

参考答案要点

• 双指针:read 扫描统计当前字符连续长度 cnt;write 写入字符本身,cnt>1 时把次数逐位转成字符写入
• 最大的坑:次数可能多位(a 连续 12 次要写 '1','2'),用 String.valueOf(cnt).toCharArray() 或除 10 取模逐位写,只写个位必错
• 复杂度:时间 O(n) 单趟;空间 O(1)(原地,write 永远追不上 read,不会覆盖未读数据)
• 边界:空数组返回 0、单元素直接写、全部相同字符(12 个 b → b12,长度反而变短);k=1 不追加数字的规则要在代码里显式体现
• 自测用例:[a,a,b,b,c,c,c] 期望 a2b2c3;[a,b,b,b,b,b,b,b,b,b,b,b] 期望 ab12——第二个用例专抓多位数次数的坑
• 追问变体:压缩后变长则返回原串(如 abc 不压缩);反向实现解压 expand;进阶是游程编码 RLE 应用于流式数据

来源:[leetcode.cn](https://leetcode.cn/problems/string-compression/)

q706 · 困难

在标准单线程 LRU(get/put 均 O(1),容量满淘汰最久未使用)基础上,手写线程安全版 ConcurrentLRUCache<K,V>,并回答:(1) 为什么不能简单给 get/put 各套一把 synchronized,或改用读写锁——瓶颈的本质是什么;(2) 给出至少一种并发优化思路(分段、近似 LRU/异步淘汰);(3) 说明 Caffeine 的思路(读路径无锁化+异步 drain)解决了什么。

参考答案要点

• 瓶颈本质:LRU 的 get 要移动链表节点,读操作本质是写操作,读写锁帮不上忙;一把全局锁则读读互斥,高并发读场景吞吐崩塌
• 方案1 分段:按 key 哈希拆成多个独立 LRU 段(每段一把锁),并发度=段数;代价是全局容量变成各段配额的近似(按权重均衡),淘汰精度略降;size 用 AtomicLong 维护跨段计数
• 方案2 近似 LRU:读路径不做链表移动,只把访问记录写入无锁结构(如环形 buffer/NODE 队列)或简单标记;淘汰线程异步消费记录批量调整顺序,或采样 N 个 entry 淘汰最旧(Redis 采样 LRU 思路)——牺牲精确 LRU 换读近乎无锁
• Caffeine 思路口述:读把访问事件扔进 ringbuffer(无锁写),写挂起等待;后台线程 drain 批量应用到条带化的 LRU/W-TinyLFU 结构——把 O(1) 链表操作从读路径挪到异步线程,读吞吐与并发 map 相当
• 一致性边界:容量满时「先驱逐再插入」必须与 put 在同一把锁/同一段内完成,否则超容量;null key/value 拒绝;统计(命中率、size)容忍弱一致
• 追问:为什么 JDK 至今没有 ConcurrentLRUHashMap(竞争成本高,官方推荐 Caffeine);业务上缓存场景通常接受近似 LRU 的原因(命中率差异小)

来源:synthesized

q707 · 中等

手写生产者-消费者(必须用 Semaphore 实现核心同步):容量 8 的缓冲区,3 个生产者线程、2 个消费者线程;用 empty(空位)、full(数据)两个信号量加一把互斥锁实现。要求解释:为什么是「2 个信号量+1 把锁」的标准结构;如果先拿互斥锁再拿信号量会出什么问题;公平性参数对吞吐的影响。并与 wait/notify 版本对比说明 Semaphore 的优势。

参考答案要点

• 标准结构:empty=Semaphore(8) 管空位、full=Semaphore(0) 管已有数据、mutex(ReentrantLock 或 Semaphore(1))保护缓冲区本体;生产者 empty.acquire→lock→put→unlock→full.release,消费者对称
• 顺序错误的死锁:若先 lock 再 empty.acquire——缓冲区满时生产者持锁等空位,而消费者必须先拿到锁才能取数据释放空位,互相等待死锁;信号量的 acquire 必须在互斥锁之外
• Semaphore vs wait/notify:信号量自带计数与等待队列,不会丢失信号(notify 唤错对象、条件变化需 while 重查都是 wait/notify 的坑);acquire/release 语义对称,可读性强
• 公平性:new Semaphore(n, true) 公平模式 FIFO 防饥饿但上下文切换多、吞吐低;默认非公平吞吐高;说清楚选择与理由
• 边界与收尾:interrupt 处理(acquire 可中断版本+善后退出)、缓冲区空/满的极端、生产者全部结束后消费者的收尾(毒丸 poison pill 或关闭标志)
• 追问:能否只用 1 个信号量+volatile 计数(能但易错,不推荐);ArrayBlockingQueue 内部就是该结构(lock+两个 condition),说明你理解 JDK 而不是背模板

来源:synthesized

q708 · 中等

二叉树的锯齿形层序遍历(LeetCode 103):给定二叉树根节点,第一层从左到右、第二层从右到左交替遍历,返回每层节点值的列表。请写出至少两种实现(BFS+按层反转、双端队列或双栈)并对比,分析复杂度,说明空树、单节点、退化链等边界,以及第一层方向约定这个易错点。

参考答案要点

• 解法1 BFS+反转:标准层序(queue+每层 size 计数),偶数层把该层结果 reverse;最直观,时间 O(n)、空间 O(n),反转总开销 O(n)
• 解法2 双端队列 deque:层序框架不变,奇数层结果从队尾 addLast、偶数层从队头 addFirst;单趟 O(n) 无显式反转
• 解法3 双栈:当前层栈与下一层栈,两层入栈顺序相反(一层先左后右、一层先右先左);空间 O(层宽),思路对称性好记
• 易错点:层号从 0 还是 1 开始决定第一层方向(题目要求第一层左到右);结果存节点值、遍历用节点对象,别混;null 子树直接跳过
• 边界:空树返回空列表;单节点 [[v]];每层一个节点的退化链(方向交替无感但别写错);深树忌递归 DFS(栈溢出风险,BFS 无此问题)
• 追问:DFS 按深度收集(level%2 决定 addFirst/addLast)也可行;之字形「流式打印」与序列化结合的变体

来源:[leetcode.cn](https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/)

q709 · 困难

一个 100GB 的 URL 访问日志文件(单机内存 4GB),统计出现频率最高的 10 个 URL。请给出完整方案并手写核心代码:哈希分片→每片 HashMap 计数+小顶堆取局部 topK→多路归并得全局 topK。要求说明:分片后某个小文件仍超内存怎么办;为什么不用「对整个文件做外部排序」的做法。

参考答案要点

• 第一步哈希分片:读大文件对每个 URL 求 hash(url)%1000 写入对应小文件——相同 URL 必进同一片,平均每片约 100MB 可入内存;这是「相同 key 必同片」的确定性保证,不是均匀概率
• 第二步局部统计:每片 HashMap 计数,维护大小为 10 的小顶堆(按次数比较,堆顶是当前第 10 大),每片输出自己的 top10
• 第三步全局归并:1000 组共约 1 万个候选 (url,count),内存直接堆/排序取全局 top10
• 复杂度:总时间 O(N) 哈希遍历+O(Σn_i·logK) 堆操作;IO 是主成本(读 100GB+写分片+再读);分片与统计可多线程/多机并行(map-reduce 化)
• 单文件仍超内存:对该文件二次哈希分桶递归处理;极端长 URL 可截断近似或换思路
• 为什么不整体外排:全文件外排要维持字符串全序,IO 趟数多、比较开销大;哈希分片把「全序问题」降为「局部频次统计」,数据通路短得多;追问近似解可提 Count-Min Sketch+堆

来源:[zhuanlan.zhihu.com](https://zhuanlan.zhihu.com/p/194012244)

q710 · 困难

手写一个生产可用的重试器 Retryer:submit(Supplier<T>) 支持最大重试次数、指数退避(base×2^attempt,封顶 cap)与全抖动(Full Jitter:sleep=random(0, min(cap, base×2^attempt)));支持异常分类器(可重试异常如超时/IO 才重试,参数校验类立即抛);支持总预算 deadline(剩余时间不足下一次退避立即失败)。请写出实现,并解释为什么需要 jitter、Full Jitter 与 Equal Jitter 的区别。

参考答案要点

• 骨架:attempt 从 0 循环到 maxRetries 执行动作;异常先经分类器判断,可重试则 delay=random(0, min(cap, base×2^attempt)) 后 sleep 继续;超过次数或不可重试则抛出,重试耗尽异常要链上最后一次 cause
• 为什么需要 jitter:大量客户端同刻失败后按相同退避序列重试,重试在时间上同步聚成尖峰(AWS 模拟实验结论),反而不利于下游恢复;jitter 把重试在时间轴摊开
• Full vs Equal Jitter:Full(0 到上限均匀随机)打散最彻底、抗同步最好;Equal(固定一半+随机一半)保留部分退避节奏、平均延迟略优但抗同步差;大并发场景 Full 更稳
• 总预算:每次重试前用 System.nanoTime 对比 deadline,剩余不足以再试(含退避时长)则立即失败;预算防止「重试队列越排越长」的尾部堆积,这是「重试比不重试更糟」的防线
• 边界:interrupt 时恢复中断标志并退出;base/cap/maxRetries 参数校验;attempt 溢出由 cap 兜底;重试器必须文档声明「调用方保证动作幂等」,可加每次失败/成功钩子用于打点
• 追问:异步版(CompletableFuture 组合重试)、与熔断联动(熔断打开直接失败不进重试)、尊重服务端 Retry-After 头

来源:[aws.amazon.com](https://aws.amazon.com/blogs/architecture/exponential-backoff-and-jitter/)

q711 · 困难

手写一个简易 EventBus:register(Object) 反射扫描 @Subscribe 注解的 public 单参方法注册订阅;post(Object event) 按事件类型同步分发到所有匹配订阅者;支持 unregister。要求:事件类型按父类/接口匹配(post 子类事件也能触发监听父类/接口的订阅者);一个订阅者抛异常不影响其他订阅者(异常隔离+异常回调);无订阅者的事件包装为 DeadEvent 再 post。请说明同步/异步的取舍,并与 Guava EventBus 对比你的简化点。

参考答案要点

• 注册结构:Map<Class<?>, List<Handler>>,Handler 持 target 与 Method;register 反射扫描 @Subscribe 且恰好一个参数的方法,按参数类型建索引,并向上遍历父类与接口全部登记(否则 post 子类查不到监听父类的订阅者)
• post 分发:按 event.getClass() 及其继承链从索引取订阅者,先拷贝快照再遍历(防遍历中 register/unregister 的 ConcurrentModificationException);容器用并发安全结构
• 异常隔离:每个订阅者调用独立 try-catch,异常交异常处理器(默认打日志、可定制回调),保证一个失败不影响其余;这与 Guava 默认吞异常(仅日志)的取舍要说清
• DeadEvent:没有任何订阅者时包装成 DeadEvent 再 post 一次(通常有默认日志订阅),用于发现事件类型配错/拼写错误
• 同步/异步取舍:同步版(调用线程直接执行)顺序可控、异常可感知、实现最简;异步版给 EventBus 注入 Executor,失去顺序保证,ThreadLocal/MDC 上下文要手动传递——说清你的选择
• 边界与泄漏:重复 register 同一对象要说明去重策略;unregister 按对象身份移除其全部 Handler(持有 target 引用会阻止 GC,内存泄漏是 EventBus 经典坑);对比 Guava:你还缺优先级、粘性事件、泛型事件

来源:synthesized

q712 · 中等

手写金额脱敏工具 SensitiveDataMasker:maskAmount(如 12345.67 → 1****.7,保留首位与末位数字、中间替换星号)、maskBankCard(6222 0212 3456 7890 → 622202*7890,前 6 后 4 可见且保持四位分组可读)、maskPhone(13812345678 → 1385678)。要求:支持千分位逗号、空格与负号输入;金额整数位不足 2 位时给出退化规则;非法输入的处理要明确。请给出单元测试思路,并说明金融场景脱敏的使用边界(哪些场景能脱敏、哪些禁止)。

参考答案要点

• 金额规则细化:整数与小数部分分别处理,小数点与负号不参与计数;12345.67 → 整数 1****、小数 *7(保留末位);整数位仅 1 位(如 5.20)退化规则要写死并与安全方确认(全脱敏或保留 1 位),不要自己发明规则
• 预处理:去千分位逗号与空格(1,234,567.89 先归一化);null/空/非数字/多小数点抛 IllegalArgumentException 或返回原文——二选一并文档化
• 银行卡:去空格校验长度后前 6 后 4 明文,中间星号并保持 4 位分组(622202******7890);长度不足 10 位退化(全脱敏+提示);可选 Luhn 校验输入合法性
• 手机号:11 位大陆号 3+4+4;非 11 位(固话、国际号)识别后走不同规则或拒绝——规则表驱动比 if-else 可扩展
• 测试思路:正常值、边界(0、负数、超大金额、超长卡号、不足位数)、非法输入(null、字母、空串)、格式变体(带逗号/空格);golden 文件回归样例固定;脱敏规则来自安全合规的输入,代码只做实现
• 使用边界:脱敏用于展示、日志、测试数据(客服界面、日志规范「打金额前先脱敏」);禁止用于支付扣款、对账、监管报送等需要原文的场景——展示层脱敏、存储层加密,需要审计原文时走加密+权限解密

来源:synthesized

q713 · 中等

重排链表(LeetCode 143):给定单链表 L0→L1→…→Ln,将其原地重排为 L0→Ln→L1→Ln-1→L2→Ln-2→…(节点对象重连,不许只改值,不许新建链表)。要求给出完整代码,并说明为什么分三步做:快慢指针找中间节点→反转后半段→前后两段交替合并。

参考答案要点

• 快慢指针找中点:slow 每次一步、fast 两步,fast 到尾时 slow 在中点,注意节点总数奇偶时 slow 的落点差异与后半段起点切分
• 反转后半段(迭代三指针 prev/cur/next),再把前半段尾节点 next 置 null 断开两段,避免合并时成环
• 交替合并:双指针各走一段,先接左再接右,注意最后剩一个尾节点的收尾
• 整体时间 O(n)、空间 O(1);若面试官放宽限制也可用线性表存节点按下标重建 O(n) 空间,两种都要能讲
• 边界:空链表、单节点、两节点、奇偶长度;追问:本题与判断回文链表共用『找中点+反转后半』骨架

来源:[leetcode.cn](https://leetcode.cn/problems/reorder-list/)

q714 · 中等

奇偶链表(LeetCode 328):给定单链表,把所有奇数位置(下标 1,3,5,…)的节点放前面、偶数位置(2,4,6,…)的节点放后面,保持两类节点各自的相对顺序,原地完成。例:1→2→3→4→5 输出 1→3→5→2→4。要求一次遍历、空间 O(1)。

参考答案要点

• 双指针交替推进:odd 走奇数链、even 走偶数链,每轮 odd.next=even.next、even.next=odd.next,两个指针同 步前移
• 提前保存偶数链头 evenHead,最后把奇数链尾接到 evenHead,忘记存 evenHead 是最常见错误
• 时间 O(n)、空间 O(1);空链表与单节点直接返回 head
• 追问点:为什么循环条件是 even != null && even.next != null 而不是只判 odd;奇偶长度时尾节点归属哪条链要能画图说清

来源:[leetcode.cn](https://leetcode.cn/problems/odd-even-linked-list/)

q715 · 中等

回文链表(LeetCode 234):判断单链表是否回文。基础版 O(n) 空间怎么做?进阶要求 O(1) 空间:快慢指针找中点→反转后半段→双指针向中间比对;并回答面试官追问:这种做法破坏了原链表结构,如何把它恢复回去(把后半段再反转回来)。

参考答案要点

• O(n) 空间版:复制到数组/ArrayList 后双指针首尾比对,先写对再优化是面试常规节奏
• O(1) 空间版:slow/fast 找中点,反转后半段(prev/cur 迭代),然后从两端逐节点比值,任一不等即 false
• 恢复链表:比对完成后把后半段再反转一次接回,体现工程严谨性(LeetCode 校验时会破坏结构被追问)
• 时间 O(n)、空间 O(1);边界:空链表与单节点返回 true,奇数长度时中点节点不参与比对
• 对比延伸:如果是数组/双端队列判断回文,直接首尾双指针即可,链表难在不能随机访问

来源:[leetcode.cn](https://leetcode.cn/problems/palindrome-linked-list/)

q716 · 中等

两数相加(LeetCode 2):两个非负整数分别按逆序存在两条链表(2→4→3 表示 342),返回它们之和的同样逆序链表,如 342+465=807 输出 7→0→8。要求逐位相加处理进位,一步遍历完成;并追问:如果链表是正序存储(头节点是最高位),你会怎么改。

参考答案要点

• 模拟竖式加法:同位相加 sum=a+b+carry,新节点值 sum%10,进位 sum/10,carry 最终非 0 要补一个节点
• 两链表长度不等:短的按 0 参与,循环条件 while(l1!=null || l2!=null || carry!=0) 三合一,漏掉最后的 carry 是高频 bug
• 用哑节点 dummy 简化头节点处理,尾指针逐步后移;时间 O(max(m,n))、空间 O(1)(结果链表不算额外空间)
• 正序存储变体:先反转两条链表按本题做再反转结果,或用栈从尾到头取数;能主动给出两种方案是加分项

来源:[leetcode.cn](https://leetcode.cn/problems/add-two-numbers/)

q717 · 困难

K 个一组翻转链表(LeetCode 25,Hard):每 k 个节点一组进行组内反转,不足 k 的末尾组保持原序;只能改节点内部 next 指针,不许换值。要求写出完整代码,并说清楚每组反转后如何把前一组尾节点接到本组新头节点。

参考答案要点

• 哑节点出发,每次从 prevGroupTail 前探 k 个节点确认够一组(end 判空则不足 k 保持原序直接收尾)
• 组内反转:记录组头 groupHead 与下一组起点 nextGroup,经典三指针反转 [groupHead, end] 区间
• 关键接线:prevGroupTail.next = 反转后的新头,原 groupHead 变成组尾,groupHead.next = nextGroup,再推进 prevGroupTail=groupHead
• 时间 O(n)、空间 O(1);边界:k=1 直接返回、总长恰为 k 的倍数、末尾不足 k
• 追问:与反转链表 II(区间反转)的骨架复用关系;递归写法(反转前 k 个再递归接后续)与迭代写法对比

来源:[leetcode.cn](https://leetcode.cn/problems/reverse-nodes-in-k-group/)

q718 · 困难

排序链表(LeetCode 148,Medium 进阶 Hard):给定单链表,按升序排序。要求时间 O(n log n)、空间 O(1) 的迭代版归并排序:快慢指针找中点切半→自底向上按 step=1,2,4,… 两两归并相邻段。请写出完整代码,并说明为什么链表场景归并优于快排。

参考答案要点

• 自顶向下递归归并好写但递归栈 O(log n) 不满足空间 O(1),面试先给递归版再优化成自底向上迭代版
• 自底向上:每轮步长 step 倍增,用 cut(prev,step) 切出两段再 merge 成有序段接回,引入哑节点统一处理头段
• merge 双指针比较节点值,用尾指针 tail 追加,避免每次从头找尾
• 链表归并只需改指针不需额外数组(数组归并要 O(n) 辅助空间),且快排在链表上无法利用随机访问做 partition 优化,最坏 O(n^2) 更容易出现
• 时间 O(n log n)、空间 O(1)(迭代版);边界:空链表、单节点、重复值、已有序/逆序输入;追问:能否用插入排序 O(n^2) 简化并说明取舍

来源:[leetcode.cn](https://leetcode.cn/problems/sort-list/)

q719 · 中等

二叉树的直径(LeetCode 543):直径是任意两节点间最长路径的边数,路径可不过根。求给定二叉树的直径。要求一次遍历解决,并解释为什么不能只对每个节点调两次 depth(那是 O(n^2))。

参考答案要点

• dfs(node) 返回以该节点为端点向下的最大边数 = max(左,右)+1(空节点返回 -1 或 0 要统一约定避免负偏)
• 路径经过节点时的候选直径 = 左深度 + 右深度,在 dfs 回溯过程中用成员变量/全局 max 持续更新
• 一次 dfs 同时完成深度计算与直径统计,时间 O(n)、空间 O(树高);O(n^2) 版(每节点重新算子树高)要能指出瓶颈
• 边界:空树直径 0、单节点直径 0(路径至少要两个节点)、退化成链表时直径=节点数-1 且递归深度等于 n 需警惕栈溢出

来源:[leetcode.cn](https://leetcode.cn/problems/diameter-of-binary-tree/)

q720 · 中等

二叉树的最近公共祖先(LeetCode 236):给定二叉树和树中两个节点 p、q(节点互异且都存在),找它们的最近公共祖先。要求递归一次遍历 O(n) 解法,并讲清递归函数的语义:『当前子树中发现 p 或 q 则返回它,否则返回 null』为什么是对的。

参考答案要点

• 递归语义:左右子树都返回非 null 说明 p、q 分居两侧,当前节点即 LCA;只有一侧非 null 则 LCA 在那一侧,向上透传
• 叶节点等于 p 或 q 直接返回自身,天然覆盖『p 是 q 祖先』的情形
• 时间 O(n)、空间 O(树高);追问:如果节点带 parent 指针,可转成两条链找第一个交点(类似链表相交)
• 扩展:二叉搜索树版利用有序性——第一个值落在 [p,q] 区间的节点即 LCA,从根往下走 O(h);两种都要会

来源:[leetcode.cn](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/)

q721 · 中等

二叉树的右视图(LeetCode 199):站在树右侧从上往下看,返回每层最右边的节点值。要求两种解法:BFS 每层取最后一个节点;DFS 先递归右子树再递归左子树、每层第一次到达时记录。并说明 DFS 版为什么『先右后左』就能保证取到每层最右。

参考答案要点

• BFS:队列按层遍历,本层 size 固定后循环 size 次,i==size-1 的元素即本层最右;时间空间 O(n)
• DFS:depth 首达即最右——先右后左,每层第一个被访问的一定是该层最右节点,if(depth==res.size()) res.add(val) 判重
• 坑点:右视图不是右子树链(左子树更深时下层答案在左子树里),要能举出反例画图说明
• 变体追问:左视图(先左后右)、俯视图/右视图变形、按层打印每层最大值(层序遍历族);边界:空树返回空

来源:[leetcode.cn](https://leetcode.cn/problems/binary-tree-right-side-view/)

q722 · 中等

二叉树的层序遍历 II(LeetCode 107,层序变形):自底向上、从左到右逐层返回节点值(最底层在最前)。先写标准 BFS 层序,再给两种『倒序』实现,并说明哪种更优。

参考答案要点

• 标准 BFS + 每层临时 list:队列 size 分层法,每层收集完加入结果
• 倒序方案一:结果 list 每层 add(0, layer)(头插)最简洁;方案二:全部收完再 Collections.reverse——两者等价,头插法少一次遍历
• 深挖追问:DFS 也能做——depth 传入递归,先左后右,按 depth 放入对应层 list,最后反转层序
• 时间 O(n)、空间 O(n)(队列+结果);边界:空树、单节点、退化链表;对比已考过的锯齿遍历(奇偶层反向)与本题为纯 bottom-up

来源:[leetcode.cn](https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/)

q723 · 中等

验证二叉搜索树(LeetCode 98):判断给定二叉树是否是合法 BST。要求两种解法:(1) 递归传 (min,max) 开区间上下界;(2) 中序遍历结果严格递增。并说明为什么只比较『每个节点与其左右孩子』是错的。

参考答案要点

• 只比父子层是错的:子树所有节点都要落在祖先划定的区间内,反例根 5、右孩子 6、右孩子的左孩子 4
• 解法一:isValid(node, min, max) 要求 node.val∈(min,max),左子树递归收紧上界为 node.val,右子树收紧下界;注意相等也算不合法
• 解法二:中序遍历(递归或显式栈迭代)维护 prev,一旦 prev>=cur 即 false;迭代版中序能体现非递归功底
• 时间 O(n)、空间 O(树高);边界:Integer.MIN/MAX 首节点坑(用 Long 或 null 语义的 min/max 避免溢出)、空树与单节点合法
• 追问:BST 中第 K 小、BST 的众数等一族题共用中序有序性

来源:[leetcode.cn](https://leetcode.cn/problems/validate-binary-search-tree/)

q724 · 中等

最小栈(LeetCode 155):设计支持 push、pop、top 操作并能在 O(1) 内检索到最小元素的栈。要求两种实现:辅助栈同步维护『当前最小值』;单栈存差值(min-value 差值法)。重点讲清 pop 时辅助栈如何同步回退。

参考答案要点

• 辅助栈法:minStack 与主栈同步 push/pop,新元素若小于等于 minStack 栈顶则同时入 minStack(pop 时值相等才同步弹出),注意用 <= 防重复最小值丢失
• 差值法:存 diff=val-min,push 后按 diff 正负更新 min,pop 时 diff<0 说明弹出的是当前 min,需要回退 min=min-diff;省一个栈但可读性差
• 所有操作 O(1)、空间 O(n);追问:O(1) 空间仅用节点内嵌 min 字段(链式栈每节点带当时最小值)
• 边界:空栈 pop/top 抛异常约定、连续相同最小值、先 push 5 再 push 5 再 pop 的行为一致性

来源:[leetcode.cn](https://leetcode.cn/problems/min-stack/)

q725 · 中等

下一个更大元素(单调栈,LeetCode 496/739 合并考查):(1) 每日温度:数组表示每日温度,返回隔多少天升温,不升温填 0;(2) 进阶:数组带循环(可绕回开头)。要求手写单调栈解法,解释为什么栈里存下标而不是值、栈内保持什么单调性。

参考答案要点

• 从右往左或从左往右两种等价写法要讲清一种:从左往右,栈存『还没找到答案的下标』,保持栈内温度单调递减
• 新元素 > 栈顶温度时,栈顶弹出且其答案 = 当前下标 - 栈顶下标,循环弹到不大于为止,再压入当前下标
• 存下标的原因:答案要求距离差值,值本身拿不到位置;存值版本(496)配合 map 记录答案
• 时间 O(n)——每个元素最多入栈出栈各一次(均摊分析是必答点)、空间 O(n);暴力 O(n^2) 会超时要能指出
• 循环数组变体:遍历两遍并用 i%n 取模只更新一次答案;边界:全递减序列答案全 0、全递增答案全 1

来源:[leetcode.cn](https://leetcode.cn/problems/daily-temperatures/)

q726 · 简单

用队列实现栈(LeetCode 225,与『两栈实现队列』互为镜像):仅用两个队列实现一个后入先出的栈,支持 push、pop、top、empty。要求两种实现:单队列循环反转版(push 时把前面元素依次转到后面)与双队列倒腾版,并分析各操作复杂度。

参考答案要点

• 单队列版:push 正常入队后,把队列前 size-1 个元素依次出队再入队,使新元素到队头,pop/top 直接队头 O(1),push O(n)
• 双队列版:主队列保存栈序(队头为栈顶),pop 时把主队列前 n-1 个倒入空队列,剩下的就是栈顶;push 直接入主队列尾(需配合一个备份队列交换引用)
• 两种方案把 O(n) 开销放在 push 还是 pop 上是设计取舍,面试要能对比陈述
• 均摊分析:单队列版每个元素从入到出最多被搬运一次;边界:空栈 pop/top 抛异常、连续 push/pop 交替

来源:[leetcode.cn](https://leetcode.cn/problems/implement-stack-using-queues/)

q727 · 中等

最长递增子序列(LeetCode 300):给定整数数组,求最长严格递增子序列长度。要求两种解法:O(n^2) DP 与 O(n log n) 贪心+二分(tails 数组),并解释 tails 数组的含义为什么是『长度为 i+1 的上升子序列的最小可能结尾』。

参考答案要点

• O(n^2) DP:dp[i] 以 i 结尾的 LIS 长度,枚举 j<i 且 nums[j]<nums[i] 取 max+1;时间 O(n^2) 先保证写对
• O(n log n):维护 tails[],每个元素二分找第一个大于等于它的位置替换(严格递增用 lower bound),若都小于则追加——tails 长度即答案
• tails 是严格递增的且是各长度最小结尾的『快照』,替换操作不改变长度但让后续更有机会接上——这段证明是面试核心
• 边界:空数组、全相等(严格递增答案为 1)、全递减;变体:最长不下降(upper bound)、俄罗斯套娃信封(二维先排序再 LIS)
• 追问:输出具体子序列——DP 版回溯 predecessor,或 tails 配合 idx/parent 数组重建

来源:[leetcode.cn](https://leetcode.cn/problems/longest-increasing-subsequence/)

q728 · 困难

编辑距离(LeetCode 72,Hard):给定两个单词 word1、word2,返回把 word1 转换成 word2 所需的最少操作数(插入/删除/替换一个字符)。要求写 O(m×n) 二维 DP 并推导状态转移,再给滚动数组优化到 O(n) 空间的写法。

参考答案要点

• dp[i][j] = word1 前 i 个字符变成 word2 前 j 个字符的最少操作;初始化 dp[i][0]=i(全删)、dp[0][j]=j(全插)
• 转移:字符相等则 dp[i][j]=dp[i-1][j-1];不等取 min(替换 dp[i-1][j-1],删除 dp[i-1][j],插入 dp[i][j-1])+1
• 空间优化:滚动数组只需上一行,注意用变量 prev 保存左上角 dp[i-1][j-1] 防止被覆盖;时间 O(mn)、空间 O(n)
• 边界:任一串为空;追问:只允许插入删除(无替换,LC 583)、允许代价不同的加权编辑距离如何改转移
• 能画出二维表手工填一遍小例子(如 horse→ros=3)是面试硬要求

来源:[leetcode.cn](https://leetcode.cn/problems/edit-distance/)

q729 · 中等

零钱兑换(LeetCode 322,完全背包):给定不同面额硬币数组和总金额 amount,计算凑成总金额所需的最少硬币个数,无法凑出返回 -1,每种硬币数量无限。要求 DP 完整代码,并对比『组合数(518)/排列数(377)』与本题『最少枚数』在转移方程和遍历顺序上的区别。

参考答案要点

• dp[i] 凑金额 i 的最少硬币数,初始化 dp[0]=0、其余为无穷大(INF 用 amount+1 防加法溢出)
• 转移 dp[i]=min(dp[i], dp[i-coin]+1) 对每枚硬币;返回 dp[amount]>amount 则 -1;一维即可,硬币外层/内层对本题结果无影响
• 对比:求组合数要硬币在外层(避免排列重复计数),求排列数要金额在外层——这个遍历顺序差异是追问高频
• 时间 O(amount×coins)、空间 O(amount);边界:amount=0 返回 0、单枚面额大于 amount、面额 1 只有一枚的贪心陷阱(贪心对任意面额不成立,反例 [1,3,4] 凑 6)

来源:[leetcode.cn](https://leetcode.cn/problems/coin-change/)

q730 · 中等

打家劫舍系列(LeetCode 198+213):(1) 一排房屋,不能偷相邻两家,求最大金额;(2) 环形排列(首尾相邻)怎么改;(3) 树形(以二叉树节点为房屋,父子不能同时偷)说思路即可。要求 (1) 给 O(1) 空间 DP,(2) 给拆两次线性的方案。

参考答案要点

• 线性版:dp[i]=max(dp[i-1], dp[i-2]+nums[i]),滚动两个变量 prev/cur 即 O(1) 空间,『不偷当前=继承昨天,偷当前=前天+当前』
• 环形版:首尾不能同偷,拆成 [0..n-2] 与 [1..n-1] 两个线性子问题各求一遍取最大;单间房要特判(n==1)
• 树形版思路:树上后序遍历,每个节点返回 (偷该节点的最大, 不偷该节点的最大),父节点状态由子节点两个状态转移——能说出框架即可
• 时间 O(n)、空间 O(1)(线性版);边界:空数组、只有一间、只有两间;易错:环形版忘记处理 n==1 时两个区间都为空

来源:[leetcode.cn](https://leetcode.cn/problems/house-robber/)

q731 · 中等

最大子数组和(LeetCode 53):给定整数数组(含负数),找出和最大的连续子数组并返回其和。要求:(1) Kadane 贪心/DP 一趟解法;(2) 返回子数组本身的下标;(3) 口述分治 O(n log n) 解法的递归结构。

参考答案要点

• Kadane:cur = max(num, cur+num) —— 前缀和为负则从当前元素重新起段;ans 持续取 max;一趟 O(n)、空间 O(1)
• 要求下标:起段重置时记录新区间起点 tmpStart,更新 ans 时同步 (start,end);这是贪心转可追溯答案的标准手法
• 分治:区间最大子段 = max(左半最大, 右半最大, 跨中点最大),跨中点从中点向两侧分别扩;T(n)=2T(n/2)+O(n) 即 O(n log n),说明实际工程不采用但要懂
• 边界:全负数(答案为最大单个元素,Kadane 天然正确)、单元素、含 0;变体追问:环形子数组最大和(918,总和-最小子数组和)、乘积最大子数组(152,需同时维护最大最小)

来源:[leetcode.cn](https://leetcode.cn/problems/maximum-subarray/)

q732 · 中等

最长回文子串(LeetCode 5):给定字符串 s,返回其中最长的回文子串。要求中心扩展法完整代码,并口述:(1) 二维 DP 的定义与转移;(2) Manacher 算法为什么能到 O(n)(只说思想框架)。

参考答案要点

• 中心扩展:枚举 2n-1 个中心(单字符中心 + 双字符间隙中心),从中心向两侧扩到不等为止,更新全局最长——实现简单面试首选,O(n^2)/O(1)
• 区间 DP:dp[i][j] 表示 s[i..j] 是否回文,依赖 dp[i+1][j-1],按子串长度从小到大填表,O(n^2)/O(n^2)
• Manacher 思想要点:插入分隔符统一奇偶,利用已算回文半径的镜像对称性跳过重复扩展,辅助数组半径不回退保证线性
• 边界:空串、单字符、全相同字符(最坏用例 aaaa…,朴素 O(n^2) 会退化,可作为引出 Manacher 的引子)
• 变体:最长回文子序列(514/516 区间 DP 求长度不要求连续)与本题『子串连续』的区别要能一句话讲清

来源:[leetcode.cn](https://leetcode.cn/problems/longest-palindromic-substring/)

q733 · 中等

和为 K 的子数组(LeetCode 560):给定整数数组 nums 与整数 k,统计和恰好等于 k 的连续子数组个数(元素可负,不能滑窗)。要求前缀和+哈希表解法,并解释为什么『先查后存』的顺序不能反。

参考答案要点

• 核心:子数组和 = 前缀和之差。遍历时查 map 中前缀和 preSum-k 出现的次数,即以当前位置结尾、和为 k 的子数组个数
• 顺序:先查 count += map.get(preSum-k) 再 map.put(preSum, +1),反过来会把长度 0 的子数组(自己减自己)算进去
• 初始化 map.put(0, 1) 表示空前缀——处理『从头开始的子数组恰好等于 k』这一漏网情形,漏这句是最常见 bug
• 时间 O(n)、空间 O(n);为什么不能滑动窗口:负数使窗口和不单调,窗口收缩规则失效——这是必答追问
• 变体:和可被 K 整除的子数组(974,前缀和取模+注意负数取模)、乘积小于 K(正数才可滑窗)

来源:[leetcode.cn](https://leetcode.cn/problems/subarray-sum-equals-k/)

q734 · 中等

岛屿数量(LeetCode 200):'1' 是陆地、'0' 是水,上下左右相连的 1 组成一个岛,求网格中岛屿数量。要求 DFS 主流程+『访问标记』两种做法(改写网格为 0 或额外 visited 数组),再口述 BFS 与并查集两种等价解法。

参考答案要点

• 双重循环扫格子,遇到 '1' 计数 +1 并从该点 flood fill(DFS),把整块连通陆地标记为已访问,防止重复计数
• DFS 递归:越界判断先行(grid 范围 + 非'1' 返回),四方向递归;深度过大可改显式栈或 BFS 队列避免栈溢出(200×200 极端蛇形用例)
• 并查集版:每个 '1' 格子是一个节点,与右、下邻居 union,最终答案 = 初始陆地数 - 成功合并次数(或查不同根个数)
• 时间均 O(m×n);标记法会破坏原网格,面试要主动说明并在需要保留输入时用 visited
• 变体族:最大岛屿面积(695)、岛屿周长(463)、封闭岛屿(1254 靠边不算)、腐烂的橘子(994 多源 BFS 按层计时)——能报出变体是加分项

来源:[leetcode.cn](https://leetcode.cn/problems/number-of-islands/)

q735 · 中等

课程表(LeetCode 207,拓扑排序):n 门课带先修关系 prerequisites(b 依赖 a),判断能否修完所有课(即有向图是否无环)。要求 BFS 入度删除法(Kahn)完整代码,并口述 DFS 三色标记判环的写法。

参考答案要点

• 建邻接表 + 入度数组;入度为 0 的节点入队(可用课程直接修),出队时计数、后继入度减 1 减到 0 再入队
• 最终计数 == n 则无环可排完,否则有环——环上节点入度永远不为 0,天然被剩下
• DFS 三色:0 未访问/1 访问中(在递归栈)/2 已完成,遇到 1 即发现回边成环; DFS 逆序出栈序列即是拓扑序之一
• 时间 O(V+E)、空间 O(V+E);边界:无先修关系(直接 true)、自依赖 [a,a](环)、重边
• 追问:输出具体修课顺序即课程表 II(210,记录出队顺序);拓扑排序唯一当且仅当每步入度 0 的节点唯一

来源:[leetcode.cn](https://leetcode.cn/problems/course-schedule/)

q736 · 困难

克隆图(LeetCode 133):无向连通图中每个节点带 val 与 neighbors 列表,给定其中一点,深拷贝整张图(新节点不是原引用)。要求 DFS+哈希表解法,并解释哈希表在『防止死循环』与『保证已克隆节点复用』上的双重作用。

参考答案要点

• map:原节点 → 克隆节点。进入 dfs 先查 map 命中直接返回(处理环与菱形共享),未命中才创建新节点并注册,再逐个递归邻居填 neighbors
• 关键顺序:先 map.put(原,新) 再递归邻居——否则环回边到来时 map 里还没有自己,无限递归栈溢出
• BFS 版:队列 + 同一个 map,克隆邻居不存在则创建并入队;复杂度均 O(V+E) 时间、O(V) 空间
• 引申:这题是『深拷贝带环引用结构』的通用模板,同族题:复制带随机指针的链表(138,同样 map 原节点到新节点,或穿插原链表 O(1) 空间法口述)
• 边界:单节点无邻居、自环边、两点互指;追问:为什么不能先遍历完再统一拷贝(遍历本身就走不出环)

来源:[leetcode.cn](https://leetcode.cn/problems/clone-graph/)

q737 · 中等

省份数量(LeetCode 547,手写并查集):n 个城市,isConnected[i][j]=1 表示直接相连,直接间接相连的城市组成一个省份,求省份数量。要求手写并查集(含路径压缩与按秩/大小合并),并说明每一步复杂度与均摊分析。

参考答案要点

• UnionFind 三件套:find(x) 路径压缩(递归或迭代两趟,父指针直接挂到根)、union(a,b) 按大小合并(小挂大,树高被压在 O(log n))
• 初始每城自成一省 count=n,每次有效合并(两根不同)count--,最终返回 count——不必再遍历数根
• 均摊复杂度:路径压缩+按大小合并后单次操作接近 O(α(n)) 反阿克曼,近似常数;面试至少要说到『均摊近似 O(1)』
• 对比:DFS/BFS 遍历邻接矩阵也能做 O(n^2),但并查集适合『动态加边』场景(如账户合并 721、冗余连接 684 动态判环),这是选型理由
• 边界:n=1、全不相连(count=n)、全相连(count=1);isConnected 对称矩阵只需处理上三角

来源:[leetcode.cn](https://leetcode.cn/problems/number-of-provinces/)

q738 · 简单

有效的括号(LeetCode 20):给定只含 '()[]{}' 的字符串,判断是否有效(左括号必须以正确类型和顺序闭合)。要求栈解法,并说明三种不合法情形如何各被覆盖;追问:如果括号种类扩展到 '<>' 或加引号怎么改。

参考答案要点

• 栈:左括号入栈,右括号到来时栈顶必须是对应左括号——用 map(右→左)统一判断,弹栈前先检查栈空
• 三种失败:右括号来了栈空(如 ')(')、栈顶不匹配(如 '(])')、扫完栈非空(如 '(((');代码三处检查各挡一种
• 长度奇数直接返回 false 是快速剪枝;时间 O(n)、空间 O(n)
• 扩展新括号种类只需扩 map;若加『可匹配的成对引号』这类自闭合符号则不入栈直接配对前一字符讨论
• 变体:最长有效括号(32,harder,栈存下标或两遍计数)、使括号有效的最少添加(921)——能点出变体名即可

来源:[leetcode.cn](https://leetcode.cn/problems/valid-parentheses/)

q739 · 困难

字符串相乘(LeetCode 43,大数乘法):给定两个非负整数字符串 num1、num2,返回乘积的字符串形式,不允许直接转 BigInteger/long。要求用『结果数组按位累加』法写出完整代码并处理前导零。

参考答案要点

• m 位数 × n 位数结果最多 m+n 位;num1[i]×num2[j] 的贡献落在结果数组的 i+j 与 i+j+1 两位(从左数下标体系要统一)
• 两遍法更好写:第一遍把每对乘积累加到 res[i+j+1],第二遍从右往左进位 res[i+j]+=res[i+j+1]/10, res[i+j+1]%=10
• 任一因子为 '0' 直接返回 "0"(避免输出 "000…"),去前导零也可以用首次非零下标截取,两者取其一要写死
• 时间 O(m×n)、空间 O(m+n);字符与数字互转 num-'0'/'0'+num 要熟练;变体:字符串相加(415)是其子步骤、链表版两数相加已另考
• 追问:Karatsuba 分治乘法为什么 O(n^1.585)——会讲『两次乘法拆成三次一半规模乘法』的思想即可

来源:[leetcode.cn](https://leetcode.cn/problems/multiply-strings/)

q740 · 中等

实现 strStr / 找子串(LC 28,RK 与 KMP 思想考查):在字符串 haystack 中找 needle 首次出现位置,不存在返回 -1。要求:(1) 写出朴素匹配;(2) 讲清 Rabin-Karp 滚动哈希的哈希函数与滚动更新公式;(3) 推导 KMP 的 next 数组含义与失配移动规则(不强制完整代码,框架必须对)。

参考答案要点

• 朴素:双指针对齐起点逐位比对,最坏 O(n×m)(如 aaaaab 对 aaab),先写对再谈优化
• RK:预处理算 needle 哈希,窗口右滑一格时 O(1) 滚动更新 h=(h-s[i]*B^(m-1))*B+s[i+m],哈希碰撞时逐位复核避免误报;均摊 O(n+m),最坏退化 O(nm)
• KMP:next[j] = 最长相等前后缀长度,失配时 j=next[j-1] 回退而 i 不回退;构建 next 数组本身是模式串自我匹配的过程
• KMP 时间 O(n+m)、空间 O(m),主串指针永不回退是与朴素法的本质区别;至少能手推 needle='aabaaf' 的 next 数组
• 工程视角:Java String.indexOf 用的是朴素+启发式,BM/Sunday 在平均场景更快——能对比说明面试筛选的是思维而非背库

来源:[leetcode.cn](https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/)

q741 · 中等

找到字符串中所有字母异位词(LC 438,定长滑动窗口):给定 s 与 p,返回 s 中所有是 p 的字母异位词的子串起始下标。要求定长窗口 + 26 长度计数数组的解法,并说明用『差异计数 diff』代替逐位比较如何把每步判断降到 O(1)。

参考答案要点

• 窗口定长 = p.length():右指针扩张,窗口超长时左指针收缩,每步右进左出各更新一次计数
• 比较法:每步比较 window 与 need 两个 26 数组是否相等 O(26);优化法:维护 differ = 两数组不相等的下标个数,右进左出更新后 differ==0 即命中,判断 O(1)
• 更新 differ 的方向:window[c] 增加后若 window[c]==need[c] 则 differ--,若之前相等现在不等则 differ++(左出对称)——边界逻辑是本题难点,建议写增加/减少各一个私有方法
• 时间 O(n×1)(差异法)或 O(26n)(比较法)、空间 O(26);边界:s 短于 p 返回空、p 含重复字母、大小写约定
• 同族题:最小覆盖子串(76,变长窗口+欠账计数 needCnt)已另考,注意两题计数策略差异并能对比

来源:[leetcode.cn](https://leetcode.cn/problems/find-all-anagrams-in-a-string/)

q742 · 简单

x 的平方根(LeetCode 69):实现 int mySqrt(int x),返回对 x 开方的整数部分(舍去小数)。要求二分与牛顿迭代两种解法,并说明二分的中点计算为什么用 mid = left + (right-left+1)/2 或如何避免死循环、乘法为什么会溢出。

参考答案要点

• 二分 [0,x]:判断 mid*mid<=x 则答案在右半(含 mid),否则左半;用 mid = left+(right-left+1)/2 上取整配合『答案含 mid 时 l=mid』防死循环
• 溢出:midmid 用 long 比较或改写为 mid<=x/mid(除法判等要防整除误差,mid<=x/mid 等价 midmid<=x 在正整数下成立)
• 牛顿迭代:x_(k+1) = (x_k + x/x_k)/2,从 x 开始单调递减收敛到整数解;取整时最后要回退校验(res*res 可能略超 x)
• 时间:二分 O(log x)、牛顿迭代二次收敛更快;边界:x=0、x=1(乘法区间 [0,x] 含 0 防死循环起点)、Integer.MAX_VALUE 溢出用例
• 扩展:精确到小数点后 k 位的实数版二分(eps=1e-k 控制循环),与浮点二分的终止条件讨论

来源:[leetcode.cn](https://leetcode.cn/problems/sqrtx/)

q743 · 中等

寻找峰值(LeetCode 162):给定 nums,相邻元素互不相等,nums[-1]=nums[n]=-∞,满足 nums[i]>相邻者的 i 是峰值,返回任意一个峰值下标,要求对数时间。并解释:为什么『往比自己大的邻居方向走』必然撞到峰值、二分的终止条件如何保证不动数组越界。

参考答案要点

• 爬坡二分:比较 nums[mid] 与 nums[mid+1],若升则峰在右侧 l=mid+1,若降则峰在左侧(含 mid) r=mid;任意时刻 [l,r] 内保证存在峰值(不变量)是正确性核心
• 为什么对:从任意点沿『更大邻居』走严格递增,而两端是 -∞,递增序列不可能无限,必然终止在某局部峰——二分每步保留仍含峰的那半
• 取 mid 用下取整即可(因比较对象是 mid+1,数组保证 mid+1 不越界:循环内 r-l>=1)
• 时间 O(log n)、空间 O(1);边界:单调递增数组答案 n-1、单调递减答案 0、单元素返回 0
• 追问:允许相邻相等时( LC 852 山脉数组与本题关系、含重复的 154 型讨论)为何不能直接二分——相等破坏了不变量的方向性

来源:[leetcode.cn](https://leetcode.cn/problems/find-peak-element/)

q744 · 困难

至多包含 K 个不同字符的最长子串(LC 340,变长滑窗进阶):给定字符串 s 与整数 k,返回包含的不同字符数不超过 k 的最长子串长度。k=0、s 空等边界自行处理;要求写出变长滑窗完整代码,并对比『恰好 K 个(LC 992)』在收缩条件上的差别。

参考答案要点

• 变长滑窗:right 右扩并把 cnt[c]++(0→1 时 distinct++);distinct>k 时左缩,cnt 减到 0 时 distinct--,直到恢复 k 个
• 每轮 right 收缩完成后更新 ans=max(ans, right-left+1)——『扩张后收缩到合法再记录』的顺序不能反
• 数据结构:int[26] 只够小写字母,通用字符用 HashMap<Character,Integer>;复杂度 O(n)(左右指针各走一遍)、空间 O(k)
• 对比:恰好 K 个(992)需『至多 K 减 至多 K-1』的差技巧或右端计数法,直接收缩到 distinct==k 无法保证子串『恰好』——能点出差异即可
• 边界:k=0 返回 0、k>=不同字符总数返回 s.length()、空串;追问:如果要求输出子串本身,记录 ans 更新时的左端点

来源:[leetcode.cn](https://leetcode.cn/problems/longest-substring-with-at-most-k-distinct-characters/)

q745 · 中等

只出现一次的数字(LeetCode 136 及 137 变体):数组里除一个数外其余都出现两次,找那个数(要求异或解法);变体:其余都出现三次、只出现一次的那个找出来(要求按位统计 mod 3 或一次异或+与的位运算技巧)。两个都要写。

参考答案要点

• 两次版:全员异或,a^a=0、0^b=b,交换律结合律下成对数抵消剩答案;O(n)/O(1),口述此性质是答题第一句
• 三次版基础解:统计 32 个位上 1 的个数,mod 3 余 1 的位属于唯一数,按位拼回;O(32n)/O(1)
• 三次版进阶(口述即可):ones/twos 两状态机——ones=(ones^x)&~twos, twos=(twos^x)&~ones,最终 ones 即答案,体现用位运算做模三计数的状态机思想
• 变体追问:两个只出现一次的数(260):全体异或得两数异或值,取最低不同位把数组分成两组各自异或
• 边界:负数(Java 左移与符号位,建议无符号右移 >>> 或 long 处理)、空数组约定

来源:[leetcode.cn](https://leetcode.cn/problems/single-number/)

q746 · 简单

位 1 的个数(LeetCode 191):给定 32 位无符号整数,返回其二进制中 1 的个数(汉明重量)。要求三种写法:逐位与、n & (n-1) 抹最低位 1、查表/分治(口述 JDK Integer.bitCount 的并行分治思想),并说明各自循环次数。

参考答案要点

• 逐位与:n&1 取末位计数后无符号右移 >>>= 1,固定循环 32 次;Java 必须用 >>> 而不是 >>,负数符号位补 1 会死循环——这是本题埋的坑
• n&(n-1):每次消去最低位的 1,循环次数等于 1 的个数,最少循环;两数相减的位含义(n-1 把最低 1 变 0、其后全变 1)要能推导
• JDK bitCount 分治:5 步位运算,先相邻 2 位相加、再 4 位、8 位、16 位、32 位(0x55555555/0x3333… 掩码),O(1) 无循环;能画出掩码分组图是强加分
• 边界:0 返回 0、0xFFFFFFFF 返回 32、负数输入语义(无符号处理)
• 同族:汉明距离(461,两数异或后数 1)、判断 2 的幂(231,n>0 且 n&(n-1)==0)

来源:[leetcode.cn](https://leetcode.cn/problems/number-of-1-bits/)

q747 · 中等

不用加减乘除做加法(剑指 Offer 65 / 面试题):写一个函数求两个整数之和,函数体内不得使用 +、-、*、/ 四则运算符(位运算与比较可用)。要求给出 a+b 位运算解法,并解释为什么在有负数场景下 Java 需要特殊处理。

参考答案要点

• 核心两步:异或 a^b 是『不考虑进位的和』,与 a&b 左移一位是进位列表;循环直到进位为 0,和 = 最后的异或值
• 每轮:a, b = a^b, (a&b)<<1,把 b 当新的进位继续叠加;非负数下最多循环 32 次必然收敛
• Java 坑:负数补码下 (a&b)<<1 左移可能溢出符号位,题目声明不溢出即可;若要严格规避可在无符号 32 位域内模拟(用 int 循环以 b!=0 终止,Java 实测可正确处理负数,但要能解释补码循环终止性)
• 延伸:不用第三个变量交换两数(a^=b; b^=a; a^=b)与本题同源,面试常连问;不用乘除实现减法 = a + (-b) 的补码取反加一
• 边界:0+0、单 0、a=b、极端 Integer.MAX_VALUE/Min_VALUE 溢出语义约定

来源:[leetcode.cn](https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/)