计算机基础
算法与手写训练 从问题约束、不变量与复杂度出发，覆盖线性结构、树图与动态规划；附 C++17 边界验证程序。
12 个专题 39 道深入问答 4 个完整实验
先独立推演，再展开答案。自评不会自动判断代码正确；完整实验的验证环境在各节注明。
ALG-01 / 基础推理与线性结构 ○ 标为掌握
复杂度与不变量：先证明，再估算 复杂度描述输入规模增长时的资源需求；不变量把代码的每次状态变化与最终正确性连接起来。
先定义输入规模和成本模型。数组长度是 n，图通常用 V 和 E 两个量，字符串比较还与字符串长度有关。O 表示渐近上界，Θ 表示同阶的上下界；写 O(n) 不等于精确执行 n 次，也不等于任何机器上都更快。空间复杂度应说明是否包含输入、输出及递归调用栈。
正确性可拆成三个部分：循环开始前不变量成立；每轮更新仍保持不变量；退出条件与不变量一起推出后置条件。还要给出严格下降且有下界的终止量，例如二分搜索的区间长度。反转链表时，可以用“prev 是已处理前缀的逆序，cur 是尚未处理后缀的首节点，两部分不丢失节点”指导指针赋值次序。
复杂度要按总工作量计数。两层循环不必然是 O(n²)：若左右指针在整个算法中只向右移动，各最多 n 次，则总计 O(n)。反之，在每次外层循环中把内层指针重置到 0，通常失去这一界。递归要统计状态数量、每个状态转移成本与重复计算；不能只看递归深度。
区分最坏情况、平均情况和摊还分析。动态数组按几何倍数扩容时，连续 n 次尾插总搬迁量为 O(n)，因此尾插的摊还成本是 O(1)，但一次扩容仍可能是 O(n)。哈希查找的平均 O(1) 则依赖哈希分布等条件，不是同一种保证。实时延迟、对抗输入或内存受限时，必须重新评估这些条件。
适用边界：算法证明基于抽象整数与有效对象，C++ 实现还必须满足整数范围、对象生命周期和容器前置条件。先用小规模穷举或朴素算法作对照，再检查空输入、单元素、重复值、极值和退化结构；测试能暴露错误，但有限测试不能替代普遍性证明。
深入面试与自测 Q1 · O(n) 的实现为什么可能比 O(n log n) 慢？应如何解释和验证？ 渐近复杂度忽略常数、缓存访问、分配、分支预测和输入规模。节点式哈希表可能进行多次随机访存，而连续数组排序能充分利用局部性；小规模输入下后者可能更快。先保证两者解决同一问题且输出语义一致，再在代表性规模、分布和编译配置下测量时间与内存；同时保留最坏情况分析。一次基准结果不能推出对所有规模都更快。
回答应覆盖 区分渐近趋势与实际延迟 考虑数据局部性和输入分布 基准与理论各有边界 ☆ 收藏 自评 需重学 不完整 能解释
Q2 · 平均 O(1) 和摊还 O(1) 有什么本质区别？ 平均分析对某个输入或随机选择的分布取期望，必须说明随机性来自哪里。摊还分析把一个合法操作序列的总成本分摊到各次操作，不需要输入服从概率分布。动态数组几何扩容的尾插属于后者：某次成本很高，但前后许多廉价操作共同承担扩容。哈希表的预期常数查找不能直接当作确定性最坏界；两种分析也可以在同一数据结构中同时出现。
☆ 收藏 自评 需重学 不完整 能解释
Q3 · 面试时如何说明一个循环正确，而不只是逐行复述代码？ 给出能连接输入与目标的状态断言，并说明初始化、保持和终止。例如求前缀最大值：处理到 i 前，best 等于区间 [0,i) 的最大值；加入 a[i] 后取 max 即保持断言。空输入必须另有契约，不能用不存在的 a[0] 初始化。退出时 i=n，断言覆盖整个数组；i 每轮增加且受 n 限制，保证终止。最后再说明实现的比较操作和下标合法。
☆ 收藏 自评 需重学 不完整 能解释
动手验证 对一段含嵌套 while 的双指针算法，分别写出输入规模、循环不变量、终止量、指针总移动次数和额外空间。再构造一个会因内层指针重置而退化为 O(n²) 的版本，说明区别。
ALG-02 / 基础推理与线性结构 ○ 标为掌握
二分边界：查找第一个满足条件的位置 二分的本质是单调谓词上的边界搜索。区间约定、重复值语义和答案不存在时的返回值必须一致。
对非递减数组，lower_bound(x) 是首个不小于 x 的位置，upper_bound(x) 是首个大于 x 的位置，返回 n 表示不存在。重复值区间为 [lower_bound(x), upper_bound(x))。不要用 lower_bound(x+1) 替代 upper_bound(x)：当 x 已是整数最大值时，x+1 可能溢出，且这一替代不适用于一般比较类型。
一种可证明的手写方式使用半开区间 [l,r)，初值 l=0、r=n。不变量是 [0,l) 均小于目标、[r,n) 均不小于目标；中间部分尚未确定。取 mid=l+(r-l)/2，若 a[mid]<x，则 l=mid+1，否则 r=mid。每次都缩短区间；退出时 l=r，正是目标边界。返回值可为 n，因此使用 a[pos] 前必须检查 pos<n。
标准库的 lower_bound 要求范围针对当前比较谓词已经分区，整体排序是常见的充分条件。C++17 的复杂度保证是对数级比较次数；对非随机访问迭代器，移动迭代器仍可能线性。对 std::map 这样的有序关联容器，应优先使用其成员 lower_bound，利用容器自身提供的对数复杂度查找。
答案二分先定义可行谓词 P(x)，再证明它只从 false 变 true，或只从 true 变 false。比如容量增加不会让原本可行的分组方案变得不可行。总复杂度是谓词调用成本乘以二分次数，不能只写 O(log M)。搜索上下界必须覆盖答案，并说明不存在解时如何返回。
适用边界：比较必须与数据分区方式一致；浮点数中的 NaN 会破坏常见大小比较的预期关系。连续域二分应使用固定迭代次数或清晰的误差契约，避免认为浮点中点总能严格缩小可表示区间。本节实验只处理非递减 int 数组，索引使用 size_t，计算中点不做 l+r。
深入面试与自测 Q1 · 为什么 lower_bound 遇到相等值仍要缩右边界？ 目标是第一个不小于 x 的位置，mid 相等只说明答案不在 mid 右侧，无法排除左侧还有相等值。把 r 设为 mid 保留 mid 作为最终边界候选，同时继续寻找更早位置。把 l 设为 mid+1 会跳过潜在答案；直接返回则仅得到某个相等位置。循环结束时由左边全小于、右边全不小于两个不变量共同确定唯一边界。
☆ 收藏 自评 需重学 不完整 能解释
Q2 · 数组没有完全排序，能否使用 lower_bound？ 对某一次固定查询，满足“所有满足 comp(element,value) 的元素都在前，其余在后”的分区条件即可，不必在各分区内部排序。例如对 x=5，序列 [3,1,4,8,6] 已按小于 5 分区。但它未必满足另一目标值的分区条件，因此不能支持任意查询。工程中通常维护完整排序，以同时满足所有查询；未满足前置条件时，标准算法的结果没有可依赖的保证。
☆ 收藏 自评 需重学 不完整 能解释
Q3 · 答案二分中，怎样避免得到看似合理但错误的结果？ 先把候选答案空间和可行性定义写出来，再独立证明单调性，不能仅凭几个样例推测。明确上下界中是否包含一个可行点，并分别处理无解与所有点可行。判定函数内部的求和、乘法也可能溢出，可在安全范围内提前比较或使用检查运算。最终测试应在小范围穷举所有答案，与二分结果对照，并验证结果可行且其前一候选不可行。
回答应覆盖 先证明谓词单调 验证最终边界而非只看数值 判定函数同样审查溢出 ☆ 收藏 自评 需重学 不完整 能解释
完整实验 已验证 · MSVC 19.37 / x64 · c++17
程序要求传入非递减数组，返回下标 n 表示不存在。断言将手写边界与标准库对照，并直接检查边界两侧性质；覆盖长度 0–6、值域 [-2,2] 的所有非递减序列及整数极值。编译时不要定义 NDEBUG，否则 assert 会被关闭。这里给出预期输出，是否实际通过编译运行以执行验证为准。
查看完整源代码 #include <algorithm>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <limits>
#include <vector>
std::size_t lower_index(const std::vector<int>& a, int target) {
std::size_t left = 0, right = a.size();
while (left < right) {
const std::size_t mid = left + (right - left) / 2;
if (a[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
std::size_t upper_index(const std::vector<int>& a, int target) {
std::size_t left = 0, right = a.size();
while (left < right) {
const std::size_t mid = left + (right - left) / 2;
if (a[mid] <= target) left = mid + 1;
else right = mid;
}
return left;
}
void check(const std::vector<int>& a) {
assert(std::is_sorted(a.begin(), a.end()));
const int targets[] = {
std::numeric_limits<int>::min(), -3, -2, -1, 0, 1, 2, 3,
std::numeric_limits<int>::max()
};
for (int x : targets) {
const auto lo = lower_index(a, x);
const auto hi = upper_index(a, x);
const auto expected_lo = static_cast<std::size_t>(
std::lower_bound(a.begin(), a.end(), x) - a.begin());
const auto expected_hi = static_cast<std::size_t>(
std::upper_bound(a.begin(), a.end(), x) - a.begin());
assert(lo == expected_lo && hi == expected_hi);
assert(lo <= hi && hi <= a.size());
assert(lo == 0 || a[lo - 1] < x);
assert(lo == a.size() || a[lo] >= x);
assert(hi == 0 || a[hi - 1] <= x);
assert(hi == a.size() || a[hi] > x);
}
}
// Enumerate every nondecreasing sequence of length <= remaining
// over the alphabet [minimum, 2].
void enumerate(std::vector<int>& a, std::size_t remaining, int minimum) {
check(a);
if (remaining == 0) return;
for (int value = minimum; value <= 2; ++value) {
a.push_back(value);
enumerate(a, remaining - 1, value);
a.pop_back();
}
}
int main() {
std::vector<int> a;
enumerate(a, 6, -2);
const std::vector<int> extremes = {
std::numeric_limits<int>::min(),
std::numeric_limits<int>::min(), 0,
std::numeric_limits<int>::max()
};
check(extremes);
const std::vector<int> same = {7, 7, 7};
assert(lower_index(same, 7) == 0);
assert(upper_index(same, 7) == same.size());
assert(lower_index(same, 8) == same.size());
std::cout << "binary boundaries: all assertions passed\n";
}
预期行为 binary boundaries: all assertions passed
下载源代码 这里的通过记录只证明指定编译器和测试输入上的结果，不证明所有平台或全部输入都正确。
动手验证 实现 lower_bound 与 upper_bound，验证空数组、全相等、目标比所有值小或大、INT_MIN/INT_MAX。再对一个“容量至少多大才可行”的问题写出谓词单调性的证明及每次判定的成本。
ALG-03 / 基础推理与线性结构 ○ 标为掌握
双指针与滑动窗口：依靠单调性删除候选 指针只移动一次是复杂度结论，能否安全移动才是正确性核心。不同窗口条件需要分别证明。
相向双指针常用于有序数组的两数之和。若 a[l]+a[r] 小于目标，固定 l 时任何更小的右值都无解，因此可以丢弃 l；大于目标时同理丢弃 r。负数并不破坏这个证明，排序才是关键。若原题要求原始下标，排序时须保留索引；两数相加的类型和范围也要单独检查。
同向滑动窗口维护连续区间及其统计量。以“最多 K 种不同字节的最长子串”为例，向右加入新字节，若种类数超过 K，则移动左端直到恢复合法；此时当前窗口是以该右端结束的最长合法候选。左右端总共移动 O(n) 次，固定字节表支持常数时间统计，额外空间与字节字符集大小有关。
不是所有连续子数组问题都适合普通滑窗。求和至少为 S 的最短区间时，非负元素使扩大窗口不减小和、缩小窗口不增大和；允许负数后此条件失效。例如数组 [-1,2]、S=2，持续扩大后的总和只有 1，简单算法可能错过单元素 [2]。此类问题可转为前缀和与单调队列等方案，需要另行证明。
计数问题常把“恰好 K 种”转为“至多 K 种的子数组数减去至多 K-1 种的子数组数”。在每个右端合法化后，可贡献 right-left+1 个合法非空子数组；这要求合法性对删除左端元素封闭。K=0 时应明确非空子数组计数为 0，并避免对无符号 K 直接做 K-1。
适用边界：实验以 std::string 的字节为元素，使用 unsigned char 转换，并以 std::map 计数而不假设 char 的位宽；其时间为 O(n log(σ+1))，σ 为出现的不同字节数，空间 O(σ)。若明确使用 8 位字节，可换成 256 项数组实现线性时间。它不是 Unicode 字符或用户可见字形计数器；UTF-8 中文需先解码为码点，按用户可见字符计数还涉及字形分段。
深入面试与自测 Q1 · while 收缩窗口嵌在 for 里，为什么仍可能是 O(n)？ 对整个执行过程计数，右端只前进 n 次，左端也只能从 0 增长到 n。每个元素最多加入一次、移出一次，若单次更新是 O(1)，总时间就是 O(n)，并非每个右端都重新扫描 n 个元素。如果窗口更新还执行遍历、字符串复制或非恒定代价的查找，就必须把这些成本乘进去；把 left 每轮重置也会破坏线性界。
回答应覆盖 用总移动次数分析 说明更新成本条件 指出重置与复制的影响 ☆ 收藏 自评 需重学 不完整 能解释
Q2 · 允许负数后，为什么某些双指针仍正确，某些滑窗却失效？ 二者依赖的单调性不同。有序两数之和依赖排序后元素的相对大小，负数仍遵守这一顺序；非负数组的和窗口依赖移入不减、移出不增，负数会直接破坏它。判断方法不是看题目有没有负数，而是写出“为什么被删除的候选不可能成为答案”的论证。若做不到，就应考虑前缀和、哈希、平衡树或单调队列等其他结构。
回答应覆盖 区分两种单调性 给出删除候选的理由 知道替代结构须重新建模 ☆ 收藏 自评 需重学 不完整 能解释
Q3 · 怎样从最长合法窗口推导出合法子数组的总数？ 当合法性对缩小左端区间封闭时，若当前最左合法端点是 l，所有以 r 结尾、起点在 [l,r] 的非空子数组都合法，数量为 r-l+1。逐右端相加不会重复，因为每个子数组有唯一右端。这个推导不适用于任意条件，比如“和恰好为 S”通常不对缩小区间封闭。总数最多 n(n+1)/2，累加类型和乘法计算需按输入上限选择并检查。
☆ 收藏 自评 需重学 不完整 能解释
完整实验 已验证 · MSVC 19.37 / x64 · c++17
以字节而非 Unicode 字符为单位，支持字符串内嵌零字节，K=0 返回 0。滑窗与朴素区间枚举对照，覆盖长度 0–6、字母表 {a,b,零字节} 的所有字符串及 char 的极值。std::map 不依赖散列表遍历顺序或 8 位 char 假设；它的更新成本是对数级。断言需在未定义 NDEBUG 时运行，预期输出不代表已执行。
查看完整源代码 #include <algorithm>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <limits>
#include <map>
#include <set>
#include <string>
std::size_t longest_at_most_k_bytes(const std::string& text, std::size_t k) {
if (k == 0) return 0;
std::map<unsigned char, std::size_t> counts;
std::size_t left = 0, best = 0;
for (std::size_t right = 0; right < text.size(); ++right) {
++counts[static_cast<unsigned char>(text[right])];
while (counts.size() > k) {
const auto key = static_cast<unsigned char>(text[left]);
auto it = counts.find(key);
assert(it != counts.end() && it->second > 0);
--it->second;
if (it->second == 0) counts.erase(it);
++left;
}
best = std::max(best, (right + 1) - left);
}
return best;
}
std::size_t brute(const std::string& text, std::size_t k) {
std::size_t best = 0;
for (std::size_t left = 0; left < text.size(); ++left) {
std::set<unsigned char> seen;
for (std::size_t right = left; right < text.size(); ++right) {
seen.insert(static_cast<unsigned char>(text[right]));
if (seen.size() <= k)
best = std::max(best, (right + 1) - left);
}
}
return best;
}
void check(const std::string& text) {
for (std::size_t k = 0; k <= 4; ++k)
assert(longest_at_most_k_bytes(text, k) == brute(text, k));
}
void enumerate(std::string& text, std::size_t remaining) {
check(text);
if (remaining == 0) return;
const char alphabet[] = {'a', 'b', '\0'};
for (char ch : alphabet) {
text.push_back(ch);
enumerate(text, remaining - 1);
text.pop_back();
}
}
int main() {
assert(longest_at_most_k_bytes("", 2) == 0);
assert(longest_at_most_k_bytes("eceba", 2) == 3);
assert(longest_at_most_k_bytes("aa", 1) == 2);
assert(longest_at_most_k_bytes("abc", 0) == 0);
const std::string with_zero = {'a', '\0', 'b', '\0', 'b'};
assert(longest_at_most_k_bytes(with_zero, 2) == 4);
const std::string char_limits = {
std::numeric_limits<char>::min(),
std::numeric_limits<char>::max(),
std::numeric_limits<char>::min()
};
check(char_limits);
std::string text;
enumerate(text, 6);
std::cout << "sliding window: all assertions passed\n";
}
预期行为 sliding window: all assertions passed
下载源代码 这里的通过记录只证明指定编译器和测试输入上的结果，不证明所有平台或全部输入都正确。
动手验证 先手写“最多 K 种不同字节的最长子串”，用朴素枚举作对照；再给出一个负数破坏最短和窗口的反例。扩展到“恰好 K 种的子数组个数”时，解释每个右端的计数公式和 K=0。
ALG-04 / 基础推理与线性结构 ○ 标为掌握
链表：指针关系、所有权与结构不变量 链表算法首先维护节点可达关系。操作前保留后继、明确节点身份与所有权，才能避免断链和悬空访问。
单链表反转维护 prev 与 cur：先保存 next=cur->next，再令 cur->next=prev，最后同时推进 prev 与 cur。循环中已处理前缀与未处理后缀互不丢失。时间 O(n)、额外指针空间 O(1)；递归版通常还有 O(n) 调用栈。空链表返回空指针，单节点保持不变。
链表的 O(1) 插入或删除有定位前提。已知前驱节点时可常数时间修改连接；如果仅知道下标或值，查找前驱可能是 O(n)。所谓“把后继值复制到当前节点再删除后继”的技巧不适用于尾节点，也可能破坏节点身份、外部引用和对象语义，不能作为一般删除接口。
快慢指针用于判环与找环入口。每轮慢走一步、快走两步，访问 fast->next->next 前必须确认 fast 和 fast->next 均非空。有环时，两者在环上的相对距离每轮前进一格，必然相遇。相遇后把一个指针移到头部，两个都每次一步，首次相遇处是环入口；该结论建立在标准的一步与两步速度上。
链表相交通常指两个头指针最终可达同一个节点对象，不是节点值相等。对无环单链表可对齐长度，或让两个指针分别走完 A 再走 B、走完 B 再走 A，最终相遇于首个公共节点或同时为空。若允许环，必须先分类讨论无环、有环及环入口关系，不能直接套无环算法。
适用边界：手写题常把 Node* 视为不拥有对象的链接，算法只重连而不释放节点；实际程序必须定义谁分配、谁销毁、外部指针是否继续有效。若使用 unique_ptr 表达所有权，重连需要移动所有权；若为 shared_ptr 链接，环会导致引用计数无法归零。并发修改链表还涉及同步和内存回收，单线程证明不能直接推广。
struct Node {
int value;
Node* next = nullptr; // 非拥有链接；调用者管理节点生命周期
};
Node* reverse_list(Node* head) {
Node* prev = nullptr;
Node* cur = head;
while (cur != nullptr) {
Node* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
// 前置条件：有限、无环的单链表；节点在整个调用期间有效。深入面试与自测 Q1 · Floyd 判环相遇后，为什么一个指针回到头部就能找到入口？ 设头到入口距离为 μ，环长为 λ，慢指针在相遇前走了 t 步，快指针走了 2t 步。相遇意味着 t 是 λ 的整数倍；慢指针相对于入口的位置为 (t-μ) mod λ，即 -μ mod λ。因此环内指针再走 μ 步会到入口，头部指针也恰好走 μ 步到入口。若 μ=0，相遇位置已是入口。证明依赖节点身份与有效链接，不依赖节点值。
☆ 收藏 自评 需重学 不完整 能解释
Q2 · 链表删除真的比数组快吗？ 若已持有有效前驱且只需重连，单链表删除链接是 O(1)；但定位前驱通常 O(n)，释放节点也有分配器成本。数组删除中间元素需搬移后续元素，但连续布局具有较好的缓存局部性，批量操作可能更快。还要考虑迭代器稳定性、随机访问和额外指针内存。选择结构应基于完整操作序列，不能只比较一次重连和一次搬移。
☆ 收藏 自评 需重学 不完整 能解释
Q3 · 反转链表后，原来保存的节点指针会怎样？ 只重连 next、没有销毁或移动节点对象时，指向各节点的指针仍指向原对象，但从该节点继续遍历的顺序已经改变，原 head 变成尾节点。如果调用者保存的是某条连接关系或“后继”假设，这些逻辑条件不再成立。若算法同时释放节点，相关指针会悬空；若使用拥有型智能指针，必须按所有权模型移动和更新，不能把裸指针版本直接照搬。
回答应覆盖 区分对象有效性与拓扑变化 说明外部观察者契约 关联所有权与释放 ☆ 收藏 自评 需重学 不完整 能解释
动手验证 使用栈上 Node 构造空链、单节点和三个节点的链表，验证反转后的节点地址顺序及尾节点 next=nullptr，再反转一次验证恢复。另画出带环链表，推导入口定位，而不是只背循环。
ALG-05 / 基础推理与线性结构 ○ 标为掌握
栈与单调栈：保留尚未解决的候选 普通栈维护嵌套关系，单调栈再利用数值顺序淘汰候选。相等值处理决定严格性和计数是否重复。
栈按后进先出组织未完成任务，适合括号匹配、表达式处理和模拟递归。C++ 的 std::stack::pop() 不返回弹出值，需先读取 top() 再 pop()，且两者都要求非空。用 vector 模拟栈可直接保存下标，但引用末尾元素后执行 push_back，需注意扩容可能使引用失效。
求每个位置右侧第一个严格更大的元素：从左向右遍历，把尚未找到答案的下标保存在栈中，使其对应值从底到顶非递增。新值 a[i] 大于栈顶值时，i 就是该下标的答案：此前经过的元素都没有成功弹出它，所以 i 是第一个。继续弹出所有被解决的下标，再压入 i。
每个下标只入栈一次、出栈至多一次，因此总时间 O(n)，辅助空间 O(n)。存下标而非单存数值，可以计算距离、处理重复值并回写原位置。严格更大用 a[top]<a[i] 弹出；若要求大于等于，则需要改成 <=，并重新确认相等值保留规则。
计算每个元素作为区间最小值的贡献时，左右边界通常必须采用一边严格、一边非严格的比较，使含重复最小值的区间只归属于一个位置。两边都严格或都非严格可能导致重复或遗漏。直方图最大矩形还需要处理扫描结束时尚在栈中的柱子，可使用显式收尾，避免构造违反高度范围的哨兵。
适用边界：单调栈回答由顺序扫描决定的最近边界问题，不是通用动态区间最值结构。固定长度滑窗最大值通常使用双端队列：队首负责剔除过期下标，队尾负责剔除被新值支配的候选。若支持任意修改和任意区间查询，则应考虑线段树等结构。
#include <cstddef>
#include <vector>
// 返回右侧首个严格更大元素的下标；n 表示不存在。
std::vector<std::size_t> next_greater(const std::vector<int>& a) {
const std::size_t n = a.size();
std::vector<std::size_t> answer(n, n), pending;
for (std::size_t i = 0; i < n; ++i) {
while (!pending.empty() && a[pending.back()] < a[i]) {
answer[pending.back()] = i;
pending.pop_back();
}
pending.push_back(i);
}
return answer;
}深入面试与自测 Q1 · 单调栈删除旧元素时，为什么不会丢失后续答案？ 需要区分两种删除理由。在“下一个更大元素”中，旧下标被弹出是因为它的最终答案已经由当前下标确定，后面任何元素都更远，不会改进答案。在窗口最大值的队尾淘汰中，旧值不大于新值且更早过期，新元素在未来窗口内同时拥有更大值和更晚失效时间，所以旧值被支配。不能只说“为了保持单调”，必须给出已解决或被支配的证明。
回答应覆盖 解释淘汰的语义 区分已解决与被支配 不把单调性本身当证明 ☆ 收藏 自评 需重学 不完整 能解释
Q2 · 重复值为什么常导致单调栈计数错误？ 以 [2,2] 的子数组最小值贡献为例，长度为 2 的区间同时含两个最小位置。如果左右都允许跨过相等值，两者都可能认领该区间，产生重复；如果双方都在相等处截断，又可能无人认领。固定一种归属规则，例如由最左或最右最小值负责，并在左右边界分别使用严格与非严格比较，才能恰好计数一次。比较符号应从归属规则推导，而非背模板。
☆ 收藏 自评 需重学 不完整 能解释
Q3 · 单调队列能支持任意删除和任意区间查询吗？ 常见滑窗单调队列利用删除发生在最旧端、加入发生在最新端这一顺序，失效下标可从队首连续剔除。若任意删除中间元素或查询历史任意区间，被淘汰的候选可能重新有用，队列已丢失这些信息。静态区间查询可考虑稀疏表，带修改的区间查询可考虑线段树；是否支持更新、查询类型和内存限制共同决定结构。
回答应覆盖 说明滑窗操作顺序 识别信息已丢失 按查询与更新需求选结构 ☆ 收藏 自评 需重学 不完整 能解释
动手验证 对 [2,2,3,1] 写出每一步栈中的下标和答案；将目标改成“右侧第一个大于等于”并给出预期结果。再解释为什么固定窗口最大值需要队首过期检查，普通栈无法直接完成。
ALG-06 / 基础推理与线性结构 ○ 标为掌握
哈希：用空间换定位，不把散列当作相等 哈希表依靠散列定位候选，再用相等关系确认键。复杂度、迭代器失效和状态表示都需要明确。
哈希把较大的键空间映射到有限桶或位置，碰撞无法普遍避免。unordered_map 仍需通过键相等谓词区分同桶元素；相等的键必须有相同哈希值，哈希相同却不要求键相等。自定义键的 Hash 与 KeyEqual 必须一致且稳定，不要只改大小写不敏感比较而保留区分大小写的散列。
std::unordered_map 的常见查找、插入平均为常数级，最坏可线性；字符串键的哈希或相等比较成本还与长度有关。装载因子影响平均桶密度，reserve 可以减少预期扩容次数，但不能消除哈希碰撞，也不能把平均界变成最坏界。需要有序遍历、范围查询或确定性对数界时，std::map 等结构可能更适合。
前缀和加哈希可统计和为 K 的子数组：设当前前缀为 p，此前有多少前缀等于 p-K，就有多少区间在当前右端结束。先计入历史前缀频次，再记录当前前缀；初始前缀 0 的频次为 1，用来覆盖从下标 0 开始的区间。负数不破坏这个等式，因此它适合普通求和滑窗失效的场景。
查找频次时，operator[] 对不存在的键会插入默认值；若只想观察，使用 find 可避免意外修改。unordered 容器重哈希会使迭代器失效，但不会使仍存在元素的指针和引用失效；erase 则使被删除元素相关引用失效。遍历中插入新键必须审查是否触发重哈希，不应依赖当前机器上桶数刚好足够。
适用边界：哈希键必须表达完整状态。仅存一个可能碰撞的指纹来判定两个字符串或状态相同，会把概率性证据当作精确相等；需保存原对象确认，或明确允许误判的概率模型。对不受信任的输入、内存极限及稳定输出顺序的需求，应分别考虑碰撞退化、容量上限与额外排序。
深入面试与自测 Q1 · 为什么 reserve 后仍不能承诺 unordered_map 查找最坏 O(1)？ reserve 主要为预期元素数量准备桶数，减少后续因装载因子触发的重哈希；它不保证键均匀落入桶。如果大量键发生碰撞，查找仍可能检查线性数量的元素。成本还包括计算哈希和键比较。需要抵抗可构造退化输入时，应结合威胁模型选择合适哈希方案、限制资源，或使用具有对数最坏界的有序结构，而不是只调大容量。
☆ 收藏 自评 需重学 不完整 能解释
Q2 · 为什么前缀和计数必须先查询，再把当前前缀加入哈希表？ 当前前缀对应右端之后的位置，合法非空子数组要与更早的前缀配对。若先加入当前前缀，在 K=0 时会把当前前缀与自己配对，错误计入长度为 0 的区间。初始记录前缀 0 一次表示数组开始之前的位置，并非额外空子数组。频次而非布尔标记是必要的，因为不同位置可能有相同前缀，每个位置都对应不同起点。
☆ 收藏 自评 需重学 不完整 能解释
Q3 · 怎样在 C++ 中安全保存哈希表查询结果，并在之后插入元素？ find 返回的迭代器不能无条件跨越可能重哈希的插入继续使用。若确实需要后续访问，可在插入完成后重新 find；或在确保该元素不会被 erase 的前提下保存指向元素的指针或引用，因为重哈希本身不会使它们失效。引用到 mapped value 与键对象的生命周期仍属于容器。提前 reserve 可减少失效机会，但代码正确性应依赖明确容量与操作条件，而非经验。
回答应覆盖 区分迭代器与引用 明确 erase 的例外 重查是简单稳健方案 ☆ 收藏 自评 需重学 不完整 能解释
动手验证 手写和为 K 的子数组计数，测试 [0,0,0]、含负数、无解和空数组，解释为何答案可能是 O(n²) 而运行时间平均 O(n)。为一个大小写不敏感字符串键同时设计相等函数与散列函数。
ALG-07 / 树、图与数据结构选择 ○ 标为掌握
树遍历：访问时机、返回信息与高度 前序、中序、后序区别在访问节点的时机。递归返回值应精确描述子树信息，避免重复扫描。
前序先处理根，再处理左右子树；中序按左、根、右；后序先完成孩子，再汇总根。二叉搜索树在其键序和重复值策略满足约定时，中序得到相应有序序列；普通二叉树没有这一保证。后序适合计算高度、子树大小、平衡性和树形动态规划，因为父节点依赖子节点结果。
一次完整遍历访问 n 个节点，时间 O(n)。递归额外空间是 O(h)，h 为树高；平衡树通常 O(log n)，退化成链时可达 O(n)。层序遍历的队列大小与最大层宽相关，最坏也可 O(n)。把递归改成显式栈可避免语言运行时调用栈溢出，但不会自动把辅助空间降为 O(1)。
自底向上返回多个必要信息，往往能避免重复计算。判断平衡二叉树时，若每个节点都重新求两棵子树高度，链形输入可退化到 O(n²)；一次后序返回“是否平衡与高度”，每个节点只合并一次，得到 O(n)。返回高度的定义要统一：空树高度可定为 0，叶子为 1。
从前序和中序重建二叉树，常以值到中序位置的映射定位根；这依赖键唯一或额外节点身份标识。存在重复值时，仅靠数值遍历序列未必唯一确定结构。序列化若要保留任意树结构，应记录空孩子标记或等价结构信息，不能只保存前序值序列。
适用边界：算法默认输入是有限、无环且父子关系符合树定义的结构。一般图或共享子树 DAG 可能被重复访问，环会造成不终止，需增加 visited 或改变建模。Morris 遍历虽可减少辅助栈，但临时修改链接，必须可靠恢复，不适合未经协调的并发读者。
#include <algorithm>
#include <cstddef>
struct TreeNode {
int value;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
};
struct TreeInfo { bool balanced; std::size_t height; };
TreeInfo inspect_tree(const TreeNode* node) {
if (node == nullptr) return {true, 0};
const auto l = inspect_tree(node->left);
const auto r = inspect_tree(node->right);
const auto gap = l.height > r.height ? l.height - r.height
: r.height - l.height;
return {l.balanced && r.balanced && gap <= 1,
1 + std::max(l.height, r.height)};
}
// 有限有效二叉树；递归深度受树高影响。深入面试与自测 Q1 · 为什么后序遍历特别适合树形动态规划？ 父节点状态往往由孩子的已完成状态组合得到，后序天然提供这种依赖顺序。例如二叉树最大路径和需要孩子返回“从该孩子向下延伸的一条路径”的最优值，父节点再用左右两条路径更新全局答案。返回给父亲的值不能同时选左右两支，否则再向上连接会产生分叉，不再是一条路径。关键是精确定义返回状态，而不是仅选择一种遍历顺序。
回答应覆盖 依赖先于使用 区分返回值与全局答案 状态语义排除非法组合 ☆ 收藏 自评 需重学 不完整 能解释
Q2 · 给定前序和中序遍历，一定能唯一重建二叉树吗？ 在两序列确实来自同一棵树、节点标识唯一时，可以：前序首项确定根，在中序中定位后分出左右子树，再递归。若只有可重复的数值，根可能对应多个中序位置，结构可能不唯一。即使标识唯一，也应验证长度、元素集合和递归切分的一致性，非法输入不能靠越界或默认映射位置继续运行。若节点有唯一 ID，可将显示值与身份分开。
☆ 收藏 自评 需重学 不完整 能解释
Q3 · 递归改成迭代之后，是否就没有空间风险了？ 没有。显式栈仍保存待处理路径或任务，所需空间与状态数量有关，只是从调用栈转移到可控制的容器内存。它便于限制容量、报告失败和处理深树，但最坏 O(h) 或 O(n) 仍存在。还要检查 vector 扩容与对象生命周期。若要求 O(1) 辅助空间，可研究临时改链接等方法，同时接受更复杂的恢复、异常和并发约束。
回答应覆盖 区分调用栈与算法空间 保留最坏规模分析 低空间方案有结构代价 ☆ 收藏 自评 需重学 不完整 能解释
动手验证 实现迭代中序遍历，并解释当前指针与显式栈分别保存什么。再实现后序一次计算平衡性和高度，构造链形树比较它与重复求高度方案的访问次数。
ALG-08 / 树、图与数据结构选择 ○ 标为掌握
BFS、DFS 与图建模：先确定边的含义 BFS 用层数刻画无权最短路，DFS 用搜索路径刻画结构。visited 的含义和标记时机决定正确性。
先说明图是否有向、是否带权、是否允许重边和自环，顶点编号是否连续。邻接表通常占 O(V+E) 空间，适合稀疏图；邻接矩阵占 O(V²)，可快速判断一条边是否存在，但遍历每个点的邻接关系需要扫描整行。网格也是隐式图，邻居由坐标规则即时生成，不必总构造边表。
BFS 在所有边代价相同的图上按非递减距离扩展。第一次发现顶点时就标记并入队，可保证每点通常只入队一次；记录 dist[v]=dist[u]+1 和 parent[v]=u，可还原一条最短路径。从多个源点同时以距离 0 入队，得到到最近源的最少边数。若还要统计最短路条数，首次访问之外的等长贡献也要处理。
DFS 沿一条路径深入再回退，适合连通分量、环检测、拓扑结构和状态搜索。递归版的调用栈在最坏情况下为 O(V)。迭代版如果要保留与递归一致的完成时机，需显式保存“当前节点、下一个待处理邻居”等帧信息，不能只把所有邻居压栈就假定后序时间相同。
对邻接表做一次完整 BFS 或 DFS，访问每点、每边常数次，时间 O(V+E)。只从一个源出发仅覆盖可达部分；若要遍历整个非连通图，需从每个尚未访问的顶点重新启动。无向图通常把一条边存两次，此常数不改变复杂度，但影响边身份和父边处理。
适用边界：普通 BFS 不适用于任意权重最短路。边权只有 0 或 1 时可用双端队列的 0-1 BFS；一般非负权重可用 Dijkstra；允许负权需要另选算法并考虑负环。状态搜索的 visited 键必须包含决定未来的全部信息，例如迷宫中的位置与钥匙集合，仅按位置去重可能删掉必要路径。
深入面试与自测 Q1 · BFS 为什么在第一次发现顶点时就能确定无权最短距离？ 队列按距离层次处理：距离 d 的顶点在距离 d+1 的顶点之前扩展。首次从距离 d 的节点发现 v，就得到长度 d+1 的路径；如果存在更短路径，它的倒数第二个节点应更早被处理，v 就应更早发现，矛盾。这个论证依赖所有边代价相同。第一次发现时标记还能防止多个前驱重复入队，但统计最短路径条数时仍需累加其他等长前驱。
☆ 收藏 自评 需重学 不完整 能解释
Q2 · 有向图判环为何不能仅用一个 visited 数组？ 访问过某节点不代表当前路径能回到它；有向无环图也可能有多条路径汇入同一节点。常用三色状态：未访问、正在当前递归路径中、已经完成。遇到指向“正在路径中”节点的边才构成回边和有向环，指向完成节点的边本身不能证明有环。无向图则要排除来自父边的反向存储；存在平行边时应按边 ID 排除，不能简单忽略所有指向父节点的边。
回答应覆盖 区分全局访问与当前路径 指出交叉边反例 处理无向重边细节 ☆ 收藏 自评 需重学 不完整 能解释
Q3 · 何时可以压缩 visited 状态，何时必须增加维度？ 只有在相同状态下可用动作、未来代价及目标判定完全等价，或其中一个状态被另一个严格支配时，才能合并。带钥匙迷宫到达同一坐标但持有钥匙不同，未来可通行门不同，必须保留钥匙集合；有剩余预算、时间周期等限制时也类似。若证明“同位置、更多钥匙、成本不高”支配另一状态，可做更细的剪枝，但维护支配关系本身也有成本。
回答应覆盖 状态由未来行为定义 给出缺维导致错误的例子 支配剪枝需证明 ☆ 收藏 自评 需重学 不完整 能解释
Q4 · 在内存受限的大图中，BFS 和 DFS 如何取舍？ BFS 必须保存当前及后续层的前沿，宽图上队列可能很大；DFS 保存当前路径与待处理分支，深图上栈可能很大，二者最坏辅助空间都可达 O(V)。若需要无权最短路，不能仅因 DFS 内存更小就替换，因为结果语义不同。可根据图结构考虑双向 BFS、隐式生成邻居或外存方案；双向 BFS 还需正确的层扩展和相遇终止条件，有向图反向搜索需使用反向边。
☆ 收藏 自评 需重学 不完整 能解释
动手验证 在同一张含不连通部分、重边和自环的图上实现 BFS 距离与 DFS 三色环检测。给 BFS 添加 parent 还原路径，并逐边验证路径合法且边数等于 dist；再构造带权图反例说明普通 BFS 的限制。
ALG-09 / 树、图与数据结构选择 ○ 标为掌握
拓扑排序与并查集：依赖顺序和集合连通 拓扑排序解决有向依赖，并查集维护无向连通集合。二者都能关联环问题，但信息能力不同。
有向图的拓扑序要求每条边 u→v 都满足 u 排在 v 前；存在拓扑序当且仅当图是 DAG。Kahn 算法维护尚未移除顶点在残余图中的入度：先把所有零入度顶点入队，每取出一个顶点就删除其出边，新的零入度顶点继续入队。若最终取出 V 个顶点则成功，否则有环。邻接表实现为 O(V+E)。
入度统计与删除必须采用相同的边语义。若保留重边，统计时每条都加一，删除时每条都减一；只在一侧去重会破坏不变量。自环直接形成有向环。非连通 DAG 仍有拓扑序；空图的空序列也合法。若要求字典序最小的拓扑序，可用小根堆替代队列，顶点选择成本相应增加。
并查集用父指针表示不相交集合，find 返回代表元，union 合并两个不同集合。按大小或秩合并，并配合路径压缩，可使一串操作达到近似常数的摊还成本，常写为反 Ackermann 函数 α(n)。这是操作序列的摊还界，不应说每一次 find 都严格 O(1)，也不应把代表元当作集合的永久业务 ID。
并查集适合增量无向连通性，以及 Kruskal 最小生成森林中判定边的两个端点是否已经相连。向无向图加入边时，若端点已连通，新边会闭合一个环。对有向图，仅有“是否属于同一无向集合”不足以描述方向和可达性，不能据此判断有向环。
适用边界：普通并查集不直接支持删除边、集合拆分或路径输出。离线删边可在条件允许时逆序变成加边；更一般的动态连通性可用时间分治与可回滚并查集。回滚时通常避免普通路径压缩，改用按大小合并并记录修改，否则 find 的大量父指针更新都要被记录和恢复。
深入面试与自测 Q1 · Kahn 算法结束后没有被输出的节点都在环里吗？ 不一定。残余图没有零入度顶点可继续移除，说明其中存在环，但环可通过有向路径阻塞下游节点。例如 A→B、B→A、B→C，C 不在任何环中，却仍有来自 B 的入边而无法输出。若要精确定位环成员，可求强连通分量：含多个顶点的分量，或含自环的单顶点分量，才属于有向环结构。
回答应覆盖 区分环成员与受阻下游 给出最小反例 知道强连通分量用途 ☆ 收藏 自评 需重学 不完整 能解释
Q2 · 如何判断一个 DAG 的拓扑序是否唯一？ 在 Kahn 算法的每一步，如果可选零入度顶点恰好一个，下一位置被强制确定；若某步有两个或更多，就可先选其中任意一个，得到不同的合法拓扑序。因此在确认最终确实处理全部顶点的前提下，每一步可选集合大小均为 1 等价于拓扑序唯一。用小根堆得到确定输出只是人为选择规则，不代表原图的拓扑序唯一。
回答应覆盖 用可选集合证明 先确认 DAG 区分确定实现与数学唯一 ☆ 收藏 自评 需重学 不完整 能解释
Q3 · 并查集能否用于课程依赖的循环检测？ 普通并查集不能正确完成有向依赖判环。它只记录无向连通集合，丢失边方向。例如 A→B、A→C、B→C 是 DAG，但第三条边连接的两点可能已经属于同一无向集合；据此报环就是误判。课程依赖应使用拓扑排序或 DFS 当前路径标记。并查集适合的问题是无向连接关系，以及在增量加边时判断是否连接了已连通的两个端点。
回答应覆盖 说明丢失方向信息 能构造 DAG 误判反例 选用拓扑或三色 DFS ☆ 收藏 自评 需重学 不完整 能解释
Q4 · 为什么可回滚并查集通常不使用普通路径压缩？ 路径压缩会在一次 find 中改写路径上多个节点的父指针，回滚必须记录并逆序恢复所有这些修改，否则历史状态被破坏。按大小合并而不压缩时，每次成功合并只需记录少量变化，树高为 O(log n)，find 的成本可预测。并不是路径压缩理论上绝对不能回滚，而是记录成本、复杂度证明与实现都更难，通常不值得为此破坏简单的回滚契约。
回答应覆盖 理解 find 也会写状态 用按大小保持对数高度 解释工程取舍而非绝对禁令 ☆ 收藏 自评 需重学 不完整 能解释
完整实验 已验证 · MSVC 19.37 / x64 · c++17
返回 optional：有序列时包含一个合法拓扑序，出现环时为 nullopt，非法顶点编号抛出异常。保留重边并对每条边一致加减入度。检查空图、独立点、重边、自环、环后尾链，并对三顶点全部 512 个有向图用排列穷举作独立对照；只验证合法性，不要求某个固定拓扑序。未定义 NDEBUG 时断言才有效，实际运行由执行验证确认。
查看完整源代码 #include <algorithm>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <limits>
#include <numeric>
#include <optional>
#include <queue>
#include <stdexcept>
#include <utility>
#include <vector>
using Edge = std::pair<std::size_t, std::size_t>;
using Order = std::vector<std::size_t>;
std::optional<Order> topological_sort(
std::size_t n, const std::vector<Edge>& edges) {
std::vector<std::vector<std::size_t>> out(n);
std::vector<std::size_t> indegree(n, 0);
for (const auto& edge : edges) {
const auto u = edge.first, v = edge.second;
if (u >= n || v >= n) throw std::out_of_range("vertex id");
if (indegree[v] == std::numeric_limits<std::size_t>::max())
throw std::overflow_error("indegree");
out[u].push_back(v);
++indegree[v];
}
std::queue<std::size_t> ready;
for (std::size_t v = 0; v < n; ++v)
if (indegree[v] == 0) ready.push(v);
Order order;
order.reserve(n);
while (!ready.empty()) {
const auto u = ready.front();
ready.pop();
order.push_back(u);
for (const auto v : out[u]) {
assert(indegree[v] > 0);
--indegree[v];
if (indegree[v] == 0) ready.push(v);
}
}
if (order.size() != n) return std::nullopt;
return order;
}
bool valid_order(std::size_t n, const std::vector<Edge>& edges,
const Order& order) {
if (order.size() != n) return false;
std::vector<std::size_t> position(n, n);
for (std::size_t i = 0; i < n; ++i) {
if (order[i] >= n || position[order[i]] != n) return false;
position[order[i]] = i;
}
for (const auto& edge : edges) {
if (edge.first >= n || edge.second >= n) return false;
if (position[edge.first] >= position[edge.second]) return false;
}
return true;
}
// Independent oracle for small graphs: try every vertex permutation.
bool brute_has_order(std::size_t n, const std::vector<Edge>& edges) {
Order order(n);
std::iota(order.begin(), order.end(), std::size_t{0});
do {
if (valid_order(n, edges, order)) return true;
} while (std::next_permutation(order.begin(), order.end()));
return false;
}
void check(std::size_t n, const std::vector<Edge>& edges) {
const auto result = topological_sort(n, edges);
assert(result.has_value() == brute_has_order(n, edges));
if (result) assert(valid_order(n, edges, *result));
}
int main() {
check(0, {});
check(4, {});
check(4, {{0, 1}, {0, 1}, {1, 2}});
check(3, {{0, 1}, {1, 0}, {1, 2}});
check(1, {{0, 0}});
// All 2^9 directed graphs on three vertices, including self-loops.
for (unsigned mask = 0; mask < (1u << 9); ++mask) {
std::vector<Edge> edges;
for (std::size_t u = 0; u < 3; ++u)
for (std::size_t v = 0; v < 3; ++v)
if ((mask & (1u << (u * 3 + v))) != 0)
edges.emplace_back(u, v);
check(3, edges);
}
bool rejected = false;
try {
(void)topological_sort(2, {{0, 2}});
} catch (const std::out_of_range&) {
rejected = true;
}
assert(rejected);
std::cout << "topological sort: all assertions passed\n";
}
预期行为 topological sort: all assertions passed
下载源代码 这里的通过记录只证明指定编译器和测试输入上的结果，不证明所有平台或全部输入都正确。
动手验证 实现 Kahn 排序并验证每条边的先后关系，而不比较唯一固定序列。测试空图、独立点、重边、自环、环后接一条尾链。再说明最后一种图中，未处理的尾链节点为何未必属于环。
ALG-10 / 树、图与数据结构选择 ○ 标为掌握
堆与 Top K：维护当前最有价值的候选 堆只保证堆顶与父子关系，不保证整体有序。选择 Top K 方案要看是否流式、是否需要排序和更新。
二叉堆是满足父子优先级关系的完全二叉树，通常使用连续数组存储。堆顶查询 O(1)，插入和删除堆顶 O(log n)。自底向上建堆是 O(n)，因为多数节点接近叶子、需要下沉的高度很小；逐个插入的最坏总成本则为 O(n log n)。
求最大的 K 个元素，可维护大小不超过 K 的小根堆。堆顶是已保留候选中最小的值：新值不大于堆顶时无法改进候选集合，大于时替换堆顶。对 K≥1，扫描 n 个输入的上界可写为 O(n log(K+1))、额外空间 O(K)；K=0 直接返回空结果。若还要求从大到小输出，需额外排序或逐个弹出再反转。
静态数组只需选出前 K 个而不要求顺序时，std::nth_element 通常更合适；C++17 对其非并行版本给出平均线性复杂度。若需要前 K 个有序，可使用 partial_sort，或分区后排序前 K 个。K 等于 n 时直接排序更清楚；随机快速选择的期望表现不能被表述为确定性最坏线性。
std::priority_queue 默认是大根堆，使用 std::greater 等比较器可得到小根堆。比较器需要严格弱序，不能写成 <=；多字段排序应明确主次键和相同分数的处理。若业务要求同分项按到达先后输出，就把序号作为显式次级键，不能依赖堆的稳定性。
适用边界：priority_queue 不提供任意元素删除或 decrease-key 接口。频率变化的在线 Top K、任务优先级更新等问题，可用带索引的堆、平衡树，或为旧记录打版本并延迟丢弃。延迟删除会积累失效条目，需要清理策略和内存界；不能只声明每次操作 O(log K) 而忽略堆实际大小。
深入面试与自测 Q1 · 为什么建堆 O(n)，而不是每个节点 O(log n) 得到 O(n log n)？ O(log n) 是单个根附近节点下沉的最坏高度，不能把它当成每个节点都实际承担的成本。约一半节点是叶子不需下沉，约四分之一节点最多下一层，约八分之一最多两层。总工作量可由 n×Σ(h/2^(h+1)) 这样的收敛级数界定为 O(n)。逐个插入则每次可能从叶子向上移动，属于另一种建堆过程，最坏 O(n log n)。
☆ 收藏 自评 需重学 不完整 能解释
Q2 · 不同机器各取本地 Top K，再合并能得到全局 Top K 吗？ 若每条记录有固定可比较分数，各分片互不遗漏，并使用一致的全序打破平分，那么全局 Top K 必在各分片本地 Top K 的并集中：一个未入本地 Top K 的记录已有至少 K 个本地记录排在它前面，不可能进入全局前 K。但如果目标是按键汇总后的全局最高频项，这个结论不成立；某键在每片都不突出，累计后却可能最高，需要先正确聚合或使用带误差保证的摘要算法。
回答应覆盖 给出候选包含证明 明确同分规则 区分记录排名与聚合排名 ☆ 收藏 自评 需重学 不完整 能解释
Q3 · 怎样处理堆中任务的优先级更新？ 直接修改外部对象的优先级不会自动重排堆，甚至使比较器依赖的关系在堆内失效。可维护元素到堆下标的映射并上浮或下沉；也可插入带新版本号的记录，弹出时与当前版本比较，跳过旧记录。前者要求每次交换同步索引，后者实现简单但会积累旧数据，需要定期重建或容量限制。选择应结合更新频率、实时延迟和内存要求。
回答应覆盖 识别堆关系失效 给出索引堆与版本方案 计算失效条目的成本 ☆ 收藏 自评 需重学 不完整 能解释
动手验证 实现流式最大 K 个值，定义重复值是否按出现次数保留，测试 K=0、K=1、K>n、全部相等。对相同输入分别使用堆和排序验证结果多重集合一致，不依赖堆的遍历顺序。
ALG-11 / 搜索与动态规划 ○ 标为掌握
回溯：状态恢复、去重与安全剪枝 回溯枚举决策树；正确剪枝删除不可能贡献答案的分支，状态恢复保证不同分支互不污染。
把问题写成“状态、下一步选择、终止条件、结果如何产生”。每个分支先做选择，再递归探索，最后撤销对共享状态的修改。状态可通过传值隔离，也可通过原地修改与恢复减少复制；后一种方式必须保证所有退出路径都恢复，包括提前返回和异常路径。
复杂度与搜索树和输出规模有关。n 个不同元素的所有子集有 2^n 个，若每个结果复制最多 n 个元素，总输出成本可达 O(n·2^n)；全排列有 n! 个，完整输出至少承担对应结果体积。剪枝能大幅减少实际访问，但没有证明时不能把最坏指数复杂度写成多项式。
重复值去重须区分同一层与同一条路径。排序后生成唯一排列时，若 a[i]==a[i-1] 且前一个相等元素尚未在当前路径使用，可跳过当前选择，避免同层把等价元素交换生成相同结果；前一个已经使用时，当前元素仍可加入路径，否则会错误遗漏包含多个相等值的排列。
剪枝必须有不会错删解的理由。求组合和时，“当前和超过目标就返回”仅在后续可选数均非负等条件下可靠；允许负数时后续可能把和拉回。最优解搜索可用剩余收益的乐观上界或代价下界，与当前最优答案比较后剪枝；界估计方向错误会悄悄删掉真正最优解。
适用边界：全局 visited 只适合未来完全相同且无须区分路径贡献的状态。枚举所有路径时，可能只应记录当前路径中的访问情况并在回退时清除；把所有历史节点永久标记会漏解。记忆化也需要完整状态键，并考虑目标是计数、最优值还是列出不同结果。
深入面试与自测 Q1 · 为什么唯一排列中的去重条件要检查前一个相等元素是否已使用？ 同一层中两个尚未使用的相等元素作为下一项，会形成数值完全相同的后续分支，因此固定先用较前的那个即可。但若前一个已经在当前路径内，选择后一个代表使用输入中的另一次出现，是必要的。例如 [1,1,2] 必须允许路径 [1] 后再选另一个 1。条件“相等且前一个未使用时跳过”区分了同层交换重复与路径内合法的多重使用。
☆ 收藏 自评 需重学 不完整 能解释
Q2 · 怎样判断一个剪枝规则是否正确？ 把规则表述为逻辑命题：被剪枝状态的所有后继都不可能满足要求，或不可能优于当前最优解。然后使用输入约束证明，而不是看几个样例。例如后续值均非负时当前和大于目标无法恢复；存在负数时该命题立即失效。可用小规模完整枚举作为对照检查剪枝版，同时专门构造边界反例。最优值的上下界方向尤其重要：必须对未探索空间保持乐观估计。
回答应覆盖 证明全部后继不可行或不优 指出约束变化影响 对照穷举检验规则 ☆ 收藏 自评 需重学 不完整 能解释
Q3 · 回溯加记忆化什么时候能变成动态规划，什么时候会漏解？ 若两个搜索路径到达相同完整状态后，未来选择及其贡献完全相同，可以缓存该状态的最优值或方案数，从而避免重复求解。状态只含当前位置而遗漏已使用集合、剩余资源等信息时，未来并不相同，缓存会错误合并。若任务是列出所有不同路径，即使未来后缀相同，不同前缀仍可能对应不同输出，不能简单“访问过就跳过”；可以缓存后缀结果再与前缀组合，但输出成本仍在。
回答应覆盖 状态满足未来等价 区分计数、最优与枚举 不忽略输出规模 ☆ 收藏 自评 需重学 不完整 能解释
动手验证 对 [1,1,2] 生成不重复排列，验证恰好得到 3 个结果且每个结果的元素多重集合相同。将含负数的组合和例子与简单“超目标返回”实现对照，找出被错删的解。
ALG-12 / 搜索与动态规划 ○ 标为掌握
动态规划：状态语义、依赖顺序与空间压缩 动态规划按依赖关系计算可复用子问题。状态、初值、遍历方向与答案位置应由同一语义推导。
先定义状态的一句话语义，再列转移、边界和计算顺序。0/1 背包可令 dp[i][c] 表示只使用前 i 件物品、总重量不超过 c 的最大价值；第 i 件可不取，或在重量允许时从 dp[i-1][c-w] 加上它的价值。两种选择都只依赖上一行，因此每件物品最多使用一次。
压缩成一维后，处理一件正重量物品时容量应从大到小更新，使 dp[c-w] 仍是上一件物品处理后的旧值。若从小到大，就可能读取本轮已经包含该物品的状态，从而允许重复使用。例如只有一件重量 2、价值 3 的物品，容量 4：0/1 背包答案是 3，升序更新却会得到 6。
初值取决于“至多”还是“恰好”。容量至多 c、允许不取物品时，所有初值为 0 合理；要求恰好装满时，只有容量 0 可达，其余状态应标记不可达。不可达状态不能直接与价值相加，使用负无穷哨兵时必须避免溢出和误判，也可使用 optional 或额外可达标志。
时间通常是状态数乘每个状态的转移数量；0/1 背包为 O(nW)、压缩空间 O(W)。W 是容量的数值而非编码位数，所以该复杂度是伪多项式；容量可达十亿时不能因为物品少就盲目建表。可根据约束考虑按价值维度建模、折半搜索或其他方案，选择前需重新估算状态数。
空间压缩保留了最优值，不一定保留恢复方案所需的历史。若要输出被选物品，可保存二维决策信息、使用持久化前驱记录，或通过重新计算分治恢复；在一维数组上随意保存可变下标前驱，可能被后续更新覆盖而重用同一物品。
适用边界：实验限定正重量、非负价值，允许空选择；对非法重量和负价值明确拒绝，并检查价值相加溢出。零重量物品可以在更一般模型中支持，但必须重新审查转移及循环终止。本节以拒绝零重量保持接口和证明一致，不把示例限制当成所有背包问题的限制。
深入面试与自测 Q1 · 为什么同样的背包公式，遍历方向一改就变成了不同问题？ 一维数组复用了上一行和当前行的存储。0/1 背包的转移需要上一行 dp[c-w]，容量倒序确保较小容量尚未在本轮写入；升序则可能读取当前行结果，等价于允许再次加入同一件物品，成为完全背包的依赖形式。方向并非独立技巧，而是对原二维依赖的实现。重量为 0、需要恰好装满或带数量限制时，都应从状态定义重新推导。
回答应覆盖 解释读旧行还是新行 用单物品反例验证 不机械套遍历方向 ☆ 收藏 自评 需重学 不完整 能解释
Q2 · 怎样发现状态缺少维度，导致“看起来能转移”却答案不对？ 寻找两个被映射到同一状态、但后续最优行为不同的历史。如果存在，状态丢失了必要信息。例如买卖股票时，只用第几天的最大收益，混合了持股和空仓，下一步允许的动作不同；应增加持仓状态，若有限次交易或冷冻期，还需加入相应维度。增加维度后再检查是否有信息可由其他维度推导，避免无意义膨胀。
回答应覆盖 用未来行为检验状态充分性 能给出缺维反例 兼顾状态规模 ☆ 收藏 自评 需重学 不完整 能解释
Q3 · 最长递增子序列的 O(n log n) 算法是否保存了一条真实子序列？ 常见 tails[len-1] 保存长度为 len 的递增子序列中最小可能末尾值，用较小末尾替换能保留更多后续扩展机会。tails 各位置可能来自不同时间的不同子序列，因此整个数组不能直接当作最终方案。严格递增用首个不小于当前值的位置更新；非递减用首个大于的位置。若要恢复序列，还需记录各长度末尾元素的原下标及每个元素的前驱下标。
回答应覆盖 准确描述 tails 含义 区分长度与方案 严格性决定二分边界 ☆ 收藏 自评 需重学 不完整 能解释
Q4 · 记忆化递归与自底向上 DP 应如何选择？ 两者可以计算同一状态依赖图。记忆化按需访问，适合可达状态稀疏且转移表达自然的情形，但有递归深度、缓存键和调用开销；自底向上便于控制顺序、压缩空间和连续内存访问，却可能计算许多无用状态。必须保证依赖无环或存在正确的迭代收敛模型，不能在一般循环依赖中仅加缓存就认为解决。选择时比较可达状态数、转移成本、内存和栈深度。
☆ 收藏 自评 需重学 不完整 能解释
完整实验 已验证 · MSVC 19.37 / x64 · c++17
本接口要求重量大于 0、价值非负，表示容量至多限制并允许空选择。倒序更新与枚举所有选/不选分支的独立实现比较，覆盖长度 0–5 的指定物品组合及容量 0–10；另外检查零重量、负价值、求和溢出与容量加一溢出。内存不足仍可能产生标准分配异常。以未定义 NDEBUG 的 C++17 构建运行，预期输出须由实际执行确认。
查看完整源代码 #include <algorithm>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <vector>
struct Item {
std::size_t weight;
long long value;
};
long long add_nonnegative(long long a, long long b) {
if (a < 0 || b < 0) throw std::invalid_argument("negative value");
if (a > std::numeric_limits<long long>::max() - b)
throw std::overflow_error("value sum");
return a + b;
}
// Positive weights, nonnegative values; each item can be selected once.
// Total weight may be less than capacity; choosing nothing is allowed.
long long knapsack01(const std::vector<Item>& items, std::size_t capacity) {
for (const auto& item : items)
if (item.weight == 0 || item.value < 0)
throw std::invalid_argument("item domain");
if (capacity == std::numeric_limits<std::size_t>::max())
throw std::length_error("capacity + 1");
std::vector<long long> dp(capacity + 1, 0);
for (const auto& item : items) {
if (item.weight > capacity) continue;
// weight > 0 guarantees this loop stops without unsigned wraparound.
for (std::size_t c = capacity; c >= item.weight; --c) {
const auto take = add_nonnegative(dp[c - item.weight], item.value);
dp[c] = std::max(dp[c], take);
}
}
return dp[capacity];
}
// Exponential oracle for the small valid inputs used below.
long long brute(const std::vector<Item>& items, std::size_t index,
std::size_t remaining) {
if (index == items.size()) return 0;
auto best = brute(items, index + 1, remaining);
const auto& item = items[index];
if (item.weight <= remaining) {
const auto take = add_nonnegative(
item.value, brute(items, index + 1, remaining - item.weight));
best = std::max(best, take);
}
return best;
}
void check(const std::vector<Item>& items) {
for (std::size_t capacity = 0; capacity <= 10; ++capacity)
assert(knapsack01(items, capacity) == brute(items, 0, capacity));
}
void enumerate(std::vector<Item>& items, std::size_t remaining) {
check(items);
if (remaining == 0) return;
const Item choices[] = {{1, 0}, {1, 2}, {2, 3}, {3, 4}};
for (const auto item : choices) {
items.push_back(item);
enumerate(items, remaining - 1);
items.pop_back();
}
}
int main() {
assert(knapsack01({}, 0) == 0);
assert(knapsack01({{2, 3}}, 4) == 3);
assert(knapsack01({{5, 7}}, 4) == 0);
assert(knapsack01({{2, 3}, {2, 4}}, 4) == 7);
assert(knapsack01({{1, 1}, {3, 4}, {4, 5}, {5, 7}}, 7) == 9);
assert(knapsack01({{1, std::numeric_limits<long long>::max()}}, 1)
== std::numeric_limits<long long>::max());
bool rejected_zero = false, rejected_negative = false;
bool rejected_overflow = false, rejected_capacity = false;
try { (void)knapsack01({{0, 1}}, 3); }
catch (const std::invalid_argument&) { rejected_zero = true; }
try { (void)knapsack01({{1, -1}}, 3); }
catch (const std::invalid_argument&) { rejected_negative = true; }
try {
(void)knapsack01(
{{1, std::numeric_limits<long long>::max()}, {1, 1}}, 2);
} catch (const std::overflow_error&) { rejected_overflow = true; }
try {
(void)knapsack01({}, std::numeric_limits<std::size_t>::max());
} catch (const std::length_error&) { rejected_capacity = true; }
assert(rejected_zero && rejected_negative);
assert(rejected_overflow && rejected_capacity);
std::vector<Item> items;
enumerate(items, 5);
std::cout << "0/1 knapsack: all assertions passed\n";
}
预期行为 0/1 knapsack: all assertions passed
下载源代码 这里的通过记录只证明指定编译器和测试输入上的结果，不证明所有平台或全部输入都正确。
动手验证 先写二维 0/1 背包，再压缩为一维，分别证明转移与倒序更新。对小规模数据枚举全部子集作对照；加入空输入、容量 0、物品过重、同重不同价值和单物品不能重复使用的测试。
启用 JavaScript 后可保存记录、搜索和安装。以下正文可以直接阅读。