03-算法刷题路线

阶段：面试篇 ｜ 建议总量：热题 100 + 剑指 Offer 为主，200 题以内 ｜ 节奏：从进阶篇开始每天 2~3 题，面试前保持手感

一、刷题总原则

• 先专题后套卷：按下面的专题顺序集中攻一类套路，形成肌肉记忆；面试前一个月再刷 Hot 100 混排，模拟真实考试；
• 每天 2~3 题、限时：简单题 15 分钟、中等题 25 分钟、困难题 40 分钟；到时没思路就看题解，看懂后合上题解默写才算完成；
• 错题隔天重做：建一个”重刷清单”，3 天后重做仍能独立写出才打勾；面试前只重刷清单里的题；
• 一题多解：每题先写暴力解，再逐步优化，每个解法都说得出时间/空间复杂度——面试官就是要听你的优化过程；
• 总量控制：200 题以内、质量优先；刷 500 遘题不如把 150 道经典题刷透；
• 与指南进度配合：进阶篇开始同步刷数组与链表，03-面试篇期间完成主干专题，冲刺期每天 1 题保手感。

二、Java 刷题常用 API ⭐

// —— List / 数组 ——
List<Integer> list = new ArrayList<>();
list.add(1); list.get(0); list.size();
list.sort(Comparator.comparingInt(a -> a));        // List 自定义升序
Collections.sort(list, (a, b) -> b - a);           // 降序
int[] arr = {3, 1, 2};
Arrays.sort(arr);                                  // 数组排序（基本类型只能升序）
int[][] intervals = {{2, 1}, {3, 2}};
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);     // 二维数组按首元素升序（区间题必用）

// —— Deque：用 ArrayDeque 同时当栈和队列，比 Stack/LinkedList 快 ——
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.peek(); stack.pop();          // 栈：压 / 瞥 / 弹
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.peek(); queue.poll();        // 队列：入 / 瞥 / 出

// —— PriorityQueue 堆：Top K、堆排序题专用 ——
PriorityQueue<Integer> minHeap = new PriorityQueue<>();                  // 小顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);   // 大顶堆
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);    // 按元素第 2 位排序
minHeap.offer(1); minHeap.peek(); minHeap.poll();

// —— HashMap：计数、映射、前缀和 ——
Map<Character, Integer> map = new HashMap<>();
map.put('a', 1); map.get('a'); map.containsKey('a');
map.getOrDefault('b', 0);
map.merge('a', 1, Integer::sum);                   // 计数神器：不存在则 1，存在则累加
map.remove('a');

// —— 常用小工具 ——
// Character.isDigit(c)、c - '0' 转 int、Integer.parseInt(s)、String.valueOf(n)
// StringBuilder 拼接；s.toCharArray() 与 new String(chars) 互转
// Integer.MIN_VALUE / MAX_VALUE 做初始极值

二·补、复杂度与算法思想速查 ⭐

面试不只要写出代码，还会追问时间/空间复杂度与”为什么这么设计”。这一节是选择题与口头追问的高频弹药。

常见排序的复杂度（背表）：

• 口径：“最坏仍 O(nlogn)“只有归并（和堆排序）能保证；快排 O(nlogn) 是平均，最坏 O(n²) 是最常见的时间复杂度误解之一。
• 改进：三数取中 / 随机化基准 / 小区间切插入排序，可显著降低快排退化概率（工业库都这么做）。

看循环算复杂度：看每层循环的步进方式，不是嵌套层数。

for (int i = 1; i < n; i *= 2)      // i 每次翻倍 → 只执行 log n 次
    for (int j = 0; j < n; j++)     // 内层固定 n 次
        sum++;                       // 合计 O(n log n)，不是 O(n²)

• 记忆：i++ 是 n 次、i *= 2 或 i /= 2 是 logn 次；两层相乘。三层循环若外层是倍增，往往是 O(n²logn) 或 O(nlogn)。

建堆是 O(n)，不是 O(nlogn)（上界 ≠ 紧界）：自底向上建堆时，n 次 sift-down 的上界是 n×O(logn)，但实际代价按层求和——大部分节点在底层、下沉高度很小，Σ(每层节点数 × 该层最大下沉高度) 收敛于 O(n)。

• 对比：逐个 insert 建堆才是 O(nlogn)；这也是堆排序整体复杂度仍为 O(nlogn) 的原因（建堆 O(n) + n 次取堆顶并调整 O(nlogn)）。
• 另一个复杂度反直觉点：HashMap 平均 O(1)、最坏 O(n)（所有 key 冲突到同一桶；JDK 8 起链表超阈值转红黑树，最坏降为 O(logn)，详见《03-集合与泛型》）。

TopK / 第 K 大：小顶堆 O(n log K)：遍历 n 个数是 O(n)，每次入堆/出堆 O(logK)，合计 O(nlogK)；K 远小于 n 时明显优于整体排序的 O(nlogn)，且只需 O(K) 空间——“海量数据取 Top K”的标准解。选小顶堆是为了让堆顶正好是当前第 K 大，超出容量就弹掉堆顶。

二分的两种取整方向必须与收缩方向配套（死循环高发区）：下取整 mid = (l + r) / 2 在区间只剩两个元素时会等于 left，若用 left = mid 收缩则 left 永不前进 → 死循环。两种修法：① 改成 left = mid + 1（配 r = mid）；② 把 mid 改成上取整 (l + r + 1) / 2 再配 left = mid。背模板时两者必须成对记（模板 2 见下）。

三、专题路线表（顺序学习）⭐

四、手撕代码模板 ⭐（背诵级，面试默写）

模板 1：反转链表（LC206）

public ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;   // 先存后继
        curr.next = prev;            // 反转指向
        prev = curr;                 // 双指针前移
        curr = next;
    }
    return prev;                     // prev 即新头
}

模板 2：二分查找（LC704，左闭右闭）

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {                    // 区间合法才继续
        int mid = left + (right - left) / 2;   // 防溢出写法
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;   // 收缩左边界
        else right = mid - 1;
    }
    return -1;
}

模板 3：快速排序

public void quickSort(int[] nums, int left, int right) {
    if (left >= right) return;
    int pivot = nums[left], i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= pivot) j--;   // 右侧找小的
        while (i < j && nums[i] <= pivot) i++;   // 左侧找大的
        swap(nums, i, j);
    }
    swap(nums, left, i);                          // 基准归位
    quickSort(nums, left, i - 1);
    quickSort(nums, i + 1, right);
}
private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

模板 4：归并排序

public int[] mergeSort(int[] nums, int left, int right) {
    if (left == right) return new int[]{nums[left]};
    int mid = left + (right - left) / 2;
    int[] l = mergeSort(nums, left, mid), r = mergeSort(nums, mid + 1, right);
    int[] res = new int[l.length + r.length];
    int i = 0, j = 0, k = 0;
    while (i < l.length && j < r.length) res[k++] = l[i] <= r[j] ? l[i++] : r[j++];
    while (i < l.length) res[k++] = l[i++];
    while (j < r.length) res[k++] = r[j++];
    return res;
}

模板 5：BFS 层序遍历（LC102，网格 BFS 同骨架）

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();               // 固定本层节点数，实现"分层"
        List<Integer> level = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

模板 6：DFS 全排列（LC46，一切回溯题的骨架）

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(nums, new boolean[nums.length], new ArrayList<>(), res);
    return res;
}
private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));        // 必须拷贝快照
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true; path.add(nums[i]);     // 做选择
        dfs(nums, used, path, res);
        path.remove(path.size() - 1); used[i] = false;   // 撤销选择
    }
}

模板 7：LRU 缓存（LC146）——先说 LinkedHashMap 思路版

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);          // 第三个参数 accessOrder=true = 按访问顺序排序（false 则按插入序）
        this.capacity = capacity;
    }
    public int get(int key) { return super.getOrDefault(key, -1); }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;              // 超容量淘汰最久未访问
    }
}

模板 7（进阶）：手写 HashMap + 双向链表版

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0), tail = new Node(0, 0);  // 哨兵

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail; tail.prev = head;
    }
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node);                      // 刚访问的提到最前
        return node.value;
    }
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) { node.value = value; moveToHead(node); return; }
        if (map.size() == capacity) {          // 淘汰链表尾部（最久未用）
            Node last = tail.prev;
            remove(last); map.remove(last.key);
        }
        Node fresh = new Node(key, value);
        map.put(key, fresh); addToHead(fresh);
    }
    private void addToHead(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
    private void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void moveToHead(Node n) { remove(n); addToHead(n); }
    static class Node { int key, value; Node prev, next; Node(int k, int v) { key = k; value = v; } }
}

五、面试场景应对

五步法（按顺序执行，全程开口讲）：

1. 澄清题意：数据规模多大、是否有序/有重复、边界情况（空、单元素、负数），复述题目与面试官确认；
2. 说思路：先讲暴力解再讲优化方向，征求面试官同意后再动手，避免闷头写偏；
3. 报复杂度：时间/空间复杂度各是多少、为什么，这是面试官判断你是否受过训练的关键；
4. 动手写：变量命名规范、保持缩进，边写边讲；卡住就先写伪代码骨架再填实现；
5. 自测用例：写完主动跑一遍空输入、单元素、重复值等用例，自己先抓 bug 比被抓强。

平台注意事项：

• 白板/纸面：先写函数骨架再填细节，保持布局整洁，写完站在面试官角度”通读”一遍；
• 牛客 ACM 模式：要自己处理输入输出，提前练 Scanner/BufferedReader 读多行数据的标准套路；
• 共享文档（无编译器）：靠脑内编译，写完口头逐行过一遍用例，主动说”这里我检查一下越界”；
• 卡壳时：绝不沉默——大声思考，从 n=1、n=2 的小例子找规律，面试官往往在等你的思考过程而不是答案。

推荐资料