Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

算法补充专题

Hot 100 没专门成章, 但面试 (尤其国内) 高频会问的经典主题. 本章按 “如何理解题目 → 为什么选算法 → 核心思想 → C++ 模板 → 易错点” 来写. 目标不是让你背代码, 而是让你知道题目出现某些信号时该选什么算法.

优先级: 排序手写 ⭐, 位运算 ⭐, 前缀和 / 差分, 并查集, 设计题. 排序和位运算几乎必问; 并查集和前缀和是中高频; LFU 等设计题偏大厂.

代码上下文: 示例使用 C++17, 省略重复的标准库头文件和 using namespace std;. 片段按文中给出的前置条件使用; 复制到独立文件时, 需要补齐该片段使用的标准库头文件.

进度自测

  • ⭐ 手写快速排序: 能解释分区, 平均 / 最坏复杂度, 为什么不稳定
  • ⭐ 手写归并排序: 能解释稳定性, 为什么链表排序常用归并
  • ⭐ 手写堆排序: 能解释建堆, 下沉, 为什么堆适合 Top K
  • 排序对比: 稳定性 / 复杂度 / 适用场景
  • ⭐ 位运算基础: & | ^ ~ << >>
  • ⭐ n & (n - 1), 判 2 的幂, 统计 1 的个数
  • 出现 3 次只出 1 次, 子集枚举, 状态压缩
  • 并查集模板: find 路径压缩 + union 按秩 / 按大小
  • 并查集应用: 省份数量 547 / 冗余连接 684
  • 一维前缀和 / 二维前缀和
  • 差分数组: 区间增减
  • 设计题: LFU 460 / 用栈实现队列 232 / 循环队列 622

学习目标与章节边界

本章训练可迁移的算法专题: 排序性质, 并查集, 前缀和与数据结构组合; 具体 Hot 100 题的逐题推导, 代码与边界统一在 LeetCode Hot 100 算法清单的 “核心题完整教学单元”, 数据超过单机内存时改看海量数据处理. 完成后应能写出专题模板, 给出复杂度推导, 并用一个反例解释选型边界.

学算法的通用方法

很多人学算法痛苦, 是因为一上来就背代码. 正确顺序应该是:

  1. 先翻译题目: 题目到底让你求什么? 是存在性, 数量, 最大最小, 所有方案, 还是设计接口?
  2. 看限制条件: 时间, 空间, 输入规模决定算法上限.
  3. 识别关键词: 有序, 连续, 频次, 连通, 区间修改, Top K, 出现次数.
  4. 先说暴力: 暴力怎么做? 复杂度多少? 为什么不够?
  5. 再选算法: 说明这个算法利用了题目的哪个性质.
  6. 最后写模板: 写稳定模板, 不要临场发明边界.

面试中可以这样表达:

暴力做法是 [暴力方案], 复杂度为 [暴力复杂度].题目要求 / 数据规模不允许. 这里有 [题目特征], 所以我选 [算法名称].核心是 [核心性质], 实现上维护 [关键状态], 复杂度为 [目标复杂度].

时间复杂度和空间复杂度

令 n 为输入规模, 例如数组长度, 节点数或字符串长度. 复杂度描述 n 增大时资源消耗的渐进增长, 不是某台机器上的精确耗时. 忽略常数和低阶项: 3n^2 + 2n + 1 是 Theta(n^2), 因为大 n 时二次项主导; 但常数在实际约束下仍会影响能否通过.

  • O(f(n)) 是渐进上界, Omega(f(n)) 是渐进下界, Theta(f(n)) 同时给出紧确的上, 下界. 面试通常报 O 作为可保证的上界, 但不能把 O(n^2) 误说成一定是 Theta(n^2).
  • 最好, 平均和最坏复杂度分别对应最有利, 按输入分布期望和最不利的输入. 摊还复杂度把一系列操作的总成本均摊到单次操作, 例如动态数组扩容的单次追加摊还为 O(1), 不表示每次追加都只执行常数次复制.
  • 空间复杂度要说明口径: 额外空间是不含输入本身的辅助内存; 递归还要计入调用栈. 例如归并排序通常额外 O(n), 二分查找的迭代写法额外 O(1), 递归写法还占 O(log n) 栈空间.

常见增长从低到高是 O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), O(n!). 二分查找每轮将候选规模减半, 经过 k 轮满足 n / 2^k <= 1, 所以 k = O(log n); 两层各扫描 n 次的嵌套循环执行约 n * n 次, 因此是 O(n^2). 选型还必须代入约束: n 为 10^5 时通常应避免 O(n^2), n 为 20 左右时 O(2^n) 的状态枚举可能可行, O(n!) 则往往只适合更小的 n 或强剪枝.

1. 手写排序 (⭐ 国内几乎必问)

如何理解排序题

面试让你手写排序, 不是考你会不会调用 sort, 而是考你是否理解:

  • 为什么平均是 O (n log n)?
  • 最坏情况什么时候出现?
  • 是否稳定?
  • 是否原地?
  • 适合数组还是链表?
  • 工程里什么时候不用自己写?

常见选择:

  • 快速排序: 数组通用排序, 平均快, 原地, 但不稳定, 最坏 O (n²).
  • 归并排序: 稳定, 复杂度稳定 O (n log n), 需要 O (n) 空间, 适合链表和外部排序.
  • 堆排序: 原地, 最坏 O (n log n), 不稳定; 思想和优先队列 / Top K 相关.

1.1 快速排序

核心思想

快排是分治:

  1. 选一个基准值 pivot.
  2. 分区: 小于 pivot 的放左边, 大于等于 pivot 的放右边.
  3. pivot 归位后, 递归排序左右两边.

关键理解: 分区后 pivot 的最终位置已经确定, 后续不需要再动它.

C++ 模板

#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

int partition(vector<int>& a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo; // [lo, i) 都小于 pivot
    for (int j = lo; j < hi; ++j) {
        if (a[j] < pivot) {
            swap(a[i], a[j]);
            i++;
        }
    }
    swap(a[i], a[hi]);
    return i;
}

void quickSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

怎么向面试官解释

  • 平均复杂度 O (n log n):每次分区 O (n), 理想情况下递归深度 log n.
  • 最坏 O (n²):如果数组已经有序且每次选端点作 pivot, 每次只减少一个元素.
  • 额外空间平均 O (log n), 最坏 O (n):递归栈深度取决于分区是否均衡.
  • 不稳定: 交换会打乱相等元素的原始顺序.

优化

  • 随机 pivot: 降低遇到最坏情况的概率.
  • 三数取中: 从头, 中, 尾选中位数作 pivot.
  • 重复值很多时使用三路分区, 避免大量相等元素导致分区极度不均衡.
  • 小数组用插入排序: 工程优化.

一次分区 trace: 数组 [4,2,5,2,3], 以末尾 3 为 pivot. 扫描到 2 时交换到左区, 扫描到第二个 2 时再交换, 扫描结束得到 [2,2,3,4,5], pivot 位于 2; 递归只处理 [2,2] 与 [4,5]. 这里的 “不稳定” 也可见于携带原始序号的 (2,A),(2,B): 跨 pivot 的交换可能改变 A/B 顺序.

int randomizedPartition(vector<int>& a, int lo, int hi) {
    int pivotIndex = lo + rand() % (hi - lo + 1);
    swap(a[pivotIndex], a[hi]);
    return partition(a, lo, hi); // 依赖本节已有 Lomuto partition
}

void quickSort3Way(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int pivotIndex = lo + rand() % (hi - lo + 1);
    int pivot = a[pivotIndex];
    swap(a[lo], a[pivotIndex]);
    int lt = lo, i = lo + 1, gt = hi;
    while (i <= gt) {
        if (a[i] < pivot) swap(a[lt++], a[i++]);
        else if (a[i] > pivot) swap(a[i], a[gt--]);
        else ++i;
    }
    quickSort3Way(a, lo, lt - 1);
    quickSort3Way(a, gt + 1, hi);
}

随机 pivot 不改变最坏 O(n^2), 但使对固定输入的期望复杂度为 O(n log n); 三路分区将等于 pivot 的元素一次性跳过, 重复值很多时明显减少递归. 边界: 全相等数组应令三路分区一次结束; rand() 仅作教学随机化, 生产代码使用 <random> 的确定性种子策略或标准库排序.

1.2 归并排序

核心思想

归并排序也是分治:

  1. 把数组从中间拆成两半.
  2. 分别递归排序.
  3. 合并两个有序数组.

它稳定, 是因为合并时如果左右元素相等, 先放左边元素, 就保持了原始相对顺序.

C++ 模板

void mergeSort(vector<int>& a, int lo, int hi, vector<int>& tmp) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid, tmp);
    mergeSort(a, mid + 1, hi, tmp);

    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++]; // <= 保证稳定
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi) tmp[k++] = a[j++];

    for (int x = lo; x <= hi; ++x) a[x] = tmp[x];
}

void mergeSort(vector<int>& a) {
    if (a.empty()) return;
    vector<int> tmp(a.size());
    mergeSort(a, 0, static_cast<int>(a.size()) - 1, tmp);
}

适用场景

  • 需要稳定排序.
  • 链表排序: 链表合并两个有序链表很方便, 不需要随机访问.
  • 外部排序: 数据太大放不进内存时, 可以分块排序再多路归并.

1.3 堆排序

核心思想

堆是一棵完全二叉树, 用数组表示:

  • 下标 i 的左孩子: 2*i + 1
  • 下标 i 的右孩子: 2*i + 2
  • 下标 i 的父节点: (i - 1) / 2

大顶堆满足: 每个节点都大于等于孩子. 因此堆顶是最大值.

堆排序流程:

  1. 建大顶堆.
  2. 把堆顶最大值交换到数组末尾.
  3. 缩小堆范围, 对新堆顶下沉.
  4. 重复直到有序.

C++ 模板

void sink(vector<int>& a, int root, int n) {
    while (true) {
        int largest = root;
        int l = root * 2 + 1;
        int r = root * 2 + 2;
        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == root) break;
        swap(a[root], a[largest]);
        root = largest;
    }
}

void heapSort(vector<int>& a) {
    int n = a.size();
    for (int i = n / 2 - 1; i >= 0; --i) sink(a, i, n); // 建堆
    for (int end = n - 1; end > 0; --end) {
        swap(a[0], a[end]);
        sink(a, 0, end);
    }
}

怎么理解建堆 O (n)

不是每个节点都下沉 log n. 底层节点很多但下沉距离短, 上层节点少但下沉距离长, 总和是 O (n).面试一般说结论即可.

1.4 冒泡排序的可验证优化

冒泡排序相邻比较并交换逆序元素, 每轮会把当前无序区的最大值送到右侧. 只在 a[j] > a[j + 1] 时交换, 相等元素不交换, 因此它是稳定排序. 基础实现最好, 平均, 最坏时间分别为 O(n), O(n^2), O(n^2) (最好情况依赖提前退出), 空间 O(1); 工程中通常使用标准库排序, 此处用于理解交换和边界.

void bubbleSort(vector<int>& a) {
    int unsortedEnd = static_cast<int>(a.size()) - 1;
    while (unsortedEnd > 0) {
        int lastSwap = -1;
        for (int j = 0; j < unsortedEnd; ++j) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                lastSwap = j;
            }
        }
        if (lastSwap == -1) break; // 本轮没有交换,数组已有序
        unsortedEnd = lastSwap;
    }
}

lastSwap 之后的区间在本轮没有发生交换, 已经有序, 下一轮无需再扫描. -1 专门表示本轮没有交换, 因此不会与索引 0 发生交换混淆. 用 [1,2,3,4] 验证首次扫描即退出; 用 [3,2,1] 验证连续交换得到 [1,2,3].

1.5 红黑树: 有界高度的有序映射基础

红黑树是带颜色约束的二叉搜索树. 它满足二叉搜索树顺序, 并维持以下关键性质:

  • 根节点为黑色.
  • 所有空叶子节点 (概念上的 NIL) 为黑色.
  • 红色节点的子节点都是黑色, 不存在连续红节点.
  • 从任一节点到其所有后代 NIL 叶子的路径, 黑色节点数相同, 称为黑高一致.

这些约束限制了最长路径不会超过最短路径的两倍, 因而树高为 O(log n), 查找, 插入和删除都能保持 O(log n). 工程上它适合需要按键有序遍历, 范围查询或有序映射 / 集合的场景; 具体 JDK 类采用何种内部实现和阈值会随版本变化, 不应把某个 JDK 的细节当作通用承诺.

插入新节点通常先按普通二叉搜索树插入并标红, 以免立即改变各路径黑高. 若出现红父子冲突:

  1. 叔节点为红: 将父和叔染黑, 祖父染红, 把检查上移到祖父.
  2. 叔节点为黑或 NIL: 先将 “内侧” 形状旋转为 “外侧”, 再围绕祖父旋转, 并交换父 / 祖父的颜色.

修复循环结束后必须无条件将根节点染黑, 包括首次插入以及叔节点为红, 检查上移到根的情形; 这样才能恢复根为黑色的性质.

以左左形状为例, grandparent 的左孩子 parent 和 parent 的左孩子 node 均为红. 对祖父右旋, 然后将 parent 染黑, grandparent 染红; 中序顺序仍是 left < parent < grandparent < right, 所以旋转没有破坏二叉搜索树顺序, 只调整了局部父子关系.

删除若移除了黑节点, 可能使某一路少一个黑色. 修复围绕 “带额外黑色” 的节点及其兄弟进行: 兄弟为红时先旋转并换色, 转成兄弟为黑的情况; 兄弟及其子节点都黑时把兄弟染红并把问题上移; 兄弟有靠外的红孩子时, 通过一次或两次旋转和重新着色让路径黑高恢复. 面试回答重点是 “旋转保持中序顺序, 变色恢复红节点和黑高约束”, 不必背诵某个库的全部分支代码.

排序对比 (高频问)

算法平均最坏额外空间稳定核心用途
快排O (n log n)O (n²)O (log n)否数组通用排序, 实际很快
归并O (n log n)O (n log n)O (n)是稳定排序, 链表排序, 外部排序
堆排O (n log n)O (n log n)O (1)否原地排序, 理解 Top K
插入O (n²)O (n²)O (1)是小数组, 近乎有序数组
冒泡O (n²)O (n²)O (1)是教学, 提前退出时最好 O (n)

易错点

  • 快排分区时循环边界最容易错, 建议固定一种 partition 写法.
  • 快排不是稳定排序.
  • 归并合并时 <= 才能保持稳定.
  • 堆排序下沉范围 n 是当前堆大小, 不是数组总长度.
  • Java 中基本类型 Arrays.sort(int[]) 不是稳定排序; 对象数组排序是稳定的 TimSort.

2. 位运算专题 (⭐)

如何理解位运算题

位运算题常见信号:

  • 数字出现次数有规律: 一个出现一次, 其余出现两次 / 三次.
  • 要求 O (1) 额外空间.
  • 需要表示集合状态: 选/不选, 访问/未访问.
  • 需要判断奇偶, 2 的幂, 某一位是否为 1.

位运算本质是把整数看成二进制位数组.

基础运算

运算含义例子
&两位都为 1 才为 1判断某位是否为 1
``有一位为 1 就为 1
^相同为 0, 不同为 1成对抵消
~按位取反掩码处理
<<左移, 乘 21 << i 表示第 i 位
>>右移取高位 / 除 2

必背技巧

以下是表达式速记, 不是可独立编译的函数:

n & (n - 1);       // 消除最低位的 1
n & -n;            // 取最低位的 1,也叫 lowbit
(n & (n - 1)) == 0 // 判断 2 的幂,前提 n > 0
(x >> i) & 1;      // 取第 i 位
x | (1 << i);      // 把第 i 位置 1
x & ~(1 << i);     // 把第 i 位置 0
x ^ (1 << i);      // 翻转第 i 位

异或为什么能找单身数

异或有三个性质:

  • a ^ a = 0
  • a ^ 0 = a
  • 交换律和结合律成立

所以一堆数里, 成对出现的数字都会抵消, 最后剩下只出现一次的数.

int singleNumber(vector<int>& nums) {
    int ans = 0;
    for (int x : nums) ans ^= x;
    return ans;
}

统计 1 的个数

int hammingWeight(unsigned int n) {
    int cnt = 0;
    while (n != 0) {
        n &= (n - 1); // 每次消掉一个最低位的 1
        cnt++;
    }
    return cnt;
}

复杂度不是固定 32 次, 而是和 1 的个数有关.

判 2 的幂

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

理解: 2 的幂二进制只有一个 1, 例如 8 是 1000, 7 是 0111, 相与为 0.

出现 3 次, 只出现 1 次

思路: 每一位单独统计 1 的个数. 如果其他数都出现 3 次, 那么每一位的计数对 3 取模后, 剩下的就是只出现一次的数在这一位上的值.

#include <cstdint>

int32_t singleNumberII(vector<int>& nums) {
    uint32_t ans = 0;
    for (int i = 0; i < 32; ++i) {
        int cnt = 0;
        for (int x : nums) {
            uint32_t bits = static_cast<uint32_t>(x);
            if ((bits >> i) & 1u) cnt++;
        }
        if (cnt % 3) ans |= (uint32_t{1} << i);
    }
    return static_cast<int32_t>(ans);
}

子集枚举

如果 n 比较小, 可以用一个整数 mask 表示选了哪些元素.

vector<vector<int>> subsets(vector<int>& nums) {
    int n = nums.size();
    if (n >= 31) throw invalid_argument("subsets requires n < 31");
    vector<vector<int>> res;
    uint32_t total = uint32_t{1} << n;
    for (uint32_t mask = 0; mask < total; ++mask) {
        vector<int> cur;
        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1u) cur.push_back(nums[i]);
        }
        res.push_back(cur);
    }
    return res;
}

易错点

  • 判断 2 的幂必须加 n > 0.
  • 左移注意溢出, 1 << 31 对有符号 int 有风险, 必要时用 1LL.
  • C++ 负数右移和符号位相关, 题目涉及无符号时用 unsigned 更清晰.

3. 并查集 (Union-Find)

如何理解题目

并查集专门处理 “分组” 和 “连通性”.看到这些表达可以优先想并查集:

  • 两个元素是否属于同一组.
  • 不断合并集合.
  • 最后有几个连通分量.
  • 加一条边会不会形成环.

典型题: 省份数量, 冗余连接, 等式方程可满足性.

为什么选并查集

如果每次都 DFS/BFS 判断两个点是否连通, 多次查询会很慢. 并查集把每个集合用一个代表元表示, 合并和查询都接近 O (1).

核心思想

  • parent[x] 表示 x 的父节点.
  • 如果 parent[x] == x, x 是这个集合的根.
  • find(x) 找 x 的根.
  • union(a, b) 把两个集合合并.

两个优化:

  1. 路径压缩: find 时把沿途节点直接挂到根上.
  2. 按秩 / 按大小合并: 小树挂到大树下, 避免树太高.

C++ 模板

class UnionFind {
    vector<int> parent;
    vector<int> size;
public:
    int count;

    UnionFind(int n) : parent(n), size(n, 1), count(n) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) swap(ra, rb);
        parent[rb] = ra;
        size[ra] += size[rb];
        count--;
        return true;
    }

    bool connected(int a, int b) {
        return find(a) == find(b);
    }
};

应用: 547 省份数量

下面的函数依赖上一小节定义的 UnionFind 类型, 不是独立代码块.

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    UnionFind uf(n);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (isConnected[i][j] == 1) uf.unite(i, j);
        }
    }
    return uf.count;
}

应用: 684 冗余连接

遍历边 (u, v):

  • 如果 u 和 v 已经连通, 再加这条边就成环, 这条边就是答案.
  • 否则合并它们.
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    UnionFind uf(static_cast<int>(edges.size()) + 1); // 题目节点编号从 1 开始
    for (const auto& edge : edges) {
        if (!uf.unite(edge[0], edge[1])) return edge;
    }
    return {};
}

对 n 条边, 时间 O(n alpha(n)), 空间 O(n), 其中 alpha 为反阿克曼函数, 实践中近似常数. 边界: 若输入不保证 “恰有一条冗余边”, 空返回仅表示没有找到, 调用方不能把它当有效边.

易错点

  • find 不做路径压缩, 最坏会退化.
  • 合并时要合并根, 不是直接 parent[a] = b.
  • 节点编号有时从 1 开始, 要开 n + 1.

4. 前缀和 & 差分

如何理解题目

前缀和和差分是一对逆运算.

  • 前缀和: 适合多次查区间和. 先预处理, 后面 O (1) 查询.
  • 差分: 适合多次做区间修改. 每次 O (1) 标记, 最后统一还原.

关键词: 区间和, 子数组和, 区域和, 区间加, 批量更新.

4.1 一维前缀和

定义: pre[i] 表示前 i 个元素的和, 也就是 nums[0..i-1].

区间 [l, r] 的和: pre[r + 1] - pre[l].

vector<long long> buildPrefix(const vector<int>& nums) {
    int n = nums.size();
    vector<long long> pre(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        pre[i + 1] = pre[i] + nums[i];
    }
    return pre;
}

long long rangeSum(const vector<long long>& pre, int l, int r) {
    return pre[r + 1] - pre[l];
}

为什么开 n + 1? 因为 pre[0] = 0 表示空前缀, 可以统一处理从 0 开始的区间.

4.2 前缀和 + 哈希表: 560 和为 K 的子数组

普通滑动窗口不适用, 因为数组可能有负数. 用前缀和:

如果 pre[j] - pre[i] = k, 说明 (i, j] 这段子数组和为 k. 遍历到当前前缀和 sum 时, 只要知道之前有多少个 sum - k.

int subarraySum(vector<int>& nums, int k) {
    unordered_map<long long, int> cnt;
    cnt[0] = 1;
    long long sum = 0;
    int ans = 0;
    for (int x : nums) {
        sum += x;
        if (cnt.count(sum - k)) ans += cnt[sum - k];
        cnt[sum]++;
    }
    return ans;
}

4.3 二维前缀和

pre[i][j] 表示从左上角到 (i-1, j-1) 的矩形和.

查询 (r1, c1) 到 (r2, c2):

sum = pre[r2+1][c2+1]
    - pre[r1][c2+1]
    - pre[r2+1][c1]
    + pre[r1][c1]

最后加回左上角, 是因为它被减了两次.

vector<vector<long long>> buildPrefix2D(const vector<vector<int>>& matrix) {
    int m = matrix.size(), n = m ? matrix[0].size() : 0;
    vector pre(m + 1, vector<long long>(n + 1, 0));
    for (int r = 0; r < m; ++r)
        for (int c = 0; c < n; ++c)
            pre[r + 1][c + 1] = matrix[r][c] + pre[r][c + 1] + pre[r + 1][c] - pre[r][c];
    return pre;
}
long long sumRegion(const vector<vector<long long>>& pre, int r1, int c1, int r2, int c2) {
    return pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];
}

预处理时间 / 空间 O(mn), 单次合法矩形查询 O(1). 边界: 空矩阵只能构建 1x1 前缀表, 不能查询; 单格查询 (r,c,r,c) 必须返回原值.

4.4 差分数组

如果有很多次 “区间 [l, r] 都加 val”, 逐个元素加会 O (n*m).差分可以每次 O (1):

class Difference {
    vector<long long> diff;
public:
    explicit Difference(const vector<int>& nums) : diff(nums.size()) {
        if (nums.empty()) return;
        diff[0] = nums[0];
        for (size_t i = 1; i < nums.size(); ++i) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    void increment(int l, int r, long long val) {
        if (l < 0 || l > r || r >= static_cast<int>(diff.size())) {
            throw out_of_range("invalid difference range");
        }
        diff[l] += val;
        if (r + 1 < static_cast<int>(diff.size())) diff[r + 1] -= val;
    }

    vector<long long> result() const {
        if (diff.empty()) return {};
        vector<long long> res(diff.size());
        res[0] = diff[0];
        for (size_t i = 1; i < diff.size(); ++i) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
};

典型题

  • 560 和为 K 的子数组: 前缀和 + 哈希表.
  • 724 寻找中心下标: 左和等于右和.
  • 304 二维区域和检索: 二维前缀和.
  • 1109 航班预订统计: 差分数组.
  • 1094 拼车: 差分 + 判断任意位置是否超载.

易错点

  • 前缀和数组建议开 n + 1.
  • 560 必须先 cnt[0] = 1, 代表空前缀.
  • 差分更新右边界时要判断 r + 1 是否越界.
  • 有负数时不要用滑动窗口求和为 K.

5. 设计题

如何理解设计题

设计题不是让你炫复杂代码, 而是考 “数据结构组合”.先问清楚:

  • 每个接口是什么?
  • 每个操作要求什么复杂度?
  • 数据量多大?
  • 是否有淘汰策略或顺序要求?

设计题的套路是: 单一数据结构不够, 就组合两个或多个结构.

5.1 LRU 缓存 (146)

完整实现见 LeetCode Hot 100 算法清单第 6 节 “链表” 中的 LRU 缓存代码. 第 52 篇目前没有 LRU 专属标题; 该真实锚点的目标节包含 LRUCache 完整实现. 这里不重复代码, 只保留选型逻辑:

  • 要 O (1) 查 key: 用哈希表.
  • 要 O (1) 删除最久未使用: 用双向链表维护顺序.
  • get/put 后都要把节点移动到最新位置.

这是 “哈希表 + 双向链表” 的经典组合.

第 52 篇给的是 C++ 版; Android 面试手写通常要求岗位语言, 下面补 Java 手写版, 分 “简单版” 和 “面试手写版”. Kotlin 可等价改写 (data class + LinkedHashMap, 或 HashMap + 双向链表).

简单版: 继承 LinkedHashMap

LinkedHashMap 自带按访问顺序排列与 removeEldestEntry 淘汰钩子, 十几行即可实现:

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    public LRUCache(int capacity) {
        // accessOrder = true: get/put 命中的节点移到队尾, 队尾即最近使用.
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        Integer value = super.get(key);
        // 未命中返回 -1; 命中时 super.get 已更新访问顺序.
        return value == null ? -1 : value;
    }

    public void put(int key, int value) {
        super.put(key, value); // 复用 LinkedHashMap, put 后会自动触发淘汰检查.
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        // 队头是最久未使用; 超容量才淘汰, 由 LinkedHashMap 自动调用.
        return size() > capacity;
    }
}

面试手写版: HashMap + 双向链表

面试常要求不依赖 LinkedHashMap, 手写 “哈希表定位 + 双向链表维护顺序”:

class LRUCache {
    // 节点同时存 key/value: 淘汰尾部时用 key 去删哈希表.
    static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    // 哨兵头尾节点, 避免判空; head 之后是最近使用, tail 之前是最久未使用.
    private final Node head = new Node(0, 0);
    private final Node 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) removeTail(); // 满则淘汰最久未使用
        Node fresh = new Node(key, value);
        map.put(key, fresh);
        addToHead(fresh);
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void removeTail() {
        Node last = tail.prev;
        removeNode(last);
        map.remove(last.key); // 链表和哈希表必须同步删除
    }
}

为什么 get/put 都是 O (1)

  • 哈希表: 查 key 平均 O (1), 负责 “定位”.
  • 双向链表: 已知节点后增删都是 O (1), 直接改前驱 / 后继指针即可. 这正是不能用单链表的原因: 删尾节点要先遍历找前驱, 是 O (n).
  • 两个操作都只是 “一次哈希查找 + 常数次指针改动”, 所以 get/put 均为 O (1).

5.2 LFU 缓存 (460)

如何理解题目

LFU 是 Least Frequently Used: 淘汰访问频次最低的 key; 如果频次相同, 淘汰最久未使用的.

比 LRU 多了一个维度: 访问频次.

选用结构

为了让 get/put 都接近 O (1), 需要:

  • key -> 节点: 快速找到 key.
  • freq -> 双向链表: 同一频次内部按 LRU 排序.
  • minFreq: 当前最小频次, 淘汰时直接定位.

C++ 可用 list + unordered_map 简化.

class LFUCache {
    struct Node { int key, value, freq; };
    int cap, minFreq = 0;
    unordered_map<int, list<Node>::iterator> keyIt;
    unordered_map<int, list<Node>> freqList;

    void touch(list<Node>::iterator it) {
        Node node = *it;
        int f = node.freq;
        freqList[f].erase(it);
        if (freqList[f].empty()) {
            freqList.erase(f);
            if (minFreq == f) minFreq++;
        }
        node.freq++;
        freqList[node.freq].push_front(node);
        keyIt[node.key] = freqList[node.freq].begin();
    }

public:
    LFUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        if (!keyIt.count(key)) return -1;
        int val = keyIt[key]->value;
        touch(keyIt[key]);
        return val;
    }

    void put(int key, int value) {
        if (cap <= 0) return;
        if (keyIt.count(key)) {
            keyIt[key]->value = value;
            touch(keyIt[key]);
            return;
        }
        if (keyIt.size() == cap) {
            auto& lst = freqList[minFreq];
            int oldKey = lst.back().key;
            lst.pop_back();
            keyIt.erase(oldKey);
            if (lst.empty()) freqList.erase(minFreq);
        }
        minFreq = 1;
        freqList[1].push_front({key, value, 1});
        keyIt[key] = freqList[1].begin();
    }
};

易错点

  • 更新已有 key 也算一次访问, 要提升频次.
  • 淘汰后要同步删除 keyIt.
  • 某个频次链表空了, 如果它等于 minFreq, 要更新 minFreq.

5.3 用栈实现队列 (232)

核心思想

队列是先进先出, 栈是后进先出. 用两个栈:

  • in: 负责入队.
  • out: 负责出队.
  • 当 out 空时, 把 in 全部倒进去, 顺序就反过来了.
class MyQueue {
    stack<int> in, out;

    void transfer() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
    }

public:
    void push(int x) { in.push(x); }

    int pop() {
        transfer();
        int x = out.top(); out.pop();
        return x;
    }

    int peek() {
        transfer();
        return out.top();
    }

    bool empty() { return in.empty() && out.empty(); }
};

复杂度: 单次最坏 O (n), 但每个元素最多进出两个栈一次, 所以摊还 O (1).

5.4 设计循环队列 (622)

核心思想

固定数组 + 头尾指针. 为了区分空和满, 最简单是额外维护 size.

class MyCircularQueue {
    vector<int> data;
    int head = 0, tail = 0, sz = 0, cap;
public:
    MyCircularQueue(int k) : data(k), cap(k) {}

    bool enQueue(int value) {
        if (isFull()) return false;
        data[tail] = value;
        tail = (tail + 1) % cap;
        sz++;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % cap;
        sz--;
        return true;
    }

    int Front() { return isEmpty() ? -1 : data[head]; }

    int Rear() {
        if (isEmpty()) return -1;
        return data[(tail - 1 + cap) % cap];
    }

    bool isEmpty() { return sz == 0; }
    bool isFull() { return sz == cap; }
};

5.5 设计 HashMap / Trie

  • HashMap: 数组 + 链表 / 红黑树处理冲突; 核心概念是哈希函数, 冲突, 负载因子, 扩容.
  • Trie: 前缀树, 适合字符串前缀查询. 每个节点保存子节点数组和 isEnd.
class Trie {
    struct Node {
        Node* child[26]{};
        bool isEnd = false;
    };
    Node* root = new Node();
public:
    ~Trie() { destroy(root); }

    void insert(string word) {
        Node* cur = root;
        for (char c : word) {
            int i = c - 'a';
            if (!cur->child[i]) cur->child[i] = new Node();
            cur = cur->child[i];
        }
        cur->isEnd = true;
    }

    bool search(string word) {
        Node* node = find(word);
        return node && node->isEnd;
    }

    bool startsWith(string prefix) {
        return find(prefix) != nullptr;
    }

private:
    void destroy(Node* node) {
        if (!node) return;
        for (Node* child : node->child) destroy(child);
        delete node;
    }

    Node* find(const string& s) {
        Node* cur = root;
        for (char c : s) {
            int i = c - 'a';
            if (!cur->child[i]) return nullptr;
            cur = cur->child[i];
        }
        return cur;
    }
};

易错点

  • 设计题先确认接口, 再写数据结构.
  • LRU/LFU 的关键不是 “能跑”, 而是所有操作是否满足复杂度.
  • 循环队列最容易错的是 Rear() 和取模.
  • Trie 如果字符集不是小写字母, 不能直接用 26 长度数组, 要改成哈希表.

小结: 补充专题优先级

  1. 必吃透: 快排/归并/堆排 + 三者对比; 位运算基础和经典 trick.
  2. 建议掌握: 并查集模板, 前缀和 + 哈希表, 差分数组.
  3. 冲大厂加分: LFU, 循环队列, HashMap/Trie 设计.
  4. 学习方式: 每个专题至少掌握一道母题, 能解释 “为什么选它”, 再去刷变体.

主题练习与预期证据

  1. 用三路快排处理 [2,2,2,1,3], 预期有序输出 [1,2,2,2,3], 并说明等值区间为何不递归.
  2. 为 684 输入 [[1,2],[1,3],[2,3]], 预期返回 [2,3]; 证据是 unite 返回 false 的时刻.
  3. 为矩阵 [[1,2],[3,4]] 查询 (0,1) 到 (1,1), 预期 6; 手算四项容斥证明没有错位.