算法补充专题

Hot 100 没专门成章、但面试(尤其国内)高频会问的几类经典主题。每节含知识点 + 模板代码 + 高频题 + 陷阱。

优先级:排序手写 ⭐ 和位运算 ⭐ 几乎必问,优先吃透;并查集、前缀和/差分、设计题中频,看公司。

进度自测

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

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

面试常让你手写并分析,而不只是调 API。重点掌握快排、归并、堆排,能说清复杂度、稳定性、适用场景。

快速排序

分治:选 pivot → 分区(小的在左、大的在右)→ 递归两边。平均 O(n log n),最坏 O(n²)(已有序且固定选端点),不稳定,原地。

fun quickSort(a: IntArray, lo: Int, hi: Int) {
    if (lo >= hi) return
    val p = partition(a, lo, hi)
    quickSort(a, lo, p - 1)
    quickSort(a, p + 1, hi)
}
fun partition(a: IntArray, lo: Int, hi: Int): Int {
    val pivot = a[hi]                    // 取末尾为基准
    var i = lo
    for (j in lo until hi) {
        if (a[j] < pivot) { a[i] = a[j].also { a[j] = a[i] }; i++ }
    }
    a[i] = a[hi].also { a[hi] = a[i] }   // pivot 归位
    return i
}

优化:随机选 pivot 避免最坏;三数取中;小数组转插入排序。

归并排序

分治:对半拆 → 递归排序 → 合并两个有序数组。稳定,O(n log n) 恒定,需 O(n) 额外空间。链表排序(148)首选。

fun mergeSort(a: IntArray, lo: Int, hi: Int, tmp: IntArray) {
    if (lo >= hi) return
    val mid = lo + (hi - lo) / 2
    mergeSort(a, lo, mid, tmp); mergeSort(a, mid + 1, hi, tmp)
    var i = lo; var j = mid + 1; var k = lo
    while (i <= mid && j <= hi) tmp[k++] = if (a[i] <= a[j]) a[i++] else a[j++]
    while (i <= mid) tmp[k++] = a[i++]
    while (j <= hi) tmp[k++] = a[j++]
    for (x in lo..hi) a[x] = tmp[x]
}

堆排序

建大顶堆 → 反复把堆顶(最大)换到末尾并下沉。原地,不稳定,O(n log n)。理解它就理解了优先队列。

fun heapSort(a: IntArray) {
    val n = a.size
    for (i in n / 2 - 1 downTo 0) sink(a, i, n)      // 建堆 O(n)
    for (end in n - 1 downTo 1) {
        a[0] = a[end].also { a[end] = a[0] }          // 堆顶换到末尾
        sink(a, 0, end)                               // 缩小范围下沉
    }
}
fun sink(a: IntArray, i: Int, n: Int) {
    var root = i
    while (true) {
        var largest = root; val l = 2*root+1; val r = 2*root+2
        if (l < n && a[l] > a[largest]) largest = l
        if (r < n && a[r] > a[largest]) largest = r
        if (largest == root) break
        a[root] = a[largest].also { a[largest] = a[root] }
        root = largest
    }
}

排序对比(高频问)

• 稳定:相等元素相对顺序不变(归并/插入/冒泡稳定;快排/堆排不稳定)。
• 陷阱:快排最坏 O(n²) 的触发条件(已有序+固定 pivot)和随机化优化是必答点;Java 的 Arrays.sort 基本类型用双轴快排、对象用 TimSort(稳定)。

2. 位运算专题(⭐)

核心运算:&(与)、|(或)、^(异或)、~(取反)、<<(左移)、>>(算术右移,补符号位)、>>>(逻辑右移,补 0)。

异或三大性质(高频):a^a=0、a^0=a、满足交换/结合律。用于找单身数、交换变量、加密。

必背技巧:

n and (n - 1)            // 消除最低位的 1
n and (-n)               // 取最低位的 1(lowbit,树状数组用)
(n and (n - 1)) == 0     // 判断是否 2 的幂(n>0)
x shr i and 1            // 取第 i 位
x or (1 shl i)           // 置第 i 位为 1
x and (1 shl i).inv()    // 清第 i 位
x xor (1 shl i)          // 翻转第 i 位

经典题:

• 统计 1 的个数(191):while (n != 0) { n = n and (n-1); count++ },循环次数 = 1 的个数。
• 2 的幂(231)/4 的幂:n > 0 && (n and (n-1)) == 0。
• 只出现一次(136):全员异或。
• 出现 3 次只出 1 次(137):按位统计模 3,或用两个状态变量。
• 只出现一次 II(260,两个数):全异或得 a^b,用 lowbit 分组再各自异或。
• 子集枚举(78):用 0..(1<<n)-1 每个 bit 表示选/不选。
• 状态压缩 DP:用 int 的 bit 表示集合状态(如旅行商、棋盘覆盖)。

// 78 子集:位运算枚举
fun subsets(nums: IntArray): List<List<Int>> {
    val res = mutableListOf<List<Int>>()
    val n = nums.size
    for (mask in 0 until (1 shl n)) {          // 2^n 种状态
        val sub = mutableListOf<Int>()
        for (i in 0 until n) if (mask shr i and 1 == 1) sub.add(nums[i])
        res.add(sub)
    }
    return res
}

• 陷阱:Kotlin 用 and/or/xor/shl/shr/ushr 关键字而非符号;>> 与 >>> 区别(负数右移);判 2 的幂别忘了 n > 0。

3. 并查集(Union-Find)

核心思想:维护不相交集合,支持两个近 O(1) 操作:find(找代表元/根)、union(合并两集合)。专治连通性 / 分组问题。

模板(路径压缩 + 按秩合并):

class UnionFind(n: Int) {
    private val parent = IntArray(n) { it }   // 初始各自为根
    private val rank = IntArray(n)             // 树高(秩)
    var count = n; private set                 // 连通分量数

    fun find(x: Int): Int {
        if (parent[x] != x) parent[x] = find(parent[x])  // 路径压缩
        return parent[x]
    }
    fun union(a: Int, b: Int) {
        val ra = find(a); val rb = find(b)
        if (ra == rb) return
        when {                                  // 按秩合并:矮树挂高树
            rank[ra] < rank[rb] -> parent[ra] = rb
            rank[ra] > rank[rb] -> parent[rb] = ra
            else -> { parent[rb] = ra; rank[ra]++ }
        }
        count--
    }
    fun connected(a: Int, b: Int) = find(a) == find(b)
}

应用:

• 547 省份数量:把相连城市 union,最后数连通分量。

• 684 冗余连接:加边时若两端已连通,该边就是多余的。

• 200 岛屿数量:也可用并查集(陆地格子 union 相邻陆地)。

• 判环 / 等式方程可满足性(990)。

• 复杂度:加上路径压缩 + 按秩合并后,单次操作近乎 O(α(n))(反阿克曼,可视作常数)。

• 陷阱:别忘路径压缩(否则退化成链 O(n));带权并查集是进阶变体。

4. 前缀和 & 差分

互为逆运算的一对技巧。前缀和:O(1) 查区间和(适合“多次查询、不修改“)。差分:O(1) 做区间增减(适合“多次区间修改、最后查询“)。

一维前缀和

pre[i] = nums[0] + ... + nums[i-1],区间 [l, r] 和 = pre[r+1] - pre[l]。

val pre = IntArray(n + 1)
for (i in 0 until n) pre[i + 1] = pre[i] + nums[i]
// 区间 [l, r] 之和:
val sum = pre[r + 1] - pre[l]

• 560 和为 K 的子数组:前缀和 + 哈希表,找 pre[j] - pre[i] = k,即统计 pre[j] - k 出现次数。
• 724 寻找中心下标、304 二维区域和。

二维前缀和

pre[i][j] = 左上角到 (i-1,j-1) 的矩形和。容斥:

区域和 = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]

差分数组

diff[i] = nums[i] - nums[i-1]。对区间 [l, r] 同时加 val,只需 diff[l] += val; diff[r+1] -= val,最后对 diff 求前缀和还原。

// 给区间 [l, r] 都加 val(多次操作)
diff[l] += value
if (r + 1 < n) diff[r + 1] -= value
// 最后还原:对 diff 求前缀和
for (i in 1 until n) diff[i] += diff[i - 1]

• 1109 航班预订统计、1094 拼车:典型差分。
• 陷阱:前缀和数组开 n+1 长度用 0 哨兵简化边界;差分注意 r+1 越界判断;560 题有负数不能用滑窗,只能前缀和。

5. 设计题

考数据结构组合 + 工程抽象能力,和你做 SDK 的强项契合。核心套路:用合适的数据结构组合,让每个操作达到要求的复杂度。

LRU 缓存(146,Hot 100 已有,这里强调)

哈希表 + 双向链表:哈希表 O(1) 定位节点,双向链表维护访问顺序(头=最近,尾=最久)。get/put 均 O(1)。和你工作中的 LruCache 直接相关,务必手写到熟。

LFU 缓存(460,难)

按使用频次淘汰,频次相同淘汰最久未用。结构:key→节点 哈希 + freq→双向链表 哈希 + 维护 minFreq。比 LRU 复杂一档,大厂常考。

用栈实现队列(232)/ 用队列实现栈(225)

• 栈→队列:两个栈(in 栈、out 栈),out 空时把 in 全部倒过来。摊还 O(1)。
• 队列→栈:入队后把前面元素轮转到后面。

设计循环队列(622)

固定数组 + 头尾指针 + 取模。判空 head == tail,判满留一个空位或用 size 计数。

设计 HashMap(706)/ 设计 Trie(208)

• HashMap:数组 + 链表(拉链法)处理冲突,理解负载因子和扩容。
• Trie:见 Hot 100 图论节,26 叉树 + isEnd。

// 232 两个栈实现队列
class MyQueue {
    private val inStack = ArrayDeque<Int>()
    private val outStack = ArrayDeque<Int>()
    fun push(x: Int) = inStack.addLast(x)
    fun pop(): Int { transfer(); return outStack.removeLast() }
    fun peek(): Int { transfer(); return outStack.last() }
    fun empty() = inStack.isEmpty() && outStack.isEmpty()
    private fun transfer() {
        if (outStack.isEmpty())
            while (inStack.isNotEmpty()) outStack.addLast(inStack.removeLast())
    }
}

• 陷阱:设计题先和面试官确认接口和复杂度要求(像做 API 设计),再选数据结构;LFU 维护 minFreq 是难点;循环队列的判空判满边界。

小结:补充专题优先级

1. 必吃透(几乎必问):手写快排/归并/堆排 + 三者对比、位运算技巧。
2. 建议掌握:并查集模板 + 547、前缀和/差分(尤其前缀和配哈希)。
3. 加分:设计题(LFU、栈队互换)——展示工程抽象,和你 SDK 背景契合。