罗罗编程学习记录
本页内容 展开查看

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))。
  • 现场模板:先写暴力,再优化。

原理流程

  1. KMP next 数组:双指针,j 指向前缀末尾,i 指向当前位置;s[i]==s[j] 时 j++ 并记录 next[i],否则 j=next[j-1]。
  2. KMP 匹配:双指针 i 遍历文本,j 遍历模式串;失配时 j=next[j-1]。
  3. 回文中心扩展:枚举中心(奇数/偶数),向两侧扩展。

代码 / 示例

// 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,维护窗口内状态。

原理流程

  1. 快慢指针:for fast in 0..n,if 满足条件 nums[slow++]=nums[fast]。
  2. 左右指针:while l<r,根据条件移动 l 或 r。
  3. 滑动窗口: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 走两步,相遇则有环。
  • 哑节点:简化头节点操作。

原理流程

  1. 反转:while curr != null,next=curr.next,curr.next=prev,prev=curr,curr=next。
  2. 环检测:slow=head,fast=head;while fast!=null && fast.next!=null,slow=slow.next,fast=fast.next.next,相遇则有环。
  3. 合并: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:队列,逐层。
  • 重构:前序第一个是根,中序找根位置划分左右。

原理流程

  1. DFS:if root==null return;处理 root;dfs(root.left);dfs(root.right)。
  2. BFS:Queue q,q.offer(root),while !q.isEmpty,for 遍历当前层。
  3. 重构:前序确定根,中序划分左右子树递归。

代码 / 示例

// 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 背包逆序(防止重复取),完全背包正序。

原理流程

  1. 定义状态:如 dp[i][j] = 前 i 个物品容量 j 的最大价值。
  2. 转移:dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。
  3. 初始化:dp[0][] = 0,dp[][0] = 0。
  4. 遍历顺序: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. 写完代码,口头列边界用例。
  2. 逐个验证(白板上模拟或口头)。
  3. 发现问题立即修正。

代码 / 图示

数组题:[]、[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. 题目 -> 复述题意。
  2. 确认输入输出、边界。
  3. 说暴力思路和复杂度。
  4. 说优化思路和复杂度。
  5. 面试官同意 -> 写代码。
  6. 写完列边界用例验证。
  7. 说时间空间复杂度。

代码 / 图示

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)。

原理流程

  1. 写完代码,先看循环层数。
  2. 再看递归深度。
  3. 最后看额外数据结构空间。

代码 / 图示

双指针: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:算,递归深度就是栈空间。

待整理清单

  • [ ] 动态规划题型分类速查
  • [ ] 图论题型模板
  • [ ] 现场手撕常见错误清单