算法补充专题

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

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

进度自测

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

学算法的通用方法

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

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

面试中可以这样表达：

暴力做法是 xxx，复杂度 O(…)。题目要求/数据规模不允许。这里有 xxx 特征，所以我选 xxx。它的核心是 xxx，实现上维护 xxx，复杂度是 xxx。

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)：递归栈平均深度。
• 不稳定：交换会打乱相等元素的原始顺序。

优化

• 随机 pivot：降低遇到最坏情况的概率。
• 三数取中：从头、中、尾选中位数作 pivot。
• 小数组用插入排序：工程优化。

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];
}

适用场景

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

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)。面试一般说结论即可。

排序对比(高频问)

易错点

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

2. 位运算专题(⭐)

如何理解位运算题

位运算题常见信号：

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

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

基础运算

必背技巧

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 取模后，剩下的就是只出现一次的数在这一位上的值。

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

子集枚举

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

vector<vector<int>> subsets(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> res;
    for (int mask = 0; mask < (1 << n); ++mask) {
        vector<int> cur;
        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) 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 省份数量

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 已经连通，再加这条边就成环，这条边就是答案。
• 否则合并它们。

易错点

• 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<int> buildPrefix(vector<int>& nums) {
    int n = nums.size();
    vector<int> pre(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        pre[i + 1] = pre[i] + nums[i];
    }
    return pre;
}

int rangeSum(vector<int>& 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<int, int> cnt;
    cnt[0] = 1;
    int sum = 0, 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]

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

4.4 差分数组

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

class Difference {
    vector<int> diff;
public:
    Difference(vector<int>& nums) : diff(nums.size()) {
        diff[0] = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    void increment(int l, int r, int val) {
        diff[l] += val;
        if (r + 1 < diff.size()) diff[r + 1] -= val;
    }

    vector<int> result() {
        vector<int> res(diff.size());
        res[0] = diff[0];
        for (int 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)

Hot 100 已讲，这里强调选型逻辑：

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

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

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:
    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:
    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. 学习方式：每个专题至少掌握一道母题，能解释“为什么选它”，再去刷变体。