02.10.5 高频手撕代码清单
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.10 设计类与手写题
覆盖范围
- 字符串/数组/链表/树/DP 现场模板
- 边界与测试用例写法
- 白板沟通节奏
高频题速览
| 编号 | 题目 | 难度 | 频率 |
|---|---|---|---|
| 02.10.5-001 | 字符串现场模板(KMP/回文) | 进阶 | ★★★★ |
| 02.10.5-002 | 数组现场模板(双指针/滑窗) | 基础 | ★★★★★ |
| 02.10.5-003 | 链表现场模板(反转/环) | 基础 | ★★★★★ |
| 02.10.5-004 | 树现场模板(DFS/BFS/重构) | 基础 | ★★★★★ |
| 02.10.5-005 | DP 现场模板(背包/子序列) | 进阶 | ★★★★ |
| 02.10.5-006 | 边界与测试用例写法 | 基础 | ★★★★ |
| 02.10.5-007 | 白板沟通节奏 | 基础 | ★★★★★ |
| 02.10.5-008 | 常见手撕题复杂度速查 | 基础 | ★★★★ |
02.10.5-001 字符串现场模板(KMP/回文)
频率 ★★★★ | 难度 进阶
一句话结论
KMP 现场先写 next 数组(前缀函数),再匹配;回文用中心扩展或 Manacher;字符串题目先判断是否暴力可过,再优化。
概念解释
- KMP:next[i] 表示模式串前 i 个字符的最长相等前后缀长度。
- 回文:中心扩展(O(n^2))或 Manacher(O(n))。
- 现场模板:先写暴力,再优化。
原理流程
- KMP next 数组:双指针,j 指向前缀末尾,i 指向当前位置;s[i]==s[j] 时 j++ 并记录 next[i],否则 j=next[j-1]。
- KMP 匹配:双指针 i 遍历文本,j 遍历模式串;失配时 j=next[j-1]。
- 回文中心扩展:枚举中心(奇数/偶数),向两侧扩展。
代码 / 示例
// KMP next 数组
int[] buildNext(String p) {
int[] next = new int[p.length()];
for (int i = 1, j = 0; i < p.length(); i++) {
while (j > 0 && p.charAt(i) != p.charAt(j)) j = next[j - 1];
if (p.charAt(i) == p.charAt(j)) j++;
next[i] = j;
}
return next;
}
// 回文中心扩展
String longestPalindrome(String s) {
int start = 0, maxLen = 0;
for (int i = 0; i < s.length(); i++) {
int l1 = expand(s, i, i), l2 = expand(s, i, i + 1);
int len = Math.max(l1, l2);
if (len > maxLen) { maxLen = len; start = i - (len - 1) / 2; }
}
return s.substring(start, start + maxLen);
}
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;
}
常见误区
- 误区:next 数组从 -1 开始;正解:Java 常用 0 开始,next[0]=0。
- 误区:中心扩展只考虑奇数;正解:奇数(i,i)和偶数(i,i+1)都要。
追问 / 延伸
- Q:Manacher 现场写得出吗? A:Manacher 细节多,现场写暴力中心扩展即可,Manacher 作为延伸。
- Q:字符串哈希? A:Rabin-Karp,哈希冲突时用双哈希。
02.10.5-002 数组现场模板(双指针/滑窗)
频率 ★★★★★ | 难度 基础
一句话结论
双指针:快慢指针(原地删除)、左右指针(有序数组)、滑动窗口;现场先判断是否有序、是否需要原地操作,再选模板。
概念解释
- 快慢指针:slow 指向结果末尾,fast 遍历。
- 左右指针:l=0、r=n-1,向中间收缩。
- 滑动窗口:left、right,维护窗口内状态。
原理流程
- 快慢指针:for fast in 0..n,if 满足条件 nums[slow++]=nums[fast]。
- 左右指针:while l<r,根据条件移动 l 或 r。
- 滑动窗口:right 扩展,left 收缩,维护窗口内计数。
代码 / 示例
// 快慢指针:原地删除等于 val 的元素
int removeElement(int[] nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++)
if (nums[fast] != val) nums[slow++] = nums[fast];
return slow;
}
// 滑动窗口:最长无重复子串
int lengthOfLongestSubstring(String s) {
int[] cnt = new int[128];
int left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
cnt[s.charAt(right)]++;
while (cnt[s.charAt(right)] > 1) cnt[s.charAt(left++)]--;
ans = Math.max(ans, right - left + 1);
}
return ans;
}
常见误区
- 误区:滑动窗口 left 收缩条件写错;正解:先扩展 right,再收缩 left 到满足条件。
- 误区:快慢指针 slow 初始为 0 还是 1;正解:slow 指向下一个写入位置,初始 0。
追问 / 延伸
- Q:滑动窗口和前缀和区别? A:滑动窗口维护连续区间,前缀和维护区间和。
- Q:数组题现场先写什么? A:先判断是否需要原地,再判断是否有序,选模板。
02.10.5-003 链表现场模板(反转/环)
频率 ★★★★★ | 难度 基础
一句话结论
反转链表:三指针 prev/curr/next;环检测:快慢指针;找中点:快慢指针;合并两个有序链表:哑节点 + 双指针。
概念解释
- 三指针反转:prev、curr、next,每次反转 curr.next 指向 prev。
- 快慢指针:slow 走一步,fast 走两步,相遇则有环。
- 哑节点:简化头节点操作。
原理流程
- 反转:while curr != null,next=curr.next,curr.next=prev,prev=curr,curr=next。
- 环检测:slow=head,fast=head;while fast!=null && fast.next!=null,slow=slow.next,fast=fast.next.next,相遇则有环。
- 合并:dummy 节点,比较 l1/l2 值,小的接上。
代码 / 示例
// 反转链表
ListNode reverse(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// 环检测
boolean hasCycle(ListNode head) {
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;
}
// 合并两个有序链表
ListNode mergeTwo(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = l1 != null ? l1 : l2;
return dummy.next;
}
常见误区
- 误区:反转链表忘记保存 next;正解:先存 next 再改 curr.next。
- 误区:快慢指针 fast 初始为 head 还是 head.next;正解:都可以,只要循环条件正确。
追问 / 延伸
- Q:找环入口? A:快慢相遇后,一个指针回到 head,两个指针同速走,相遇点即入口。
- Q:链表题现场先写什么? A:先判断是否需要哑节点,再判断是否需要快慢指针。
02.10.5-004 树现场模板(DFS/BFS/重构)
频率 ★★★★★ | 难度 基础
一句话结论
DFS 递归:先写终止条件,再写当前层逻辑,再递归子节点;BFS:队列逐层遍历;树的重构:根据遍历序列特点(前序+中序、后序+中序)递归构建。
概念解释
- DFS:递归,简洁但注意栈溢出。
- BFS:队列,逐层。
- 重构:前序第一个是根,中序找根位置划分左右。
原理流程
- DFS:if root==null return;处理 root;dfs(root.left);dfs(root.right)。
- BFS:Queue
q,q.offer(root),while !q.isEmpty,for 遍历当前层。 - 重构:前序确定根,中序划分左右子树递归。
代码 / 示例
// DFS:前序遍历
void preorder(TreeNode root, List<Integer> res) {
if (root == null) return;
res.add(root.val);
preorder(root.left, res);
preorder(root.right, res);
}
// BFS:层序遍历
List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new java.util.LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode n = q.poll();
level.add(n.val);
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
res.add(level);
}
return res;
}
// 重构:前序+中序
TreeNode buildTree(int[] preorder, int[] inorder) {
java.util.Map<Integer, Integer> inMap = new java.util.HashMap<>();
for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
return build(preorder, 0, preorder.length - 1, inMap, 0, inorder.length - 1);
}
TreeNode build(int[] pre, int preL, int preR, java.util.Map<Integer, Integer> inMap, int inL, int inR) {
if (preL > preR) return null;
int rootVal = pre[preL];
TreeNode root = new TreeNode(rootVal);
int inRoot = inMap.get(rootVal);
int leftLen = inRoot - inL;
root.left = build(pre, preL + 1, preL + leftLen, inMap, inL, inRoot - 1);
root.right = build(pre, preL + leftLen + 1, preR, inMap, inRoot + 1, inR);
return root;
}
常见误区
- 误区:BFS 忘记记录层 size;正解:每层先记录 size,for 遍历当前层。
- 误区:重构时左右子树范围写错;正解:前序根之后,左子树长度 = 中序根位置 - 中序左边界。
追问 / 延伸
- Q:DFS 递归栈溢出? A:树深度大时(如 10 万)递归栈溢出,改迭代。
- Q:Morris 遍历? A:O(1) 空间遍历,利用叶子节点空指针,现场一般不要求。
02.10.5-005 DP 现场模板(背包/子序列)
频率 ★★★★ | 难度 进阶
一句话结论
DP 先定义状态(dp[i][j] 含义),再写转移方程,再确定遍历顺序,最后初始化;背包问题:01 背包逆序遍历,完全背包正序遍历;子序列问题:双串 DP。
概念解释
- 状态定义:dp[i][j] 表示什么。
- 转移方程:dp[i][j] 由哪些状态推出。
- 遍历顺序:01 背包逆序(防止重复取),完全背包正序。
原理流程
- 定义状态:如 dp[i][j] = 前 i 个物品容量 j 的最大价值。
- 转移:dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。
- 初始化:dp[0][] = 0,dp[][0] = 0。
- 遍历顺序:01 背包逆序 j,完全背包正序 j。
代码 / 示例
// 01 背包
int knapsack(int[] w, int[] v, int cap) {
int[] dp = new int[cap + 1];
for (int i = 0; i < w.length; i++)
for (int j = cap; j >= w[i]; j--)
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
return dp[cap];
}
// 最长公共子序列
int longestCommonSubsequence(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
return dp[m][n];
}
常见误区
- 误区:01 背包正序遍历;正解:正序会导致同一物品被重复取(变成完全背包)。
- 误区:DP 状态定义不清;正解:先写清楚 dp[i][j] 表示什么,再写转移。
追问 / 延伸
- Q:完全背包和 01 背包区别? A:完全背包物品可重复取,正序遍历。
- Q:DP 现场先写什么? A:先定义状态,再写转移方程,再写遍历顺序。
02.10.5-006 边界与测试用例写法
频率 ★★★★ | 难度 基础
一句话结论
手撕题写完后主动列边界用例:空输入、单元素、极值、重复元素、逆序、全相同;白板上口头说明用例并验证。
概念解释
- 空输入:数组空、链表空、字符串空。
- 单元素:长度 1。
- 极值:最大值、最小值、int 溢出。
- 重复:全相同、全部重复。
原理流程
- 写完代码,口头列边界用例。
- 逐个验证(白板上模拟或口头)。
- 发现问题立即修正。
代码 / 图示
数组题:[]、[1]、[1,2,3]、[3,2,1]、[1,1,1]、[Integer.MAX_VALUE]
链表题:null、单节点、两节点、有环、无环
树题:null、单节点、左斜树、右斜树、完全二叉树
DP 题:n=0、n=1、n=最大值、全相同元素
常见误区
- 误区:只写正常用例;正解:主动列边界用例,面试官看重这个。
- 误区:边界用例只列不验证;正解:白板上模拟验证。
追问 / 延伸
- Q:白板上怎么列用例? A:口头说"空输入、单元素、极值",然后模拟跑一遍。
- Q:int 溢出怎么处理? A:用 long 或检查边界。
02.10.5-007 白板沟通节奏
频率 ★★★★★ | 难度 基础
一句话结论
听到题先复述题意、确认输入输出边界、说思路(暴力 + 优化)、面试官同意后写代码、写完列边界用例验证;全程口头思考,不要闷头写。
概念解释
- 复述:确认理解正确。
- 确认边界:空输入、单元素、极值。
- 说思路:暴力 + 优化,说清复杂度。
- 写代码:面试官同意后再写。
- 验证:列边界用例。
原理流程
- 题目 -> 复述题意。
- 确认输入输出、边界。
- 说暴力思路和复杂度。
- 说优化思路和复杂度。
- 面试官同意 -> 写代码。
- 写完列边界用例验证。
- 说时间空间复杂度。
代码 / 图示
1. 复述题意(30s)
2. 确认边界(30s)
3. 说思路(2min)
4. 写代码(5min)
5. 验证(2min)
6. 总结(30s)
常见误区
- 误区:直接写代码;正解:先沟通思路,面试官同意后再写。
- 误区:闷头写;正解:全程口头思考,让面试官知道你在想什么。
追问 / 延伸
- Q:面试官说"你直接写"? A:那快速说思路(10s)后写。
- Q:写代码卡壳怎么办? A:说思路,让面试官提示,不要沉默。
02.10.5-008 常见手撕题复杂度速查
频率 ★★★★ | 难度 基础
一句话结论
手撕题写完必须报时间空间复杂度;常见题:双指针 O(n)、滑窗 O(n)、二分 O(log n)、归并 O(n log n)、DP O(n^2) 或 O(n)、DFS/BFS O(V+E)、链表反转 O(n)、树遍历 O(n)。
概念解释
- 时间复杂度:最坏情况下的操作次数。
- 空间复杂度:额外空间(不含输入)。
- 均摊 vs 最坏:如动态数组扩容是均摊 O(1)。
原理流程
- 写完代码,先看循环层数。
- 再看递归深度。
- 最后看额外数据结构空间。
代码 / 图示
双指针:O(n) 时间,O(1) 空间
滑动窗口:O(n) 时间,O(k) 空间(k 为字符集)
二分查找:O(log n) 时间,O(1) 空间
归并排序:O(n log n) 时间,O(n) 空间
01 背包:O(n*cap) 时间,O(cap) 空间
LCS:O(m*n) 时间,O(m*n) 空间
DFS:O(V+E) 时间,O(V) 栈空间
BFS:O(V+E) 时间,O(V) 队列空间
链表反转:O(n) 时间,O(1) 空间
树遍历:O(n) 时间,O(h) 栈空间
常见误区
- 误区:只说时间不说空间;正解:时间空间都要说。
- 误区:滑动窗口是 O(n^2);正解:right 走 n 步,left 走 n 步,合计 O(n)。
追问 / 延伸
- Q:均摊和最坏区别? A:均摊是多次操作平均,最坏是单次上限。
- Q:递归栈空间算空间复杂度吗? A:算,递归深度就是栈空间。
待整理清单
- [ ] 动态规划题型分类速查
- [ ] 图论题型模板
- [ ] 现场手撕常见错误清单