#036. 编程六：数据结构设计题
先用一个小例走通
流式数1、5、2到来时，排序中位数分别1、3、2。双堆让较小一半的最大值和较大一半的最小值始终可读，偶数时平均两边界。多重集合允许同一个值存多个副本，删除一个5不该删光所有5。设计题先说支持哪些操作及每项成本，再挑结构；“用了堆”不是完整接口说明。
#学习目标：设计题怎么答
设计题与算法题的差别在于：题面先给你一个接口（连续调用 add、窗口滑动、图上带锁移动），你要选一个内部表示让每次调用都便宜。答题的通用骨架是四步：先复述接口与调用模式（多少次插入、多少次查询、能否修改输入）；再选结构并说出不变量（结构内部任何时刻必须满足的性质）；然后做均摊分析（单次调用的最坏与均摊代价）；最后给边界（空流、单元素、重复值、溢出）。面试官评的是这条流程的完整度，而不只是能不能跑。
本章的三个主角恰好展示三种「状态设计」思路：中位数家族靠对半维护——两个堆各管一半，中位数永远在堆顶；带钥匙的可达性靠约束入状态——把「已收集的钥匙」并入搜索状态，或者用不动点迭代绕开显式状态；优惠券数位和靠数位 DP——把「数值大小约束」拆成逐位决策。设计题的本质是状态选择，这句话值得在面试里说出口。
先问清操作序列：流式 add 是均摊分析；窗口滑动含删除，堆不直接支持删除，就要多重集合或延迟删除。
双堆的正确性全部压在「左堆最大不大于右堆最小、大小差不超过一」上；讲清不变量比画十个例子更有说服力。
同一需求给出两套结构（双堆 vs 有序集合、不动点 BFS vs 状压 BFS），按数据范围选型，是设计题的满分姿势。
#知识点一：对半维护——双堆与多重集合
中位数只需要「正中间的一两个数」，因此不需要维护全序，只需要把数据切成较小的左半与较大的右半：左半用大根堆（堆顶是左半最大），右半用小根堆（堆顶是右半最小）。两条不变量：
有序不变量：任意时刻 \(\max(\text{low}) \le \min(\text{high})\)——新元素先与左堆顶比较决定进哪半，再平衡，保证不被破坏。
平衡不变量：\(|\text{low}| = |\text{high}|\) 或 \(|\text{low}| = |\text{high}| + 1\)——奇数个元素时左堆多一个，中位数即左堆顶；偶数个时取两堆顶平均。
均摊代价：每次 add 至多触发一次堆间搬运，\(O(\log n)\)；查询中位数只看堆顶，\(O(1)\)。
难点在删除：标准堆不支持删除任意元素。两条路：其一，换成两个有序多重集合（multiset），删除 \(O(\log n)\) 精确完成，窗口中位数用它最省心；其二，保留双堆，把要删的元素记入「延迟删除」哈希表，等到它浮到堆顶时才真正弹出，并各维护一个「有效大小」计数——在线算法与带删除场景的标准工业做法。代价是代码量翻倍，面试里先讲清思路再决定写哪版。
有序数组（或 sort 每次查询）插入是 \(O(n)\)，流式场景 \(n\) 次插入要 \(O(n^2)\)；平衡 BST 或树状数组上二分能做到 \(O(\log n)\) 但代码更重。双堆是「只需要中位数」这一需求下的最小代价结构——能讲出这层取舍，设计题就赢了一半。
#知识点二：把约束放进状态——钥匙、锁与不动点
普通图搜索的状态是「当前在哪个房间」；带锁之后，能走哪条边还取决于「手里有哪些钥匙」，状态必须扩成（房间，钥匙集合）。两种实现按钥匙类型数 \(k\) 分流：
状态 \((\text{room}, \text{mask})\)，mask 是已收集钥匙类型的位掩码。进入房间即把该房间钥匙类型置位。复杂度 \(O(2^k \cdot m)\)，\(k \le 20\) 左右可用。
从当前已访问房间出发做一轮普通 BFS，只能穿「已有钥匙」的隧道；访问新房间可能带来新钥匙，若本轮有新增就再跑一轮，直到无新增（不动点）。每轮至少新开一个房间，至多 \(n\) 轮，复杂度 \(O(n \cdot (n + m))\)，不依赖 \(k\)。
两者的关系值得多说一句：不动点版本等价于把「钥匙集合单调增长」这一性质抽出来做了松弛——钥匙只会增多不会减少，所以重复扫描必然收敛，这与贝尔曼-福特反复松弛边是同一种思想。面试里能指出「这是带单调性的松弛」会比背模板更加分。
#例题一：运行中位数（源题 66）
例题 1（源题 66）：写一个函数，返回一个数列的运行中位数（running median）——每读入一个数，输出至今所有数的中位数。
思路。知识点一的双堆：新数与左堆顶比较决定去向，插入后立即恢复平衡不变量；中位数按奇偶从堆顶读取。
class RunningMedian {
public:
void add(int x) {
if (low.empty() || x <= low.top()) low.push(x); // 新数进较小的一半
else high.push(x);
if (low.size() > high.size() + 1) { // 平衡：low 恰好多 0 或 1
high.push(low.top()); low.pop();
} else if (high.size() > low.size()) {
low.push(high.top()); high.pop();
}
}
double median() const {
if (low.empty()) return numeric_limits<double>::quiet_NaN(); // 空流：中位数无定义
return low.size() > high.size()
? (double)low.top() // 奇数个：左堆顶
: ((double)low.top() + high.top()) / 2.0; // 偶数个：两堆顶平均
}
private:
priority_queue<int> low; // 较小一半：大根堆
priority_queue<int, vector<int>, greater<int>> high; // 较大一半：小根堆
};数值结果。流 \(2, 1, 5, 7, 2, 0, 5\) 的运行中位数依次为 \(2,\ 1.5,\ 2,\ 3.5,\ 2,\ 2,\ 2\)。
复杂度与边界。add 均摊 \(O(\log n)\)（一次插入至多再搬运一个元素）、median \(O(1)\)，空间 \(O(n)\)。边界：空流返回 NaN 或抛异常（口径先说死）；偶数个的平均值注意 (a + b) / 2.0 用浮点除，两个 int 相加先提升为 long long 防溢出；重复值天然支持（堆不管相等）。
面试怎么讲。三句话定调：「中位数只需要中间一两个数，所以对半维护」「两条不变量：跨堆有序、大小差至多一」「add 对数、查询常数」。然后主动延伸：若还要支持删除，换双多重集合或延迟删除双堆——顺势把下一题引出来。
推导补全与自检。左侧大顶堆保存较小一半，右侧小顶堆保存较大一半；维持左最大\(\le \)右最小、两边大小差\(\le 1\)。输入[5,1,3,2]的中位数应为5、3、3、2.5。偶数取(a+b)/2时先转浮点或更宽整数，避免两极值相加溢出。两个堆内部都无序，但分区不变量保证只有堆顶会参与中位数。
#例题二：滑动窗口中位数（源题 40）
例题 2（源题 40）：给定数列与窗口长度 \(k\)，给出每个长度为 \(k\) 的滑动子数组（sliding sublist）的中位数。
思路。窗口每滑一步 = 一次插入 + 一次删除 + 一次查询。堆不支持删除，用两个多重集合维护左右两半（与双堆完全同构的不变量），删除用 find 精确擦除一个实例，再平衡。
vector<double> slidingMedian(const vector<int>& a, int k) {
if (k <= 0 || k > (int)a.size()) return {};
multiset<int> low, high; // low：较小一半；high：较大一半
auto rebalance = [&]() {
while (low.size() > high.size() + 1) {
high.insert(*low.rbegin()); // 左半最大值上移
low.erase(prev(low.end()));
}
while (low.size() < high.size()) {
low.insert(*high.begin()); // 右半最小值下移
high.erase(high.begin());
}
};
vector<double> res;
for (int i = 0; i < (int)a.size(); ++i) {
if (low.empty() || a[i] <= *low.rbegin()) low.insert(a[i]);
else high.insert(a[i]); // 插入新元素到对应半区
if (i >= k) { // 窗口左界滑出：删除旧元素
int out = a[i - k];
auto it = low.find(out);
if (it != low.end()) low.erase(it);
else high.erase(high.find(out)); // 必在另一侧（不变量保证）
}
rebalance();
if (i >= k - 1) { // 窗口填满后逐个输出
long long m1 = *low.rbegin();
res.push_back(k % 2 == 1 ? (double)m1 : (m1 + *high.begin()) / 2.0);
}
}
return res;
}数值结果。\([1,3,-1,-3,5,3,6,7]\)、\(k=3\)：中位数序列 \(1, -1, -1, 3, 5, 6\)。
复杂度与边界。每步插入、删除、平衡都是 \(O(\log k)\)，总 \(O(n \log k)\)、空间 \(O(k)\)。边界：\(k = 1\) 时中位数就是元素本身；\(k\) 等于数组长度退化为单次中位数；重复值由多重集合天然处理（erase(iterator) 只删一个实例，切勿传值删除）。若面试官要求双堆版，就讲延迟删除：待删值进哈希计数，堆顶命中时才弹出，有效大小单独记账——思路分与代码分可以分开拿。
面试怎么讲。先说「窗口滑动引入删除，堆不擅长删除，两个多重集合是最短路径」，写完补一句均摊 \(O(n\log k)\)，并主动对比延迟删除双堆——这就是知识点一里 trade-off 表达的落地。
推导补全与自检。滑窗\([1,3,-1,-3,5]\)、\(k=3\)的中位数为1、\(-1\)、\(-1\)。删除只能擦掉一个相同值实例；multiset.erase(value)会删除该值全部副本，应find后erase(iterator)。每轮插入和删除后都恢复分区与大小不变量。若用延迟删除双堆，还需区分逻辑大小与物理堆长度，不能拿含过期元素的size直接比较。
#例题三：房间、钥匙与可达性（源题 61）
例题 3（源题 61）：\(n\) 个房间、\(m\) 条隧道，房间 \(i\) 内有一把类型为 \(r[i]\) 的钥匙，第 \(j\) 条隧道连接 \(u[j]\) 与 \(v[j]\) 但上锁，需要类型 \(c[j]\) 的钥匙才能通过。给定起点 \(s\)，问能访问哪些房间；再问从哪个房间出发能访问最多房间。
建模。图搜索的边带「钥匙门」约束。按知识点二：钥匙类型数未知时用不动点 BFS——每轮从已访问房间做一次普通 BFS（只穿已持有钥匙的隧道），新房间可能带来新钥匙，有新增就再来一轮。第二个问题枚举所有起点取最大（钥匙结构一般无法共享加速，这是诚实且正确的答案）。
// tunnels[j] = {u, v, 打开该隧道所需钥匙类型}；key[i] = 房间 i 内的钥匙类型
vector<int> reachableRooms(int n, int s, const vector<int>& key,
const vector<array<int, 3>>& tunnels) {
vector<vector<pair<int, int>>> adj(n); // (对端房间, 所需钥匙类型)
for (auto& [u, v, c] : tunnels) {
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
vector<char> vis(n, 0);
vis[s] = 1; // 进入起点房间
while (true) {
unordered_set<int> keys; // 已到过房间提供的钥匙
for (int i = 0; i < n; ++i) if (vis[i]) keys.insert(key[i]);
queue<int> q;
for (int i = 0; i < n; ++i) if (vis[i]) q.push(i);
int fresh = 0; // 本轮新开房间数
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto& [v, c] : adj[u])
if (!vis[v] && keys.count(c)) { // 钥匙在手才能穿隧道
vis[v] = 1; ++fresh;
keys.insert(key[v]); // 新钥匙当场生效
q.push(v);
}
}
if (fresh == 0) break; // 不动点：无新房间即收敛
}
vector<int> rooms;
for (int i = 0; i < n; ++i) if (vis[i]) rooms.push_back(i);
return rooms;
}
// 第二问：枚举所有起点，取可达房间最多者
int bestStart(int n, const vector<int>& key,
const vector<array<int, 3>>& tunnels) {
int bestCnt = -1, bestRoom = -1;
for (int s = 0; s < n; ++s) {
int cnt = (int)reachableRooms(n, s, key, tunnels).size();
if (cnt > bestCnt) { bestCnt = cnt; bestRoom = s; }
}
return bestRoom;
}数值结果。4 个房间，钥匙类型 \(\text{key} = [0,1,2,5]\)，隧道 \(\{0,1,5\}, \{1,2,1\}, \{2,3,2\}\)：从 0 出发只有钥匙类型 0，隧道 0–1 需要类型 5，只能访问 \(\{0\}\)；从 1 出发顺次拿到钥匙 1、2、5，反过来还能打开 0–1，四个房间全到。最佳起点是 1。
复杂度与边界。每轮 BFS \(O(n + m)\)，每轮至少新开一个房间，单起点 \(O(n(n+m))\)；枚举全部起点 \(O(n^2(n+m))\)，面试规模足够。若钥匙类型数 \(k \le 20\)，主动改口：「也可以状压 BFS，状态 \((\text{room}, \text{mask})\)，\(O(2^k m)\)，\(k\) 小的时候更快」——同一题给两套按范围分流的方案是设计题的标准答法。边界：起点房间钥匙必收；隧道双向可达（题意如此则建双向边）；自环与重边无影响。
面试怎么讲。先把「锁约束」翻译成状态扩展或不动点松弛（二选一讲透），用小例子演示「新钥匙回头开旧门」的循环打开过程，最后给两套实现的选型条件。
推导补全与自检。到达房间时获得新钥匙，必须重新激活此前因缺钥匙而阻塞的门；普通“一次扫描所有邻边后永久忘记”会漏路。可按钥匙类型存等待门，首次获得某类钥匙时把该类等待目标加入队列。单源每个门只需登记和解锁有限次；所有起点都求最优则朴素重复O(n(n+m))，不能把单源复杂度误报为整体。
#例题四：岛屿、完全背包与数位 DP（源题 53、75、69）
例题 4（源题 53）：给定 0/1 二维矩阵，1 表示陆地，识别其中的岛屿（四方向相邻的 1 连通块）并计数。
思路。洪泛（flood fill）：扫到一块未访问的陆地就把整座岛淹没，计数加一。DFS 版就地标记；图论基础（BFS/DFS、并查集）在 005 章有完整讲解，这里给最简实现。
int numIslands(vector<vector<char>>& g) {
int n = g.size(), m = g[0].size(), ans = 0;
function<void(int, int)> dfs = [&](int r, int c) {
if (r < 0 || r >= n || c < 0 || c >= m || g[r][c] != '1') return; // 越界或非陆地
g[r][c] = '0'; // 就地标记，防止回头
dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
};
for (int r = 0; r < n; ++r)
for (int c = 0; c < m; ++c)
if (g[r][c] == '1') { ++ans; dfs(r, c); } // 每次洪泛即一座新岛
return ans;
}复杂度与边界。时间空间均 \(O(nm)\)，每格至多访问两次。边界：空矩阵返回 0；全 1 矩阵答案 1。追问准备：不许改输入就用 visited 数组或并查集；矩阵大到放不进内存就按行扫描 + 并查集合并（面试只需说思路）。源题另一问「按系数找连通关系」即邻接判定（上下左右），口径先复述。
推导补全与自检。四连通的递归洪泛在访问一个1时立即改0，再看四邻居；否则相邻陆地会互相递归。\(1\times 1\)的1返回1、0返回0；空矩阵要先检查再取grid[0]。改原数组的副作用需明确，若后面还要使用原地形，应传副本或单独visited。所有格子只处理一次给O(RC)，递归栈最坏也为O(RC)。
例题 5（源题 75）：实现 \(f(a, b)\)：\(a\) 为正整数，\(b\) 为正整数列表，判断 \(a\) 能否表示为 \(b\) 中元素之和（每个元素可重复使用任意次）。
建模。完全背包（unbounded knapsack）的可达性版本：\(dp[x]\) 表示金额 \(x\) 能否凑出，\(dp[0] = \text{true}\)，转移 \(dp[x] = \bigvee_{v \in b,\ v \le x} dp[x - v]\)。
bool canSum(int a, const vector<int>& b) {
if (a == 0) return true; // 空和即为 0（题设 a 为正，此行是防御）
vector<char> dp(a + 1, 0);
dp[0] = 1; // 完全背包可达性
for (int x = 1; x <= a; ++x)
for (int v : b)
if (v <= x && dp[x - v]) { dp[x] = 1; break; }
return dp[a];
}数值结果。\(a = 11, b = [5, 3]\)：\(11 = 3+3+5\)，返回真；\(a = 7, b = [5, 3]\)：可达集 \(\{3,5,6,8,9,10,11,\ldots\}\) 不含 7，返回假。
复杂度与边界。时间 \(O(a \cdot |b|)\)、空间 \(O(a)\)。剪枝彩蛋：若 \(\gcd(b) \nmid a\) 直接返回假；gcd整除只是必要条件，不能凭“a很大”直接返回真。若要用Frobenius或模最小币值的最短路作短路，须证明对应条件与阈值；本例代码仍以完全背包为准。
推导补全与自检。可重复正整数凑和，从\(dp[0]=true\)出发，若按每种币遍历则金额必须正向；\(b=[3],a=6\)应为真，而\(0/1\)背包倒序会返回假。gcd(b)不整除a时可立即判假，但整除不充分，例如\(b=[4,6],a=2\)仍不可达。\(a=0\)应为真（空组合），零币和负币必须按输入约束排除以避免循环意义混乱。
例题 6（源题 69）：优惠券编号从 LowValue 到 HighValue，每张券的码是其数位和；获奖者均匀分配在所有码上。用动态规划求码的分配方式数、最少与最多的获奖人数（例：2 到 11 时，码 2 有两张券（2 与 11），其余码各一，共 9 种码、最多 2 人）。
建模。先求计数函数 \(f(N)\)：\(0..N\) 中每种数位和的券数。数位 DP：预处理 \(g[i][s]\)（\(i\) 个 0–9 自由数位凑出和 \(s\) 的方案数）；再逐位枚举「第 \(i\) 位首次小于 \(N\) 的数字」的情形，后缀自由。区间 \([\text{Lo}, \text{Hi}]\) 的计数为 \(f(\text{Hi}) - f(\text{Lo}-1)\)，非零项即码数，取最小/最大即所求。
// f(N)：0..N 中每种「数位和」的计数（数位 DP）
vector<long long> digitSumCounts(long long N) {
string D = to_string(N);
int n = D.size();
// g[i][s]：i 个 0..9 自由数位凑出和 s 的方案数
vector<vector<long long>> g(n + 1, vector<long long>(9 * n + 1, 0));
g[0][0] = 1;
for (int i = 1; i <= n; ++i)
for (int s = 0; s <= 9 * i; ++s)
for (int d = 0; d <= 9 && d <= s; ++d) g[i][s] += g[i - 1][s - d];
vector<long long> cnt(9 * n + 1, 0);
int pref = 0; // 与 N 完全相同的前缀数位和
for (int i = 0; i < n; ++i) {
for (int d = 0; d < D[i] - '0'; ++d) // 第 i 位首次小于 N 的数字
for (int s = 0; s <= 9 * (n - i - 1); ++s)
cnt[pref + d + s] += g[n - i - 1][s];
pref += D[i] - '0';
}
cnt[pref] += 1; // N 自身
return cnt;
}
// 返回：码数、每个码上最少获奖人数、最多获奖人数
tuple<long long, long long, long long> couponStats(long long Lo, long long Hi) {
auto hi = digitSumCounts(Hi);
auto lo = Lo > 0 ? digitSumCounts(Lo - 1)
: vector<long long>(hi.size(), 0);
long long codes = 0, mn = LLONG_MAX, mx = 0;
for (size_t s = 0; s < hi.size(); ++s) {
long long c = hi[s] - (s < lo.size() ? lo[s] : 0);
if (c > 0) { ++codes; mn = min(mn, c); mx = max(mx, c); }
}
if (codes == 0) return {0, 0, 0}; // 空区间防御
return {codes, mn, mx};
}数值结果。\(\text{Lo}=2, \text{Hi}=11\)：码 1 只有券 10（1 张），码 2 有券 2 与 11（2 张），码 3–9 各 1 张——共 9 种码、最少 1 人、最多 2 人，与题给示例完全一致。
复杂度与边界。数位 DP 为 \(O(L^2 \cdot 81)\)（\(L\) 为位数，\(9L\) 为最大数位和），对 long long 范围绰绰有余。边界：Lo 为 0 时 \(f(\text{Lo}-1)\) 直接置零向量；数位和最大 \(9 \times 19 = 171\)，两表长度不同时以长表为准逐位相减。追问准备：若问「哪个码人数最多」，返回最大值下标即可；若码上均匀抽奖，某张券中奖概率是 \(\frac{1}{\text{该码券数}} \times \frac{1}{\text{码数}}\)——顺口就能补上概率口径。
C69的ways表述不清。为避免把不同统计量混成一个输出，先给每种数位和的完整券数分布。2…11的例子有9个非空码，最小桶大小1（8个码达到），最大桶大小2（只有码2达到）。若“ways”问可选择的码数，取9；若问达到最多获奖人数的选码方式数，取1；若问达到最少人数的方式数，取8。原文无法唯一决定它指哪个，不能把“最少人数1”直接等同于“方式数1”。digitSumCounts已经返回逐码计数，可据明确的输出规格统计。
推导补全与自检。数位DP状态含位数、当前数位和、是否贴上界；若统计[Low,High]，用\(F(High)-F(Low-1)\)逐个数位和相减。前导零不改变数位和，但若不允许编号0，应在范围差或started标记里去掉。取最小获奖人数时只对非零计数的码求最小，否则把从未出现的码算进去会错误得到0。
#例题五：调度、填充与回归口径（源题 29、30、73）
编程篇收尾的三道题分属贪心调度、位运算填充与统计口径，按题库完整性收录于此；它们共同的模式是「先用小例子把口径钉死，再动手」。
例题 7（源题 C29）：电影排片的接口与条件回顾
原题每天只限制总时长3小时，不限制片数。完整精确搜索实现见032章电影排片的minDaysMinutesExact；同一问题不再保留一份只解“每天两部”的代码冒充原题。
若时长恰为正整数小时1、2、3，可用计数闭式：设三类片数n₁、n₂、n₃，先让每部3小时独占一天，每部2小时尽可能带一部1小时，其余1小时每三部一天。总天数为\(n_3+n_2+\lceil\max(0,n_1-n_2)/3\rceil\)。[1,1,1,1,1]因此为2天。任意分钟时长不满足这个特殊值域条件，应回到装箱模型。
推导补全与自检。两个章节统一指向同一个原规则精确实现；受限版本须在接口、示例和复杂度中明确条件。三小时是180分钟，不能把参数用整数分钟而代码仍拿常数3比较。
例题 8（源题 C30）：用2的幂长度文件填满空段；地址对齐另设条件
无对齐要求的原文版本。PDF只给占用位置与2的幂大小，没有给地址对齐要求。不同连续空段不能跨越，长度L的每段可按二进制分解，最少popcount(L)个文件。下界理由：k个2的幂相加，二进制1的数量不超过k；构造恰好用每一个1位对应的块，达到下界。
若额外要求对齐。大小2ᵏ的块起始地址必须是2ᵏ的倍数，此时段起点也影响答案。在每段当前起点，从能对齐且不超过余长的块中选最大者。对齐的二进制块要么不交、要么包含，最大可行块不会跨越空段，其他对齐覆盖只能将它细分；合并细分块不会增加数量，所以贪心可取最少块。
long long minFiles(const string& slots, bool aligned = false) {
long long answer = 0, n = slots.size();
for (long long i = 0; i < n;) {
if (slots[i] != '.') { ++i; continue; }
long long start = i;
while (i < n && slots[i] == '.') ++i;
long long remaining = i - start;
if (!aligned) { answer += __builtin_popcountll(remaining); continue; }
while (remaining > 0) {
long long block = 1;
while (block <= remaining / 2 && start % (2 * block) == 0) block *= 2;
start += block; remaining -= block; ++answer;
}
}
return answer;
}slots=".#.."的空段为地址0的一格、地址2起的两格：两种模式均用2个块。slots="#..#"只有地址1、2两格空闲：不对齐可用一个大小2的块；对齐模式必须用两个大小1的块。默认aligned=false；地址从0开始，'.'为空闲、其他字符为已占。无对齐模式O(n)扫描、O(1)额外空间；对齐模式最坏O(n log n)时间，额外空间仍O(1)。
推导补全与自检。长度相同但起点不同的空段，在对齐要求下可能有不同答案，不能继续声称“无论对齐与否都等于popcount”。原题缺失对齐信息时，先按无对齐规则作答，再给显式开关的条件版本。
例题 9（源题 73，统计题）：线性回归中设计矩阵不可逆，怎么办？
诊断。\(X^\top X\) 奇异通常来自四种情形：特征完全共线（某列是其余列的线性组合）、虚拟变量陷阱（哑变量加全了常数列）、样本数小于特征数（\(n \lt p\)）、重复或常数列。先做诊断再谈药方，是这道题的正确顺序。
删共线列：去掉冗余列（或去掉一个哑变量基准类），让列满秩——最干净，前提是你能识别冗余。
岭回归：解 \((X^\top X + \lambda I)\hat\beta = X^\top y\)，\(\lambda \gt 0\) 使矩阵正定可逆；等价于给 \(\beta\) 加 \(L_2\) 惩罚，\(\lambda\) 由交叉验证选。
伪逆（Moore–Penrose）：\(\hat\beta = X^{+} y\) 用 SVD 计算，给出最小范数最小二乘解——不选 \(\lambda\) 的「自动」版本，数值上奇异值截断要设阈值。
补数据或重新采样：若不可逆源于 \(n \lt p\) 或采样缺陷，治本靠再收集数据或特征选择。
面试怎么讲。一句话总结：「先查共线来源，能删就删；删不了用岭回归或伪逆，两者分别是『可调参数的稳定解』与『最小范数解』」。岭回归的正则化视角与选择问题在 027 章展开，OLS 的几何与推导见 026 章。
推导补全与自检。\(X^TX\)奇异时系数不唯一，但最小二乘拟合向量\(X\widehat\beta\)是到列空间的唯一投影。SVD伪逆给最小欧氏范数解，Ridge改变目标并给收缩解，删冗余列改变参数表示，三者不是同一种处理。近奇异而非完全奇异时也应看条件数与样本外稳定性，不能只检查det是否恰为0；QR/SVD通常比显式求逆可靠。
#误区与边界
一、平衡写反：左堆只允许比右堆多一个，反了会偶数取错堆顶；二、多重集合删除传值：erase(value) 会删光所有实例，必须传 find 返回的迭代器；三、偶数平均溢出：两个 int 堆顶相加先转 long long 或 double。窗口题还有一个隐藏坑：删除元素找错半区会破坏不变量，应先在左半 find，找不到再删右半——依据是跨堆有序。
钥匙题：忘收起点房间的钥匙、或拿到新钥匙后不重访先前被锁住的边，都会漏解；若使用多轮不动点搜索，下一轮生效本身仍可正确收敛；状压与不动点按钥匙类型数分流，别在 \(k\) 很大时硬上 \(2^k\)。数位 DP：上界本身（\(N\) 那一支）要单独加一，区间相减时两表长度对齐。完全背包：\(a\) 特大时先做 gcd/Frobenius 短路。调度与填充题：装箱的「每天几部」与文件的「是否对齐」两个口径必须先问——这类题丢分大多丢在口径而非算法。
#检查清单
- 我能写出双堆运行中位数，口述两条不变量与 add 均摊 \(O(\log n)\)、查询 \(O(1)\) 的代价。
- 我能把双堆改造成双多重集合以支持删除，正确输出滑动窗口中位数，并说明延迟删除双堆的替代方案。
- 我能把「锁与钥匙」约束并入图搜索状态，实现不动点 BFS，并按钥匙类型数在 \(O(n(n+m))\) 与 \(O(2^k m)\) 之间选型。
- 我能用洪泛数岛屿并就地标记，说出禁止改输入时的 visited/并查集替代方案。
- 我能实现完全背包可达性 \(f(a,b)\)，并用 gcd 与 已给明确定理条件的剩余类方法分析大目标，而非凭一个未证明的Frobenius阈值短路。
- 我能用数位 DP 求任意区间内数位和的分布，并复现 2..11 的「9 种码、最多 2 人」示例。
- 我能对设计矩阵不可逆给出诊断顺序与三类药方（删列、岭回归、伪逆），并链接到正则化章节。
- 我拿到任何设计题都会先复述接口与调用模式，再选结构、讲不变量、做均摊分析、过边界清单。