手撕代码题

手撕代码环节重点不在"写出来"，而在于：先讲清思路 → 分析复杂度 → 写对边界 → 主动测试。本篇收录最高频的几类模板。

Q1: 手写快速排序 「🟢 校招/初级」

考察点：分治思想、分区逻辑、对不稳定性的认知。

参考答案：

public void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[lo + (hi - lo) / 2]; // 取中间值，降低有序数组退化概率
    int i = lo, j = hi;
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            int t = a[i]; a[i] = a[j]; a[j] = t;
            i++; j--;
        }
    }
    quickSort(a, lo, j);
    quickSort(a, i, hi);
}

• 平均 O(n log n)，最坏 O(n²)（有序 + 取首元素为基准）；空间 O(log n) 递归栈。
• 快排是不稳定排序；归并稳定但需要 O(n) 额外空间。

追问延伸：

• 怎么优化最坏情况？（随机化基准 / 三数取中）
• 数组第 K 大的数怎么用快排思想做到平均 O(n)？（快速选择）

Q2: 二分查找及常见变体 「🟢 校招/初级」

考察点：边界控制能力，while 条件与收缩方式必须一次写对。

参考答案：

// 闭区间 [lo, hi]
int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; // 防溢出
        if (a[mid] == target) return mid;
        else if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

常见变体：找第一个 ≥ target 的位置（左边界二分）、找最后一个 ≤ target 的位置。核心口诀：想清楚"区间定义"和"收缩时 mid 是否还可能是答案"。

追问延伸：

• 旋转排序数组怎么二分？
• 二分答案类题目（如"最小化最大值"）的套路？

Q3: 反转链表（迭代 + 递归两种写法） 「🟢 校招/初级」

考察点：指针操作基本功。

参考答案：

// 迭代
public ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

递归写法：head.next.next = head; head.next = null; 返回递归结果的尾。迭代是首选，递归考察你是否能讲清调用栈变化。

追问延伸：

• 反转链表的第 m 到 n 个节点？
• K 个一组反转链表？

Q4: 两数之和、三数之和 「🟢 校招/初级」

考察点：哈希表加速查找、排序 + 双指针去重。

参考答案：

• 两数之和：遍历数组，哈希表存 值→下标，查 target - num 是否存在，O(n)。
• 三数之和：先排序，固定一个数后用双指针在右侧区间找两数之和等于目标；去重靠跳过相同元素，O(n²)。

追问延伸：

• 四数之和怎么扩展？
• 为什么双指针解法必须先排序，排序后下标变了怎么办？

Q5: 动态规划入门：最长递增子序列 / 编辑距离 「🟡 中级」

考察点：能否定义状态、写出转移方程。

参考答案：

• LIS：dp[i] = 以 nums[i] 结尾的最长递增子序列长度；转移：dp[i] = max(dp[j]+1)，对所有 j<i 且 nums[j]<nums[i]。O(n²)，可用二分优化到 O(n log n)。
• 编辑距离：dp[i][j] 表示 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数；字符相同取左上角，不同取 插入/删除/替换 三者最小值 +1。
• 答题套路：定义状态含义 → 写转移方程 → 确定初始值和遍历方向 → 空间优化。

追问延伸：

• 0-1 背包和完全背包的遍历顺序差异？
• 怎么判断一个问题能不能用动态规划？（最优子结构 + 重叠子问题）

Q6: LRU 缓存怎么实现？ 「🟡 中级」

考察点：哈希表 + 双向链表的组合设计能力，超高频题。

参考答案：

• 结构：哈希表 key → 节点（O(1) 定位）+ 双向链表维护访问顺序（头部最新，尾部最旧）。
• get：命中则把节点移到头部；put：存在则更新并移到头部，不存在则插入头部，超容量则删除尾部节点并清理哈希表。
• Java 可直接继承 LinkedHashMap 重写 removeEldestEntry，但面试通常要求手写双向链表版。

class Node { int k, v; Node prev, next; Node(int k, int v) { this.k = k; this.v = v; } }
// 伪代码核心
Node get(int key) {
    Node n = map.get(key);
    if (n == null) return null;
    moveToHead(n);
    return n;
}

追问延伸：

• LFU 和 LRU 的区别？LFU 怎么实现？（双哈希 + 频次桶）
• Redis 的近似 LRU 是怎么做的？（采样淘汰，见 Redis 篇）