💯 LeetCode 高频
LRU 缓存 · 接雨水 · 最长回文子串 · 合并 K 个链表 · 三数之和 · 括号匹配
1. 手写 LRU 缓存（146）？
需求：get/put 都 O(1)，容量满时淘汰最久未使用的。结构：HashMap（定位 O(1)）+ 双向链表（记录访问顺序 O(1)）。
- get：命中 → 把节点移到链表头（头=最近使用）
- put：已存在 → 更新值并移到头；不存在 → 头部插入，超容量则删除尾部（最久未用）
- 双向链表才能 O(1) 删除任意节点（单向不行）
核心骨架（LinkedHashMap 版一行，手写版要点）
// 手写要点（HashMap + 自建双向链表 Node）
class LRUCache {
private final Map<Integer, Node> map = new HashMap<>();
private final int capacity;
private final Node head = new Node(), tail = new Node(); // 虚拟头尾
LRUCache(int cap) { capacity = cap; head.next = tail; tail.prev = head; }
public int get(int key) {
Node n = map.get(key);
if (n == null) return -1;
moveToHead(n);
return n.value;
}
public void put(int key, int value) {
Node n = map.get(key);
if (n != null) { n.value = value; moveToHead(n); return; }
if (map.size() == capacity) {
Node last = tail.prev; // 淘汰最久未用
removeNode(last);
map.remove(last.key);
}
Node fresh = new Node(key, value);
addToHead(fresh);
map.put(key, fresh);
}
// moveToHead / addToHead / removeNode：纯指针操作，面试现场画图写
}🎯 面试要点
- 虚拟头尾节点消灭空指针判断——写链表题的通用技巧
- 面试延伸：LinkedHashMap 的 removeEldestEntry（Java 基础页有）；Redis 的 LRU 是抽样近似
- 进阶：LFU（淘汰最不常用）需要频率桶 + 双向链表，两层结构
2. 接雨水（42）——双指针解法？
核心洞察：每个位置能接的水 = min(左侧最高, 右侧最高) - 当前高度（为负则 0）。
双指针优化：左右指针向中间靠，维护 leftMax/rightMax。哪边最大高度小，哪边先结算（该位置水量已确定，因为 min 被小者限制）。O(n) 时间 O(1) 空间。
双指针接雨水
public int trap(int[] h) {
int l = 0, r = h.length - 1, lMax = 0, rMax = 0, water = 0;
while (l < r) {
lMax = Math.max(lMax, h[l]);
rMax = Math.max(rMax, h[r]);
if (lMax < rMax) { // 左边最高小 → 结算左边
water += lMax - h[l];
l++;
} else {
water += rMax - h[r];
r--;
}
}
return water;
}🎯 面试要点
- 先答暴力（每位置左右扫，O(n²)）→ 再答前缀最大数组（O(n) 空间）→ 最后双指针（O(1) 空间），展示递进
- 双指针结算规则一句话："哪边矮结算哪边"
3. 最长回文子串（5）——中心扩展？
回文串关于中心对称。中心扩展：枚举每个中心（n 个单字符中心 + n-1 个双字符中心，共 2n-1 个），向两边扩展找最长回文。O(n²) 时间 O(1) 空间。
中心扩展
public String longestPalindrome(String s) {
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expand(s, i, i); // 奇数长度中心
int len2 = expand(s, i, i + 1); // 偶数长度中心
int len = Math.max(len1, len2);
if (len > end - start + 1) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
return r - l - 1;
}🎯 面试要点
- 进阶方案：Manacher 算法 O(n)（预处理插入 # + 维护回文半径），答出名字和思想即可
- 回文子序列（非连续）用区间 DP：dp[i][j] = 首尾相等 ? dp[i+1][j-1]+2 : max(dp[i+1][j], dp[i][j-1])
4. 其他高频题一句话思路？
| 题目 | 思路 |
|---|---|
| 三数之和 | 排序 + 固定一个 + 双指针，注意去重（跳过相同值） |
| 合并 K 个有序链表 | 优先队列（堆）每轮取最小头，或两两归并 |
| 有效括号 | 栈匹配；变体"最长有效括号"用栈存下标 |
| 最大子数组和 | Kadane：dp[i] = max(dp[i-1] + a[i], a[i])，贪心滚动 |
| 买卖股票（一次） | 维护"至今最低价"，每天算差价取最大 |
| 环形链表 II | 快慢指针相遇后，慢指针从头再走，再次相遇即环入口 |
| 无重复最长子串 | 滑动窗口 + HashMap 记录字符最近下标 |
| 数组中的第 K 大 | 快排 partition 剪枝（平均 O(n)）或堆（O(n log k)） |
| 二叉树最近公共祖先 | 递归：左含 p 右含 q 则当前即 LCA |
| 字符串转换整数 | 状态机：空格/符号/数字/结束四态，防溢出判断 |
🎯 面试要点
- 刷题策略：高频 100 题反复刷，每题做到"不看答案 20 分钟写出来 + 讲清复杂度"
- 面试现场：先确认边界（空输入、极端值）→ 讲思路 → 写代码 → 手动跑例子 → 分析复杂度