# 算法面试模式闪卡：双指针、滑动窗口、图与动态规划 ![深蓝色背景上，中央光点连接双指针、滑动窗口、树、图、搜索路径和状态网格的抽象图形]() 用中文闪卡训练算法面试中的模式识别：从题目信号判断双指针、滑动窗口、图、动态规划等方法，并复习不变量、复杂度、边界条件与常见误选。 Автор [Flashcards Open Source App]() [Изучать эту колоду бесплатно]() Откроется Nibomo, и вы сможете начать изучение\. ## Сведения о колоде - Карточки: 216 карточек - Версия: 1 - Опубликовано: 3 сентября 2026 г. - Последнее обновление: 10 сентября 2026 г. - Лицензия: Common knowledge · CC0 1\.0 - Языки аудитории: [zh]() - Предмет: 计算机科学 - Теги: 算法面试, 数组与字符串, 线性结构, 树与堆, 图算法, 搜索与优化, 动态规划 ## Об этой колоде 这套 216 张中文闪卡面向准备算法面试的候选人，重点是先识别模式，再开始写代码。 卡片练习五类检索：从题目信号选择候选模式；从模式说出适用前提和核心不变量；根据输入与实现判断时间、辅助空间复杂度；从边界条件或失败症状定位漏洞；在易混场景中解释为什么某个模式不合适，并给出更合适的方向。只有当反向检索确实能帮助选型时才单独成卡；“复杂度 → 算法”“答案 → 题名”等歧义大、容易靠猜的映射被排除，也不机械生成所有事实排列。 学习顺序从数组、字符串、哈希表、栈和队列的基础判断开始，再交错引入双指针、滑动窗口、二分查找、链表、区间、树与堆；随后学习图表示、遍历、最短路、拓扑排序和并查集；最后处理回溯、贪心与动态规划。每个主题先建立前提和状态，再进入不变量、复杂度、边界条件与常见误选；相关变体会被错开，避免前一张卡直接提示下一张。 内容覆盖数组与字符串、哈希表、双指针、滑动窗口、栈与队列、二分查找、链表、区间、树、堆、图、并查集、回溯、贪心和动态规划。它不是按命名题目组织的题解卡包，也不是逐题代码合集；不包含完整题面、逐行代码、按公司整理的题库、机械反向卡或特定语言语法记忆。卡片本身不使用图片、音频或其他媒体，唯一媒体是一张原创生成的抽象封面。 所有问题、回答、顺序和元数据均独立创作，封面也是独立生成的原创构图。未复制任何第三方题面、答案、课程文字、代码、示例或图表。算法事实属于通用知识；在权利适用范围内，原创问题、回答、编排、元数据和封面以 CC0 1.0 提供。外部核对资料仍受其各自条款约束。 ## Похожие колоды - [日语五十音图闪卡：平假名、片假名与罗马音]() - [CFA Level III 投资组合管理路径闪卡：核心与路径复习]() - [高考数学导数公式与题型闪卡：单调性、极值与切线]() - [考研英语（一）核心词汇闪卡｜词义、搭配与语境]() - [教师资格证科目一《综合素质》核心考点闪卡]() - [大学英语四级（CET\-4）核心词汇闪卡：中文释义与例句]() ## Карточки в этой колоде ### Карточка 1 **Вопрос** 按索引遍历长度为 `n` 的序列时，最基本的合法边界是什么？ **Ответ** **合法索引满足 `0 <= i < n`。** 空序列的 `n = 0`，因此一次也不应访问；需要查看 `i + 1` 时，还要把条件收紧到 `i + 1 < n`。 ### Карточка 2 **Вопрос** 只需反复判断某个值是否出现过，通常先考虑什么结构？ **Ответ** **先考虑 hash set。** 它直接表达 membership；处理 `n` 个元素时通常用 `O(n)` 辅助空间，单次查询期望 `O(1)`。如果还要次数或位置，再改用 hash map。 ### Карточка 3 **Вопрос** 什么处理顺序是使用 stack 的强信号？ **Ответ** **最新进入、最先处理的 LIFO 顺序。** 当一个对象要等到后面的信息出现才结算，而且最近未结算对象必须先处理时，stack 往往最自然。 ### Карточка 4 **Вопрос** 决定原地修改数组前，必须先确认哪项语义前提？ **Ответ** **必须确认允许改写输入，而且后续不再需要原始排列。** 原地算法省辅助空间，但会破坏旧值或顺序；若调用方仍依赖原数据，就应复制或选用非破坏式方案。 ### Карточка 5 **Вопрос** 题目需要持续知道每个值出现了多少次，应维护什么状态？ **Ответ** **维护 `value -> count` 的 hash map。** 读到一个值就更新其计数；这样 membership 只是 `count > 0` 的特例，也能正确区分重复值。 ### Карточка 6 **Вопрос** 需要按发现顺序处理待办对象时，通常用什么结构保存 frontier？ **Ответ** **用 FIFO queue。** 先发现的对象先出队，新的对象从队尾加入，因此处理顺序稳定；如果改用 stack，顺序会变成深度优先式的后进先出。 ### Карточка 7 **Вопрос** 许多查询都要重复使用某位置左侧或右侧的聚合结果时，先考虑什么预处理？ **Ответ** **先考虑 prefix 或 suffix 聚合。** 一次 `O(n)` 预处理后，读取某个已保存的前缀或后缀结果是 `O(1)`；若查询任意中间区间，还要确认聚合能否用逆运算拆分，或改用别的结构。 ### Карточка 8 **Вопрос** 既要按值快速查找，又要返回原始位置时，hash map 应保存什么？ **Ответ** **保存 `value -> index`，或在重复值有意义时保存 `value -> indices`。** 不能默认一个值只有一个位置；覆盖旧索引是否正确，取决于需要任意位置、最近位置还是全部位置。 ### Карточка 9 **Вопрос** 检查成对分隔符的嵌套是否合法时，stack 应保存什么？ **Ответ** **保存尚未匹配的 opening delimiter。** 遇到 closing delimiter 时，它必须匹配栈顶；栈空却要关闭，或扫描结束后栈仍非空，都表示结构不合法。 ### Карточка 10 **Вопрос** 什么时候不能为了简化扫描而直接排序输入？ **Ответ** **当原始顺序或原始索引属于答案语义时，不能直接排序。** Comparison sort 通常花 `O(n log n)` 时间并重排元素；若排序仍有价值，可把原索引与值一起保存，或改用不破坏顺序的状态结构。 ### Карточка 11 **Вопрос** 既要去重又要保留首次出现顺序时，为什么不能只返回 hash set？ **Ответ** **因为普通 hash set 只表达唯一性，不保证还原首次出现顺序。** 扫描原序列时用 set 判断是否见过，并把首次出现的值追加到结果，才能同时满足两项要求。 ### Карточка 12 **Вопрос** 算法需要在两端都进行 `O(1)` 级别的插入或删除时，应优先考虑什么结构？ **Ответ** **优先考虑 deque。** queue 只暴露固定的入队端和出队端，stack 只操作一端；deque 明确支持两端操作。这里的 `O(1)` 指常见 deque 实现的摊还或最坏界，需以具体实现为准。 ### Карточка 13 **Вопрос** 判断数组扫描复杂度时，比“代码有几层循环”更可靠的做法是什么？ **Ответ** **计算每个元素被访问的总次数。** 若长度为 `n` 的序列中，每个元素只被常数次访问，且每次处理为 `O(1)`，总时间就是 `O(n)`；若对每个位置都重新扫描一个随 `n` 增长的范围，才可能达到 `O(n²)`。 ### Карточка 14 **Вопрос** 如何准确表述 hash table 查找、插入和删除的复杂度？ **Ответ** **通常是期望或摊还 `O(1)`，最坏 `O(n)`。** 结论依赖分布良好的 hash、受控装载因子和扩容策略；严重碰撞可让一次操作退化为线性扫描。保存最多 `n` 个键时，辅助空间为 `O(n)`。 ### Карточка 15 **Вопрос** 哪类“最近一个更大或更小元素”查询常提示 monotonic stack？ **Ответ** **当元素按顺序到达，并要找最近的支配元素时，考虑 monotonic stack。** 栈中只保留仍可能成为答案的候选；新元素会淘汰已不可能再被选中的栈顶。 ### Карточка 16 **Вопрос** 什么输入特征会让相向双指针成为候选模式？ **Ответ** **有序序列加上可单调判断的关系，是强信号。** 当当前结果偏小只可能通过移动 `left` 改善、偏大只可能通过移动 `right` 改善时，每一步才能安全排除一批候选。 ### Карточка 17 **Вопрос** 根节点和 `left`、`right` 引用如何表示一棵二叉树？ **Ответ** 从根节点沿 `left`、`right` 引用可到达全部节点。每个引用表示一条父到子的边；树结构还要求无环，并且除根外每个节点恰有一个父节点。 ### Карточка 18 **Вопрос** 要比较所有长度恰好为 `k` 的连续片段时，应怎样避免每次重算？ **Ответ** **维护固定长度 sliding window。** 窗口右移一格时加入新元素、移除离开的元素，便可复用上一窗口的 state；若更新各为 `O(1)`，扫描长度 `n` 的序列总计 `O(n)`。 ### Карточка 19 **Вопрос** 递归 DFS 遍历树时，每次调用最自然的子问题是什么？ **Ответ** 以当前节点为根的整棵子树。调用处理当前节点，并从左右子树拿回结果；这让递归参数和返回值都围绕一个明确的子树定义。 ### Карточка 20 **Вопрос** 使用半开区间写 binary search 时，循环不变量应怎样表述？ **Ответ** **候选区间始终是 `[left, right)`。** 初始化通常为 `left = 0, right = n`，循环条件是 `left < right`；每次更新必须严格缩短这个区间，空输入自然得到 `[0, 0)`。 ### Карточка 21 **Вопрос** 树的 BFS 怎样准确分隔当前层与下一层？ **Ответ** 处理一层前先记录当前队列长度 `levelSize`，只弹出这 `levelSize` 个节点。处理期间新入队的孩子自然属于下一层。 ### Карточка 22 **Вопрос** 链表操作会频繁改动头节点时，sentinel 能消除哪类分支？ **Ответ** **它把“头节点前面没有 predecessor”这个特例变成普通情况。** 让 `sentinel.next` 指向真实头节点后，删除、插入和合并都可统一通过前驱重连，最后返回 `sentinel.next`。 ### Карточка 23 **Вопрос** 需要先处理父节点，再处理它的子树时，应选哪种遍历顺序？ **Ответ** 前序遍历：先当前节点，再左子树，最后右子树。它适合把父节点状态传给后代，或在进入子树前完成处理。 ### Карточка 24 **Вопрос** 处理区间前，为什么必须先确定闭区间还是半开区间？ **Ответ** **因为端点相等时是否重叠取决于区间约定。** 闭区间 `[a, b]` 与 `[b, c]` 共享 `b`；半开区间 `[a, b)` 与 `[b, c)` 不重叠。排序、合并和事件 tie-break 都必须沿用同一约定。 ### Карточка 25 **Вопрос** 含 `m` 个元素的 binary heap 中，读取 top、`push` 和 `pop` 各是什么复杂度？ **Ответ** 读取 top 是 `O(1)`；`push` 和弹出 top 都是 `O(log m)`。后两者最多沿堆高调整一次，binary heap 的高度是 `O(log m)`。 ### Карточка 26 **Вопрос** 相向双指针每次移动一端时，必须证明什么？ **Ответ** **必须证明被越过的候选不可能优于或满足答案。** 这个 discard invariant 通常来自排序与单调关系；若无法证明，移动指针只是猜测，可能漏掉有效组合。 ### Карточка 27 **Вопрос** 当前节点的答案依赖左右子树结果时，应优先想到哪种遍历顺序？ **Ответ** 后序遍历：先求左右子树，再处理当前节点。高度、子树大小和子树聚合都符合“孩子先完成，父节点再合并”的结构。 ### Карточка 28 **Вопрос** 可变 sliding window 能靠移动 `left` 修复违规状态，需要什么前提？ **Ответ** **可行性必须对窗口收缩呈单调变化。** 固定 `right` 后，移除左端元素应当只朝“更可行”的方向走；若收缩可能反复让状态变好又变坏，就不能用单向 `left` 安全排除候选。 ### Карточка 29 **Вопрос** 为什么把 `m` 个已有元素自底向上建成 binary heap 是 `O(m)`，而不是 `O(m log m)`？ **Ответ** 因为自底向上的 `heapify` 只让少量靠近根的节点下沉较远，大多数节点移动很短或不移动；按高度汇总工作量是 `O(m)`。逐个 `push` 才是 `O(m log m)`。 ### Карточка 30 **Вопрос** 怎样把“找第一个满足条件的位置”写成稳定的 binary search 目标？ **Ответ** **在 `P(i)` 从 false 单调变为 true 的前提下，搜索最小的 true 位置。** 当 `P(mid)` 为真时保留 `mid` 并收紧右界，否则排除 `mid` 及其左侧；结束后还要检查返回位置是否在范围内且确实满足条件。 ### Карточка 31 **Вопрос** 二叉树的中序遍历在什么前提下会得到非降序序列？ **Ответ** 这棵树必须满足 BST 的全局顺序约束，并采用一致的重复值策略。中序按左子树、当前节点、右子树访问；普通二叉树没有有序保证。 ### Карточка 32 **Вопрос** 迭代反转单链表时，`prev` 与 `current` 应保持什么不变量？ **Ответ** **`prev` 始终是已反转前缀的头，`current` 是尚未处理后缀的头。** 改写 `current.next` 前先保存原来的 `next`，再依次推进 `prev` 和 `current`，才不会丢失后缀。 ### Карточка 33 **Вопрос** 递归处理空子树时，base case 应返回什么？ **Ответ** 返回当前子问题的中性结果，而不是随手写一个固定值。例如计数返回 `0`，高度按所选定义返回 `0` 或 `-1`，布尔验证常返回 `true`。定义必须与合并公式一致。 ### Карточка 34 **Вопрос** 两个半开区间 `[a, b)` 与 `[c, d)` 的重叠条件是什么？ **Ответ** **重叠当且仅当 `max(a, c) < min(b, d)`。** 严格小于体现了半开语义：`b = c` 只是首尾相接，不共享任何点。若改成闭区间，相应比较通常要允许端点相等。 ### Карточка 35 **Вопрос** 扫描 `n` 个元素并保留最大的 `k` 个时，小根堆应维持什么不变量？ **Ответ** 堆中始终是当前见过元素里最大的至多 `k` 个，堆顶是候选里的最小门槛。假设 `1 ≤ k ≤ n`；堆未满时直接加入，满后只用更大值替换 top。时间 `O(n log k)`，辅助空间 `O(k)`。 ### Карточка 36 **Вопрос** 原地筛选或压缩数组时，read/write pointers 的核心不变量是什么？ **Ответ** **`[0, write)` 始终是已经确定的输出前缀，`read` 扫描尚未处理的输入。** 每遇到应保留的元素，就写到 `write` 并递增；前提是允许覆盖已读区域。 ### Карточка 37 **Вопрос** 访问一棵含 `n` 个节点、高度为 `h` 的树一次，递归遍历的时间和辅助空间是多少？ **Ответ** 时间通常是 `O(n)`，递归辅助空间是 `O(h)`。每个节点只处理常数次；调用栈只保存当前根到节点的路径。输出本身占用的空间应另计。 ### Карточка 38 **Вопрос** sliding window 的计数或总和状态必须始终对应什么范围？ **Ответ** **必须精确对应当前窗口 `[left, right]` 或 `[left, right)`，二者选定一种。** 扩张时先加入新元素，收缩时移除离开元素；边界约定和更新顺序不一致会产生 off-by-one。 ### Карточка 39 **Вопрос** 数据逐个到达、总长度未知，但只需随时保留最大的 `k` 个值，应选什么结构？ **Ответ** 选容量为 `k` 的小根堆，并假设 `k ≥ 1`。它不需要保存完整数据流；每个输入最坏做一次 `O(log k)` 的堆更新，辅助空间保持 `O(k)`。 ### Карточка 40 **Вопрос** “最后一个满足条件的位置”怎样借助边界 binary search 表达？ **Ответ** **在 predicate 从 true 单调变为 false 时，先找第一个 false，再取其前一个位置。** 这把右边界问题转成统一的左边界模板；返回前必须检查前一个位置存在，并确实属于有效范围。 ### Карточка 41 **Вопрос** 用栈实现“根、左、右”的迭代 DFS 时，孩子应按什么顺序入栈？ **Ответ** 先压入右孩子，再压入左孩子。栈是 LIFO，左孩子因此先弹出；若反过来入栈，实际访问顺序会变成“根、右、左”。 ### Карточка 42 **Вопрос** 为什么“单链表删除是 `O(1)`”必须附带节点定位前提？ **Ответ** **只有待改写的 predecessor 已知时，局部重连才是 `O(1)`。** 若先要从头找到第 `k` 个节点、目标值或其前驱，定位本身是 `O(n)`；不能把查找成本藏在删除操作之外。 ### Карточка 43 **Вопрос** 合并 `k` 个各自非降序、总计 `N` 个元素的序列时，堆里应保存什么？ **Ответ** 保存每个尚未耗尽序列的当前头部候选。每次弹出全局最小值，再把同一序列的下一个值入堆；时间 `O(N log k)`，辅助空间 `O(k)`。 ### Карточка 44 **Вопрос** 按起点排序后合并区间时，应保持什么扫描不变量？ **Ответ** **结果中已完成区间互不重叠，最后一个区间代表当前可扩展的 union。** 新区间若按既定端点语义与它重叠，就更新终点；否则追加为下一段。按起点排序保证后续起点不会倒退。 ### Карточка 45 **Вопрос** 树的 BFS 为什么不能笼统地说只占 `O(h)` 辅助空间？ **Ответ** 因为队列保存的是一段横向 frontier，空间由最大层宽 `w` 决定，即 `O(w)`，最坏可达 `O(n)`。`h` 描述的是高度，更直接对应 DFS 路径栈。 ### Карточка 46 **Вопрос** 判断一个序列能否按顺序匹配到另一个序列中时，双指针如何分工？ **Ответ** **一个指针指向下一个待匹配元素，另一个只向前扫描候选序列。** 匹配成功才推进前者；不变量是前者之前的元素已按顺序匹配，扫描过的位置无需回看。 ### Карточка 47 **Вопрос** 只保留 `k` 个候选时，第 `k` 大与第 `k` 小分别该用哪一侧的堆？ **Ответ** 假设 `1 ≤ k ≤ n`：第 `k` 大用容量 `k` 的小根堆；第 `k` 小用容量 `k` 的大根堆。堆顶始终是当前候选集合里最容易被淘汰的边界值。 ### Карточка 48 **Вопрос** 求最长可行窗口与最短可行窗口时，收缩时机有什么区别？ **Ответ** **最长问题通常在窗口违规时收缩；最短问题通常在窗口仍可行时持续收缩并更新答案。** 两者都依赖单调可行性，但优化目标决定何时记录候选。 ### Карточка 49 **Вопрос** 含 `n` 个节点的树做递归 DFS 时，调用栈何时是 `O(log n)`，何时会退化为 `O(n)`？ **Ответ** 只有树高 `h = O(log n)`，例如树明确平衡时，调用栈才是 `O(log n)`；链状或严重偏斜的树有 `h = O(n)`，调用栈也会达到 `O(n)`。 ### Карточка 50 **Вопрос** 没有显式有序数组时，什么条件仍允许在 answer space 上二分？ **Ответ** **候选答案必须有序，而且可行性 predicate 在某个边界只改变一次真假。** 每次检查 `mid` 后，predicate 要能证明一整侧都可排除；检查本身不必是 `O(1)`。 ### Карточка 51 **Вопрос** 什么时候直接排序通常比维护 top-k 堆更合适？ **Ответ** 需要完整有序结果，或 `k` 与 `n` 同量级时，排序通常更简单。comparison sort 用 `O(n log n)` 时间；容量 `k` 的堆适合只取少量候选，用 `O(n log k)` 时间和 `O(k)` 辅助空间。 ### Карточка 52 **Вопрос** 要在一次遍历中找到单链表中点，fast/slow pointers 应怎样移动？ **Ответ** **`slow` 每次走一步，`fast` 每次走两步。** 当 `fast` 到达末尾时，`slow` 约走了链长的一半；偶数长度时返回两个中点中的哪一个，取决于循环条件，必须事先约定。 ### Карточка 53 **Вопрос** 沿一个孩子方向查找 BST 的做法依赖什么前提，复杂度怎样写？ **Ответ** 前提是整棵树满足约定的 BST 顺序。查找时间是 `O(h)`；只有明确平衡时才是 `O(log n)`，任意 BST 在偏斜时最坏为 `O(n)`。 ### Карточка 54 **Вопрос** 要计算任一时刻同时活跃的区间数，扫描线维护什么量？ **Ответ** **维护当前 active count，并记录其最大值。** 按时间处理开始与结束事件：开始时加一，结束时减一；端点相同时谁先处理，必须由闭区间或半开区间语义决定。 ### Карточка 55 **Вопрос** 为什么 binary heap 不适合查找一个任意给定值？ **Ответ** 堆只保证父子之间的偏序，不保证左右子树内部有序。除 top 外，一个值可能出现在许多位置，因此查找任意值最坏仍要扫描 `O(m)` 个元素。 ### Карточка 56 **Вопрос** 双指针代码含嵌套 `while` 时，何时总时间仍是 `O(n)`？ **Ответ** **当每个指针都只单向移动，且各自总共最多跨过 `n` 个位置时。** 内层循环的所有迭代可以按指针移动次数合计，因此是 `O(n + n) = O(n)`，不是逐次相乘。 ### Карточка 57 **Вопрос** 在 BST 中只关心闭区间 `[L, R]` 内的值时，何时可剪掉整侧子树？ **Ответ** 当前值小于 `L` 时可跳过左子树；当前值大于 `R` 时可跳过右子树。这个剪枝依赖有效 BST 的全局顺序和已明确的闭区间语义。 ### Карточка 58 **Вопрос** 窗口允许重复值且要精确移除左端元素时，为什么 set 往往不够？ **Ответ** **因为 set 不记录同一值在窗口中还有几份。** 应维护 frequency map；元素离开时减一，只有计数降到零才删除键，这样窗口 state 才不会过早宣告该值消失。 ### Карточка 59 **Вопрос** 堆中旧条目无法高效定位删除时，lazy deletion 怎样保持 top 正确？ **Ответ** 另存最新状态或有效标记；每次读取 top 前，持续弹出已失效条目。每次弹出是 `O(log m)`，但每个旧条目最多清理一次，所以总清理成本可摊还；堆仍可能暂时保存所有未清理条目。 ### Карточка 60 **Вопрос** 如果 predicate 随候选值反复在 true 与 false 之间切换，为什么不能 binary search？ **Ответ** **因为一次判断无法安全排除完整的一侧。** Binary search 需要真假区间只有一个分界；predicate 非单调时，`mid` 的结果不能说明左侧或右侧全部无效。 ### Карточка 61 **Вопрос** 为什么只比较 BST 节点与它的直接孩子不足以验证整棵树？ **Ответ** 因为更深的后代也必须满足所有祖先带来的范围限制。递归时应传递允许的下界和上界，并按既定重复值策略决定边界是严格还是可包含。 ### Карточка 62 **Вопрос** 为什么一快一慢两个指针能用 `O(1)` 辅助空间检测链表中的环？ **Ответ** **进入环后，`fast` 每轮相对 `slow` 多前进一步，因此最终会追上它。** 若 `fast` 先到达 `null`，链表无环；整个过程最多线性步数，所以时间 `O(n)`、辅助空间 `O(1)`。 ### Карточка 63 **Вопрос** 用双堆维护数据流中位数时，需要维持哪两个不变量？ **Ответ** 小值半区用大根堆、大值半区用小根堆；两边大小最多相差 `1`，且前者所有值不大于后者所有值。插入是 `O(log n)`，读中位数是 `O(1)`，空间是 `O(n)`。 ### Карточка 64 **Вопрос** 半开区间 `[start, end)` 的扫描线中，同一时刻的结束和开始事件谁先处理？ **Ответ** **先处理结束，再处理开始。** 因为在半开语义下，旧区间在 `end` 已不活跃，新区间可从同一时刻开始；反过来会把本不重叠的两段短暂计为同时活跃。 ### Карточка 65 **Вопрос** BST 允许重复值时，为什么必须先约定重复值放在哪一侧？ **Ответ** 因为搜索、插入、验证和中序有序性的边界都依赖同一约定。例如“左侧严格小于、右侧大于等于”与“两侧都严格”不是同一个数据结构契约。 ### Карточка 66 **Вопрос** 无序序列上的关系不随指针移动单调变化时，为什么不应硬套相向双指针？ **Ответ** **因为移动任一端都无法证明被跳过的组合无效。** 若排序不破坏答案语义，可以先排序建立单调性；否则应考虑 hash 状态、完整搜索或别的能保留候选的方法。 ### Карточка 67 **Вопрос** 每个节点都要汇总其整棵子树的信息时，递归函数应返回什么？ **Ответ** 返回父节点合并时真正需要的子树摘要，例如大小、高度或最佳向下值。这样每个节点只合并一次，通常是 `O(n)` 时间和 `O(h)` 调用栈。 ### Карточка 68 **Вопрос** 窗口收缩到空时，哪些 state 必须同步恢复？ **Ответ** **所有只描述窗口内容的 state 都必须回到空状态。** 计数、总和、distinct 数和 deque 都不能残留已移除元素；同时边界应满足所选约定，例如半开窗口 `[left, right)` 在 `left = right` 时为空。 ### Карточка 69 **Вопрос** DFS 共用一个可变 `path` 记录当前根到节点路径时，离开节点前必须做什么？ **Ответ** 必须撤销本层加入的节点，也就是 `pop`。不回退会让一个分支的节点泄漏到兄弟分支；进入时 `push`、退出时 `pop` 正好维持“`path` 等于当前递归路径”的不变量。 ### Карточка 70 **Вопрос** 长度为 `n` 的候选区间每轮至少减半时，迭代和递归 binary search 的复杂度分别是什么？ **Ответ** **两者时间都是 `O(log n)`；迭代辅助空间 `O(1)`，递归调用栈 `O(log n)`。** 前提是每轮检查与边界更新为 `O(1)`；若每次 predicate 检查的上界为 `C(n)`，总时间上界是 `O(C(n) log n)`。 ### Карточка 71 **Вопрос** 树中经过当前节点的最长简单路径，为什么要组合两个孩子方向的贡献？ **Ответ** 因为这条路径可从一个子树上来，再进入另一个子树，所以要组合两个最大的向下长度；但返回给父节点时只能选其中一个方向。节点数或边数的口径要从 base case 到公式保持一致。 ### Карточка 72 **Вопрос** 快慢指针在环内相遇后，怎样找到环的入口？ **Ответ** **把一个指针移回头节点，再让两个指针每次各走一步；下一次相遇点就是环入口。** 这个结论来自相遇时走过距离的整圈关系，不需要额外 set，整体时间 `O(n)`、辅助空间 `O(1)`。 ### Карточка 73 **Вопрос** 树 DFS 把答案放在跨调用复用的全局变量里，最常见的正确性风险是什么？ **Ответ** 旧结果会污染新的遍历，兄弟分支也可能意外共享不该共享的状态。优先让递归返回子树结果；确需共享聚合量时，把它限制在单次调用范围并明确初始化。 ### Карточка 74 **Вопрос** 先按端点排序、再线性扫描 `n` 个区间时，整体复杂度应怎样写？ **Ответ** **时间是 `O(n log n)`，由 comparison sort 主导；扫描是 `O(n)`。** 辅助空间取决于排序实现，不能一概写成 `O(1)`；若把返回结果也计入总空间，最多 `n` 个新区间另占 `O(n)`。 ### Карточка 75 **Вопрос** 怎样在一次后序遍历中同时计算树高并发现不平衡子树？ **Ответ** 让递归返回高度或一个“不平衡” sentinel。任一孩子已不平衡，或左右高度差超过允许值，就继续向上传 sentinel；否则返回当前高度。这样是 `O(n)`，避免反复计算高度导致最坏 `O(n²)`。 ### Карточка 76 **Вопрос** monotonic stack 为什么常能在线性时间内完成整次扫描？ **Ответ** **每个元素最多入栈一次、出栈一次。** 虽然某一步可能连续弹出很多元素，但对 `n` 个元素合计只有 `O(n)` 次 push/pop；栈最多保存 `n` 个候选，辅助空间 `O(n)`。 ### Карточка 77 **Вопрос** 看到“树上的路径”时，写算法前最先要澄清什么？ **Ответ** 先澄清端点范围：根到叶、根到任意节点，还是任意节点到任意节点。还要确认长度按边还是按节点计；这些定义会直接改变 base case 和合并方式。 ### Карточка 78 **Вопрос** 可变 sliding window 有内层收缩循环时，何时总时间是 `O(n)`？ **Ответ** **当 `right` 与 `left` 都只向前，且各自最多移动 `n` 次时。** 对长度 `n` 的序列，所有扩张与收缩合计 `O(n)`；辅助空间等于窗口 state，可从 `O(1)` 到最多 `O(n)`。 ### Карточка 79 **Вопрос** 即使递归 DFS 的渐进空间是正确的，什么树形仍可能让实现栈溢出？ **Ответ** 高度接近 `n` 的链状或严重偏斜树。它需要 `O(n)` 层调用；输入深度可能超过运行时栈限制时，应改用显式栈或确认环境能承受该深度。 ### Карточка 80 **Вопрос** 整数 binary search 中，怎样计算 `mid` 更不容易溢出？ **Ответ** **使用 `mid = left + (right - left) / 2` 的整数取整形式。** 它避免先计算可能溢出的 `left + right`；向下还是向上取整要与边界更新配套，确保候选区间每轮严格缩小。 ### Карточка 81 **Вопрос** 普通根树中，后序 DFS 如何识别两个不同且已知存在节点的最低共同祖先？ **Ответ** 找最深的汇合点：当前节点自身和各子树返回的命中信号中，只要有两路覆盖两个目标，当前节点就是最低共同祖先。若目标不保证都存在，还必须另行确认两者确实被找到。 ### Карточка 82 **Вопрос** 合并两个已按同一规则排序的链表时，tail 应保持什么不变量？ **Ответ** **`tail` 始终指向已合并有序前缀的最后节点。** 每次比较两个当前节点，把较小者接到 `tail.next` 并推进对应指针；一条链耗尽后，剩余有序后缀可以整体接上。 ### Карточка 83 **Вопрос** 二叉树里什么才算叶节点？空树和单节点树分别怎样判断？ **Ответ** 叶节点是自身存在且 `left`、`right` 都为空的节点。空树没有叶节点；单节点树的根同时也是叶节点。不能把空引用本身当成叶节点。 ### Карточка 84 **Вопрос** 用两个 stack 实现 queue 时，怎样得到摊还 `O(1)` 的出队？ **Ответ** **入队压入 `in`；只有 `out` 为空时，才把 `in` 全部倒入 `out`。** 每个元素最多被压入和弹出常数次，所以一串 `m` 次操作总计 `O(m)`；单次搬运仍可能是 `O(n)`。 ### Карточка 85 **Вопрос** 树题中，什么信号更偏向 BFS，什么信号更偏向 DFS？ **Ответ** 逐层、离根最近或最少边数更偏向 BFS；子树聚合、根到节点状态和回溯路径更偏向 DFS。两者通常都能遍历全树，选择依据是需要的访问顺序与状态形状。 ### Карточка 86 **Вопрос** 含 `V` 个顶点、`E` 条边的稀疏图，通常应选哪种邻接表示？ **Ответ** 通常选 adjacency list。它占 `O(V+E)` 空间，并能只遍历真实存在的邻边；实现时也要为孤立顶点保留空邻接表或等价记录。 ### Карточка 87 **Вопрос** 需要列举一连串选择形成的所有可行结果时，应先把搜索过程看成什么结构？ **Ответ** 决策树。每一层表示一次选择，每条边表示一个候选动作，叶子或满足终止条件的节点表示完整结果；这正是回溯适用的基本信号。 ### Карточка 88 **Вопрос** adjacency list 中，有向边与无向边应怎样记录？ **Ответ** 有向边 `u → v` 只把 `v` 放进 `u` 的邻接表；无向边 `{u, v}` 通常同时记录 `u → v` 和 `v → u`。若 `E` 按逻辑无向边计数，存两次仍是 `O(V+E)` 空间。 ### Карточка 89 **Вопрос** 回溯中 `choose → explore → unchoose` 的核心不变量是什么？ **Ответ** 每次递归返回后，共享状态必须恢复到选择前的样子。这样下一个候选分支看到的是同一个父状态，而不是被前一分支污染的状态。 ### Карточка 90 **Вопрос** 图的 BFS 为什么通常要在入队时标记 `visited`，而不是出队时？ **Ответ** 入队时标记可保证每个顶点只进入队列一次。若等到出队，同一顶点可能被多个前驱重复入队，放大时间和空间；无权图中，首次发现时的距离也已是最短距离。 ### Карточка 91 **Вопрос** 为什么删除单链表中的当前节点通常需要它的 predecessor？ **Ответ** **因为要把 `predecessor.next` 改为 `current.next`。** 单链表没有反向链接；若只拿到当前节点，通用删除无法更新前一条边，尾节点尤其不能靠复制后继值处理。 ### Карточка 92 **Вопрос** 什么时候 adjacency matrix 比 adjacency list 更合适？ **Ответ** 图很稠密，或需要频繁 `O(1)` 判断任意两点是否有边时，matrix 更合适。代价是 `O(V²)` 空间，枚举一个顶点的全部邻居也要扫描 `O(V)` 个位置。 ### Карточка 93 **Вопрос** 怎样判断回溯递归参数是否记录了足够但不过量的状态？ **Ответ** 状态应恰好决定“接下来还能选什么”和“何时得到结果”。能由现有参数推导的信息不必重复存；缺少会影响合法候选的信息，则会让不同子问题被错误混在一起。 ### Карточка 94 **Вопрос** 图的 DFS 为什么不能像树遍历那样只递归所有邻居？ **Ответ** 图可能有环，也可能有多条路径到同一顶点，所以必须记录访问状态，避免无限递归和重复处理。仅有一个 `visited` 集合足够做普通可达性遍历，但某些环检测还需要更细状态。 ### Карточка 95 **Вопрос** 回溯的终止条件需要同时保证哪两件事？ **Ответ** 保证正确收集完整解，并阻止搜索越过有效深度。条件太早会漏解，太晚会访问无意义或越界状态；应直接对应“一个候选解已经完整”的定义。 ### Карточка 96 **Вопрос** 无权图中，求源点到各点的最少边数应选什么算法？ **Ответ** 选 BFS。它按距离层扩展，第一次发现顶点时就得到最少边数；用 adjacency list 时，时间 `O(V+E)`，队列和访问状态占 `O(V)`。 ### Карточка 97 **Вопрос** 用 monotonic deque 维护窗口最大值时，deque 中应保留什么？ **Ответ** **按值单调递减排列、且仍在窗口内的候选索引。** 新元素进入时从队尾删掉不大于它的旧候选，窗口左移时从队首删掉过期索引；队首因此始终是当前最大值的位置。 ### Карточка 98 **Вопрос** 用 adjacency list 完整遍历图时，BFS 或 DFS 的复杂度怎样写？ **Ответ** 时间是 `O(V+E)`，辅助状态通常是 `O(V)`，不含图本身。完整遍历要从每个未访问顶点启动一次；无向边虽在邻接表出现两次，不改变渐进复杂度。 ### Карточка 99 **Вопрос** 回溯里的 `path` 与控制搜索的状态有什么区别？ **Ответ** `path` 保存当前已选内容；控制状态决定下一步候选，例如位置、剩余额度或已用集合。两者可能重叠，但不能因为 `path` 可展示结果，就假定它包含全部搜索约束。 ### Карточка 100 **Вопрос** 怎样用一次总体线性的遍历统计无向图的连通分量？ **Ответ** 依次检查所有顶点；每遇到一个未访问顶点，就从它启动一次 BFS 或 DFS，并把分量数加一。用 adjacency list 时，每个顶点和边总共只处理常数次，时间 `O(V+E)`。 ### Карточка 101 **Вопрос** 设计回溯时，“生成候选”这一步应回答什么问题？ **Ответ** 它应列出从当前状态出发所有且仅有的合法下一步。漏掉候选会破坏完备性，加入非法候选则需要额外检查并扩大搜索树。 ### Карточка 102 **Вопрос** 同一个图改用 adjacency matrix 后，完整 BFS 或 DFS 为什么通常变成 `O(V²)`？ **Ответ** 因为每访问一个顶点，都要扫描长度为 `V` 的整行来找邻居；最多扫描 `V` 行，所以是 `O(V²)`，即使实际边很少也是如此。matrix 本身也占 `O(V²)` 空间。 ### Карточка 103 **Вопрос** 改写单链表的 `current.next` 前，最常见的防丢链动作是什么？ **Ответ** **先把原来的 `current.next` 保存到临时变量。** 一旦覆盖这条链接，又没有其他引用指向后缀，后续节点就无法继续访问；重连顺序应明确每一步仍能到达未处理部分。 ### Карточка 104 **Вопрос** 用 DFS 检测有向图环时，为什么需要 `white/gray/black` 三种状态？ **Ответ** `gray` 表示顶点仍在当前递归路径上，遇到指向 `gray` 的边就说明有环；`black` 表示该顶点已完整处理。单一 `visited` 无法区分“当前路径上的祖先”和“其他已完成分支”。 ### Карточка 105 **Вопрос** 把当前 `path` 加入结果集时，为什么通常要保存副本？ **Ответ** 因为 `path` 往往是后续会继续修改的可变容器。若只保存同一个引用，回溯撤销和后续选择会改掉已经收集的结果。 ### Карточка 106 **Вопрос** 无权图 BFS 能保证最短距离的核心队列不变量是什么？ **Ответ** 队列按从小到大的距离层处理顶点。距离为 `d` 的顶点只会发现尚未访问、距离为 `d+1` 的邻居，因此一个顶点首次被发现时，不可能还存在更短的未处理路径。 ### Карточка 107 **Вопрос** 只需生成无顺序的选择组合时，递归参数常用什么来避免反向重复？ **Ответ** 使用单调前进的 `start` 索引。下一层只从当前索引之后选择，使同一组元素只按一种顺序生成，而不是再生成顺序相反的副本。 ### Карточка 108 **Вопрос** 简单无向图中，DFS 遇到已访问邻居时，怎样区分父边与环？ **Ответ** 把进入当前顶点的 `parent` 一并传入；已访问邻居若不是 `parent`，就存在环。这个判断假设没有平行边；多重图要追踪边 ID，不能只比较父顶点。 ### Карточка 109 **Вопрос** monotonic deque 扫描 `n` 个元素时，为什么总维护成本是 `O(n)`？ **Ответ** **每个索引最多从队尾加入一次，并从队首或队尾删除一次。** 某一步虽可能连续删除多个索引，整次扫描的 deque 操作总数仍为 `O(n)`；最坏辅助空间为 `O(n)`。 ### Карточка 110 **Вопрос** 为什么普通 DFS 不能保证找到无权图中的最短路径？ **Ответ** DFS 会先沿一个分支走深，第一次到达目标的路径可能很长。无权最短路应使用按层扩展的 BFS；只有树中两点路径唯一等特殊结构，遍历顺序才不影响那条路径本身。 ### Карточка 111 **Вопрос** 一个剪枝条件要正确，必须证明什么？ **Ответ** 必须证明被剪掉的前缀不可能扩展成任何所需解。剪枝只是减少访问状态，不能靠“通常没有希望”来牺牲完备性。 ### Карточка 112 **Вопрос** 题目要求所有依赖都先于依赖者出现时，应想到什么图模型与算法？ **Ответ** 建有向依赖图并求 topological order。只有 DAG 才存在这种顺序；若图中有向环存在，就不可能同时满足所有先后约束。 ### Карточка 113 **Вопрос** 每个位置都可从尚未使用的元素中选择时，状态通常要增加什么？ **Ответ** 增加 `used` 集合或布尔数组。它记录当前路径已经占用的元素，使每层都能从全部未用元素中选择；这适合顺序会产生不同结果的排列型状态。 ### Карточка 114 **Вопрос** 无权图中要计算每个顶点到最近源点的距离，多个源点应怎样启动 BFS？ **Ответ** 把所有源点都以距离 `0` 同时入队，再做一次 BFS。它们共同形成第 `0` 层，后续首次发现距离就是到任一源点的最短距离；adjacency list 上仍是 `O(V+E)`。 ### Карточка 115 **Вопрос** 算法频繁按第 `k` 个位置访问元素时，为什么单链表通常不是合适选择？ **Ответ** **因为单链表没有随机访问，第 `k` 个位置需要从头走 `O(k)`。** 数组可按索引 `O(1)` 访问；链表的优势是已知位置附近的重连，不是按下标查找。 ### Карточка 116 **Вопрос** 边不断加入，只需回答“两点现在是否连通”时，应优先想到什么结构？ **Ответ** 优先想到 union-find。每条新边用 `union` 合并分量，查询时比较两个点的 `find` 结果；它适合增量式无向连通，不负责恢复具体路径。 ### Карточка 117 **Вопрос** 找到一个可行解后能否立即返回，取决于什么？ **Ответ** 取决于目标是“任意一个解”还是“全部解／最优解”。前者可短路；后者仍需探索其他可能分支，除非已有正确的最优性界。 ### Карточка 118 **Вопрос** 带权图的边权满足什么条件时，可以用 Dijkstra 求单源最短路？ **Ответ** 所有可达边的权重都必须非负。Dijkstra 每次确定当前 tentative distance 最小的未确定顶点；非负权保证以后经过更远顶点不可能把它改得更小。 ### Карточка 119 **Вопрос** 输入含重复值且结果按值去重时，怎样跳过同一层的重复分支？ **Ответ** 可为每层维护 `seen`；若排序不改变题意，也可先让相同值相邻，再跳过同层的等值候选。只跳同层重复，跨层出现同值可能代表合法的再次选择。 ### Карточка 120 **Вопрос** Kahn 拓扑排序中，入度为 `0` 的队列表示什么？ **Ответ** 它保存当前所有前置依赖都已移除的顶点。弹出一个顶点并删去它的出边后，新变成入度 `0` 的顶点入队；若最终处理数小于 `V`，图中有环。adjacency list 实现为 `O(V+E)` 时间、`O(V)` 辅助空间。 ### Карточка 121 **Вопрос** 用 queue 分层处理 frontier 时，怎样避免把下一层节点混入当前层？ **Ответ** **在处理本层前先记录当前 queue size，只弹出这固定数量的对象。** 过程中加入队尾的新对象属于下一层；不要让不断变化的 queue length 决定本层循环次数。 ### Карточка 122 **Вопрос** union-find 中，`find(x)` 返回值必须满足什么代表元不变量？ **Ответ** 它返回 `x` 所在分量的根代表元 `r`，且 `parent[r] = r`。两个元素连通当且仅当它们的根相同；路径压缩只能缩短父链，不能改变分量归属。 ### Карточка 123 **Вопрос** 为什么列举全部结果的回溯复杂度必须考虑输出规模？ **Ответ** 因为仅写出结果就需要与输出字节数成正比的时间。更准确的口径是 `O(访问状态数 × 每状态工作 + 输出规模)`；结果很多时，算法不可能比输出本身更快。 ### Карточка 124 **Вопрос** binary heap 没有 decrease-key 时，Dijkstra 怎样处理同一顶点的旧距离条目？ **Ответ** 每次松弛成功就压入新 `(distance, vertex)`；弹出时若距离不等于当前 `dist[vertex]`，就跳过旧条目。adjacency list 上这种 lazy 实现为 `O((V+E) log E)` 时间、最坏 `O(V+E)` 辅助空间；简单图中也可写成 `O((V+E) log V)`。 ### Карточка 125 **Вопрос** “输入位置互不相同”为什么不等于“生成结果按值互不重复”？ **Ответ** 不同索引可以保存相同值。用索引判断是否已使用只能防止重复占用同一位置；若结果按值判等，还要处理等值候选造成的对称分支。 ### Карточка 126 **Вопрос** DFS 怎样生成 topological order？ **Ответ** 在一个顶点的所有出邻居处理完后，把它加入 finish 列表，最后反转该列表。还要用三色状态检测有向环；有环时 finish 顺序不是有效拓扑序。 ### Карточка 127 **Вопрос** union by rank 或 size 为什么只能在两个根之间合并？ **Ответ** 因为 rank 或 size 描述的是整棵代表树，只有根持有有效的分量摘要。先 `find` 两个根，再把较矮或较小的根挂到另一根下，才能保持结构浅且摘要正确。 ### Карточка 128 **Вопрос** 哪类前缀最适合立即剪枝？ **Ответ** 已经违反且后续选择无法修复的约束前缀。例如约束具有单调恶化性质时，一旦越界，继续加选择也不可能恢复合法。 ### Карточка 129 **Вопрос** 从源点可达的边中出现负权时，为什么不能继续套用 Dijkstra？ **Ответ** 因为一个已弹出的顶点仍可能经负权边得到更短路径，破坏“最小 tentative distance 已确定”的不变量。无负环时可考虑 Bellman–Ford；若存在源点可达的负环，从该环还能到达的顶点没有有限最短距离。 ### Карточка 130 **Вопрос** 求最优值的回溯中，什么时候可以用上界或下界剪掉整个分支？ **Ответ** 当该分支即使达到可证明的最好界，也不可能优于当前最优解时。界必须对该分支剩余可能性有效；界越紧通常剪得越多，但不会改变最坏情况保证。 ### Карточка 131 **Вопрос** 为什么同一个 DAG 可能有多个合法 topological order？ **Ответ** 没有依赖关系强制先后的顶点可以交换位置。Kahn 过程中若某一步同时有多个入度 `0` 的选择，就存在多个合法顺序；每一步都只有一个选择时，顺序才唯一。 ### Карточка 132 **Вопрос** 同时使用路径压缩和按秩或大小合并时，union-find 操作的复杂度应怎样表述？ **Ответ** 完成 `O(n)` 初始化后，`m` 次 `find/union` 总时间是 `O(m α(n))`，所以单次是摊还 `O(α(n))`。`α(n)` 是增长极慢的反 Ackermann 函数，工程上近似常数，但不是严格 `O(1)`。 ### Карточка 133 **Вопрос** 搜索树每层最多 `b` 个候选、最大深度为 `d` 时，朴素回溯的规模怎样估算？ **Ответ** 节点上界是 `1+b+…+b^d`；当 `b>1` 时为 `O(b^d)`，当 `b=1` 时为 `O(d)`。若每个叶子还复制长度 `d` 的结果，要另计复制成本；实际分析优先使用真实访问状态数。 ### Карточка 134 **Вопрос** 逐条加入简单无向图的边时，union-find 怎样识别一条形成环的冗余边？ **Ответ** 加入 `{u, v}` 前若 `find(u) = find(v)`，两点已经连通，这条新边就闭合了一个环；否则执行 `union`。这个判定针对增量式无向图，不能直接套到有向图。 ### Карточка 135 **Вопрос** 当前和超过目标就停止向下搜索，需要什么前提？ **Ответ** 需要后续选择不会让和下降，例如所有可追加值都非负。若还允许负值，超过目标的前缀仍可能被拉回，直接剪枝会漏解。 ### Карточка 136 **Вопрос** union-find 能回答连通性，却不能直接回答哪些常见图问题？ **Ответ** 它不能恢复具体路径、计算最短距离或表达有向可达性，也不擅长普通在线删边。需要这些信息时，应保留图表示，并选择 BFS、DFS、最短路或更专门的动态结构。 ### Карточка 137 **Вопрос** 不计输出时，深度为 `d` 的原地回溯通常需要多少辅助空间？ **Ответ** 通常是 `O(d)` 调用栈，再加当前路径和约束状态所占空间。若每层复制完整状态，空间可能更高，不能只看递归深度。 ### Карточка 138 **Вопрос** 什么组合信号最值得考虑动态规划？ **Ответ** 问题可拆成重复出现的子问题，而且目标答案能由这些子问题答案组合出来。还需要能把每个子问题压成有限、可比较的 `state`；只有递归结构并不够。 ### Карточка 139 **Вопрос** 某状态下只有一个合法候选时，应怎样处理这一步？ **Ответ** 直接沿唯一候选继续即可。它仍属于搜索状态转换，但不会产生分支；提前识别 forced move 能减少通用候选循环的开销，也方便暴露无候选的失败状态。 ### Карточка 140 **Вопрос** 写 DP 前，`dp[...]` 的含义应该明确到什么程度？ **Ответ** 要明确每个索引代表的输入范围、资源或边界，以及值表示最大值、最小值、计数还是可行性。例如“处理前 `i` 个元素、容量为 `c` 时的最佳值”才足以推导 transition。 ### Карточка 141 **Вопрос** 约束搜索中，为什么常优先处理候选最少的未决变量？ **Ответ** 它更可能尽早暴露冲突，从而缩短失败分支。这是改变搜索顺序的启发式，不会单独证明更好的最坏复杂度，也不能删掉任何合法候选。 ### Карточка 142 **Вопрос** base case 在 DP 中除了终止递归，还承担什么作用？ **Ответ** 它定义最小子问题的真实答案，并为所有后续 transition 提供起点。错误的 base case 会系统性污染整张表，即使递推式本身正确。 ### Карточка 143 **Вопрос** 回溯中的 symmetry breaking 在删什么？ **Ответ** 它删除的是由对称选择产生、但代表同一个本质结果的等价分支。规则必须为每个等价类保留至少一个代表，否则会把真正不同的解一起删掉。 ### Карточка 144 **Вопрос** 怎样检查 DP state 是否足以代表子问题？ **Ответ** 若两个历史映射到同一 state，它们未来的合法选择和最优后续值必须相同。若未来还依赖被丢掉的历史信息，state 就不充分，需要增加维度或改变定义。 ### Карточка 145 **Вопрос** 一次选择后立即缩小其他变量的候选集合，为什么能加速回溯？ **Ответ** 这是约束传播：它把新确定的信息尽早传给后续状态，让矛盾更早出现。撤销选择时也必须恢复被缩小的候选集合，或使用不可变的新状态。 ### Карточка 146 **Вопрос** 为什么很多 DP 要显式定义空前缀、零容量或空区间？ **Ответ** 这些是 transition 会引用的合法最小状态。把它们作为哨兵行、哨兵列或长度为零的 base case，能让边界与普通递推保持同一语义。 ### Карточка 147 **Вопрос** 加入剪枝后，为什么不能直接宣称回溯从指数时间变成多项式时间？ **Ответ** 因为剪枝效果依赖输入和界的强弱；仍可能出现几乎没有分支可剪的输入。除非能证明所有输入的访问状态数都有多项式上界，否则最坏复杂度仍可能是指数级。 ### Карточка 148 **Вопрос** DP transition 应从哪里推导，而不是靠套模板？ **Ответ** 从最后一次选择或当前 state 的合法前驱推导。先覆盖所有合法来源，再用与目标一致的 `min`、`max`、求和或逻辑运算合并；计数时还要保证分类互斥。 ### Карточка 149 **Вопрос** 只改变候选尝试顺序，会影响回溯的正确性吗？ **Ответ** 完整枚举时不会，只要所有合法候选仍会被访问。寻找首个解或配合当前最优界时，好的顺序可能更早得到强基准，从而显著加快剪枝，但最坏情况未必改变。 ### Карточка 150 **Вопрос** tabulation 的迭代顺序由什么决定？ **Ответ** 由依赖方向决定：计算一个 state 前，它引用的所有前驱必须已经完成。先画出 transition 的依赖边，再选相应的索引、长度或拓扑顺序。 ### Карточка 151 **Вопрос** 枚举不允许重复节点的路径时，`visited` 为什么常要在回溯后撤销？ **Ответ** 因为约束通常是“当前路径内不能重复”，而不是“所有路径全局不能再用”。离开当前分支后撤销标记，其他独立路径才有机会使用该节点。 ### Карточка 152 **Вопрос** memoization 怎样消除递归中的重复子问题？ **Ответ** 第一次计算某个完整 state key 时保存结果，以后遇到同一 key 直接复用。它只访问从初始状态可达的子问题，但还会保留递归调用栈。 ### Карточка 153 **Вопрос** 什么时候可以给回溯加入 memo，而不把不同历史错误合并？ **Ответ** 当返回结果只由 memo key 表示的状态决定时。若合法后续还取决于未编码的路径历史，缓存会复用错误答案；若目标是逐条输出路径，也不能把聚合值缓存当成完整枚举。 ### Карточка 154 **Вопрос** tabulation 的核心做法是什么？ **Ответ** 按合法依赖顺序从 base case 向目标 state 填表。它不需要递归栈，通常布局紧凑，但可能计算一些从实际初始输入不可达的表项。 ### Карточка 155 **Вопрос** 什么时候把 `visited` 设为全局且不撤销会改变搜索语义？ **Ответ** 当同一状态可由不同路径到达，而目标需要区分或枚举这些路径时。全局标记会合并后来的到达；只有“每个状态处理一次”足以完成目标时才适合不撤销。 ### Карточка 156 **Вопрос** 状态空间稀疏且很多 state 不可达时，memoization 与 tabulation 通常怎样取舍？ **Ответ** memoization 常更自然，因为只计算可达 state；tabulation 可能扫完整稠密表。若递归深度危险、依赖顺序清晰或需要紧凑连续内存，tabulation 可能更合适。 ### Карточка 157 **Вопрос** 回溯状态应该每层复制，还是原地修改后撤销？ **Ответ** 两者都可以。复制更容易保持分支隔离但每层可能付出状态大小的时间和空间；原地修改更省复制成本，却要求每个变化都有严格对称的撤销。 ### Карточка 158 **Вопрос** DP 时间复杂度应怎样从 state 与 transition 推导？ **Ответ** 用 `可达或已填的 state 数 S × 每个 state 的 transition 成本 T`，即 `O(S·T)`。若不同 state 的出边数不同，更准确地把所有实际 transition 成本求和。 ### Карточка 159 **Вопрос** 当前没有合法候选，但结果还不完整时，这个回溯状态代表什么？ **Ответ** 它代表失败叶子，应直接返回且不收集结果。不要把“无法继续”与“已经完成”混成同一个终止条件。 ### Карточка 160 **Вопрос** 分析 top-down DP 的辅助空间时，要统计哪些部分？ **Ответ** 统计最多 `S` 个缓存 state、最大递归深度 `h` 的调用栈，以及每层或每个 state 保存的额外数据。因此常见口径是 `O(S + h)`，但大对象 key 或 parent 表还要另计。 ### Карточка 161 **Вопрос** 搜索树可能非常深时，递归回溯还有什么实现风险？ **Ответ** 调用栈可能超出运行时限制。可改用显式栈保存状态与下一候选位置，但仍要准确模拟进入、探索和撤销；这只改变栈的承载方式，不降低搜索规模。 ### Карточка 162 **Вопрос** 普通 DP recurrence 的依赖图有环时，为什么不能直接递归加 memo？ **Ответ** 因为某个 state 会在结果确定前再次依赖自己，memo 中还没有可复用的完成值。需要证明能消除环、改写 state，或使用适合循环依赖的其他算法，而不是把进行中的值当答案。 ### Карточка 163 **Вопрос** 什么信号说明朴素回溯很可能无法承受输入规模？ **Ответ** 分支因子大、深度高、约束弱，而且不存在可复用的紧凑子状态。此时访问状态可能接近完整决策树规模；应寻找更强剪枝、可合并的 DP 状态或问题特有结构。 ### Карточка 164 **Вопрос** 什么时候自然地把 1D DP state 定义为 `dp[i]`？ **Ответ** 当前答案只需描述前 `i` 个元素、长度 `i` 的前缀或位置 `i`，且未来不需要更多历史维度时。必须先说清 `i` 是数量还是索引，避免 base case 与返回位置错一位。 ### Карточка 165 **Вопрос** 什么题目信号值得考虑贪心，但还不足以证明贪心正确？ **Ответ** 解由一串可立即做出的局部选择组成，而且希望每步只保留一个方向。这个结构只提示候选方法；还必须证明当前选择不会排除某个全局最优解。 ### Карточка 166 **Вопрос** 网格型 DP 中，`dp[r][c]` 最常表示哪类子问题？ **Ответ** 表示到达格点 `(r,c)` 的答案，或以该格点为边界的矩形前缀答案。具体含义必须说明允许从哪些方向转移；坐标本身不能替代 transition 定义。 ### Карточка 167 **Вопрос** 贪心选择性质具体要说明什么？ **Ответ** 要说明存在一个最优解包含当前贪心选择。这样做出该选择后，剩余部分仍可作为同类子问题继续求解，而不是仅凭局部指标看起来最好。 ### Карточка 168 **Вопрос** 两个序列共同决定答案时，`dp[i][j]` 的自然语义是什么？ **Ответ** 通常表示第一个序列前 `i` 个元素与第二个序列前 `j` 个元素组成的子问题。比较当前末尾后，transition 可引用缩短一个或两个前缀的 state。 ### Карточка 169 **Вопрос** exchange argument 怎样证明第一步贪心选择是安全的？ **Ответ** 取一个最优解，把它与贪心选择冲突的部分换掉，并证明可行性不变且目标值不变差。于是至少有一个同样好的最优解以贪心选择开头。 ### Карточка 170 **Вопрос** 资源容量限制下的选择型 DP，常用哪两个维度定义 state？ **Ответ** 常用“已考虑的前 `i` 个候选”和“当前容量 `c`”。`dp[i][c]` 表示在这两项限制下的目标值，使“不选当前项”和“选择当前项”能引用明确前驱。 ### Карточка 171 **Вопрос** staying-ahead 证明比较的是什么？ **Ответ** 比较贪心解与任意最优解的每个等长前缀，证明贪心前缀在关键指标上始终不落后。最后一个前缀就是完整解，因此得到整体最优性。 ### Карточка 172 **Вопрос** 当答案由连续区间内部的拆分决定时，常用什么 DP state？ **Ответ** 使用 `dp[l][r]` 表示区间 `[l,r]` 的答案。transition 枚举合法分割点或最后合并位置，并组合更短的子区间。 ### Карточка 173 **Вопрос** 用归纳法证明贪心时，归纳步骤要连接哪两个事实？ **Ответ** 先证明当前选择属于某个最优解，再证明选完后的剩余实例仍满足同样结构。这样可对剩余实例重复应用贪心论证。 ### Карточка 174 **Вопрос** DAG 上的 DP 应按什么顺序处理节点？ **Ответ** 按与 transition 依赖方向一致的拓扑顺序。若 `u` 的答案用于更新 `v`，就先完成 `u`；反向定义 state 时则使用反向拓扑顺序。 ### Карточка 175 **Вопрос** 为什么只有 optimal substructure 不能推出贪心正确？ **Ответ** 因为它只说明最优解由最优子解组成，没有说明哪一个局部选择可安全固定。多个分支都可能通向不同子问题；若无法排除分支，通常仍需 DP 或搜索比较它们。 ### Карточка 176 **Вопрос** 计数型 DP 为什么常把前驱答案相加？ **Ответ** 因为每个前驱代表一组到达当前 state 的方案；当这些方案集合互不重叠且覆盖全部情况时，总数就是求和。若分类重叠，相加会重复计数。 ### Карточка 177 **Вопрос** exchange argument 只证明能交换第一处差异，为什么还不够？ **Ответ** 还要说明交换可反复进行，最终能把某个最优解转换成完整的贪心解。若后续交换会破坏前面保持的结构，证明链就没有闭合。 ### Карточка 178 **Вопрос** 1D recurrence 只依赖前 `k` 个 state 时，空间可怎样压缩？ **Ответ** 只保留长度 `k` 的滚动窗口，把空间从 `O(n)` 降到 `O(k)`；若 `k` 是常数，就是 `O(1)`。更新前要保存仍会被后续 transition 使用的旧值。 ### Карточка 179 **Вопрос** 怀疑某个贪心规则错误时，一个直接的快速检查是什么？ **Ответ** 构造一个最小反例，让局部最优选择占用未来关键资源，而另一项当前略差的选择得到更好总结果。一个合法反例就足以否定通用正确性。 ### Карточка 180 **Вопрос** 网格 DP 的第一行和第一列为什么经常需要单独初始化？ **Ответ** 它们缺少某些普通前驱，直接套通用 transition 会越界或读到假状态。可以单独初始化，也可加语义明确的哨兵边界；两种方法都要保持不可达位置不可被误用。 ### Карточка 181 **Вопрос** 贪心算法先排序时，排序依据应怎样论证？ **Ответ** 常见办法是证明把相邻逆序对换成该顺序不会破坏可行性或使目标变差，并能反复交换到目标顺序。若只能说这个 key “直觉上重要”，排序仍是未经证明的猜测。 ### Карточка 182 **Вопрос** 长度分别为 `n` 和 `m` 的双序列 DP，若每个 state 做 `O(1)` 工作，复杂度是多少？ **Ответ** 共有 `O(nm)` 个 state，因此时间为 `O(nm)`，完整表空间为 `O(nm)`。若只依赖有限相邻行，可按列数压缩；只有序列角色可交换时，才能进一步选短序列为列并写成 `O(min(n,m))`。 ### Карточка 183 **Вопрос** “每次拿当前收益最大项”为什么可能失败？ **Ответ** 当前最大收益可能消耗过多容量或阻塞多个稍小但合计更优的选择。除非能证明替换或支配关系，单步收益最大只是启发式。 ### Карточка 184 **Вопрос** “每个候选选或不选”的 DP transition 怎样组织？ **Ответ** 把当前 state 的答案合并为两类：不选时继承前一个候选层；可选时从扣除相应资源的合法前驱加上当前贡献。两类必须覆盖全部方案且不重复。 ### Карточка 185 **Вопрос** 排序后单次贪心扫描通常需要维护什么不变量？ **Ответ** 已处理前缀的选择必须始终可行，并且能扩展成某个该前缀下不劣的完整解。每次接受或拒绝候选都要保持这个性质。 ### Карточка 186 **Вопрос** bottom-up interval DP 为什么通常按区间长度递增填表？ **Ответ** 因为长区间的 transition 通常依赖更短子区间。先完成长度较小的 `[l,r]`，再扩展长度，能保证所有前驱已经有值。 ### Карточка 187 **Вопрос** 同一个最优化场景中，什么区别通常把贪心与 DP 分开？ **Ответ** 贪心能证明一个局部选择可永久固定；DP 则保留多个状态下的最佳结果，直到 transition 比较后再决定。无法证明安全丢弃其他选择时，更像 DP。 ### Карточка 188 **Вопрос** DAG DP 每条依赖边处理一次时，复杂度怎样计算？ **Ответ** 对 `V` 个 state 和 `E` 条 transition 边，拓扑排序加递推通常是 `O(V+E)` 时间；邻接表、入度和 DP 值共需 `O(V+E)` 空间。 ### Карточка 189 **Вопрос** 贪心指标相同时，tie-breaking 可以随便写吗？ **Ответ** 只有证明任一并列选择都安全时才可以。否则第二关键字可能影响可行性或未来选择；实现中应明确稳定、确定且符合证明的 tie-breaking。 ### Карточка 190 **Вопрос** 可行性 DP 的多个前驱通常怎样合并？ **Ответ** 用逻辑 OR：只要存在一个合法前驱能转移到当前 state，它就可达。初始化时必须区分真实可达的 base case 与默认的 `false`。 ### Карточка 191 **Вопрос** 按收益与成本比选择时，“资源可切分”为什么是重要边界？ **Ответ** 可切分时，剩余容量可用候选的一部分填补；不可切分时，一个高比率大项可能挡住组合起来更好的小项。比率规则能否精确求优必须按具体约束证明。 ### Карточка 192 **Вопрос** 把双序列 DP 压成一行时，为什么常需要保存左上角旧值？ **Ответ** 因为原 `dp[i-1][j-1]` 会在原地更新 `dp[j]` 时被覆盖。用临时变量保存更新前的左上角，才能同时读取上一行、当前行左侧和上一行左侧。 ### Карточка 193 **Вопрос** 贪心前的排序或去除被支配项，属于算法复杂度的一部分吗？ **Ответ** 属于。若 `n` 个候选先 comparison sort 再线性扫描，时间是 `O(n log n)`，不是 `O(n)`；排序辅助空间取决于具体实现。 ### Карточка 194 **Вопрос** 每个候选最多使用一次时，1D 容量 DP 为什么通常倒序更新 `c`？ **Ответ** 倒序保证读取的 `dp[c-cost]` 仍来自处理当前候选之前的旧层，因此当前候选不会在同一轮被重复使用。正序会读到本轮刚更新的值，改变问题语义。 ### Карточка 195 **Вопрос** 什么时候可以用 dominance rule 永久丢弃一个候选？ **Ответ** 当另一个候选在所有与未来有关的维度上都不差，并至少一项更好，而且替换后仍可行。只比较一个维度不足以建立支配关系。 ### Карточка 196 **Вопрос** 长度为 `n` 的 interval DP 若每个区间枚举 `O(n)` 个分割点，时间和表空间是多少？ **Ответ** 共有 `O(n²)` 个区间 state，每个最多做 `O(n)` 次 transition，所以时间为 `O(n³)`，完整表空间为 `O(n²)`。 ### Карточка 197 **Вопрос** 若候选已按证明所需顺序给出，贪心扫描何时是 `O(n)`？ **Ответ** 当 `n` 个候选各处理一次，且每次可行性更新和选择都是 `O(1)` 时，扫描为 `O(n)`。若更新依赖树、heap 或再次搜索，就要把相应成本计入。 ### Карточка 198 **Вопрос** 最小值或最大值 DP 中，不可达 state 应怎样初始化？ **Ответ** 用不会被误当成合法答案的 sentinel，例如最小化用 `+∞`、最大化用 `-∞`，并只从可达前驱转移。随手初始化为 `0` 可能凭空制造路径。 ### Карточка 199 **Вопрос** 选择不可撤销且非法前缀无法修复时，贪心每一步要检查什么？ **Ответ** 检查加入候选后前缀仍然可行。一旦接受非法选择，后续无法修复；检查所用的状态和约束必须与正确性证明一致。 ### Карточка 200 **Вопрос** 正成本候选允许重复使用时，1D 容量 DP 为什么常正序更新 `c`？ **Ответ** 正序让 `dp[c-cost]` 可以是本轮刚加入当前候选后的值，从而再次使用它。这个方向只适用于 transition 明确允许无限复用的语义；零成本候选要单独判断是否使目标无界。 ### Карточка 201 **Вопрос** 用大小最多为 `k` 的 heap 从 `n` 个候选中保留当前最佳集合，复杂度怎样计算？ **Ответ** 若每个候选至多触发常数次 heap 操作，时间为 `O(n log k)`，辅助空间为 `O(k)`。这只是实现成本；保留哪些候选仍需要独立的正确性证明。 ### Карточка 202 **Вопрос** 计数 DP 结果可能很大时，什么时候可以在每次 transition 后取模？ **Ответ** 只有题目要求返回某个模数下的结果，且后续运算与模运算兼容时。若需要精确计数、比较真实大小或恢复值，擅自取模会改变答案。 ### Карточка 203 **Вопрос** 一个离线贪心证明为什么不能自动用于在线到达的候选？ **Ответ** 离线算法可能依赖完整排序或未来信息，在线算法在做决定时看不到这些内容。若选择不可撤销，信息条件变化会破坏原来的安全选择论证。 ### Карточка 204 **Вопрос** 有 `n` 个候选、整数容量上限 `C` 的典型容量 DP，复杂度怎样表达？ **Ответ** 若每个 `(i,c)` state 做 `O(1)` transition，时间为 `O(nC)`；完整二维表空间为 `O(nC)`，可合法滚动时为 `O(C)`。这是 pseudo-polynomial：`C` 的数值可能远大于其编码长度。 ### Карточка 205 **Вопрос** 输入允许负收益或负成本时，为什么要重新检查原有贪心规则？ **Ответ** 因为许多单调性、排序和“加入不会变差”的论证默认量为非负。负值不必然使贪心失败，但它可能直接破坏证明依赖的前提。 ### Карточка 206 **Вопрос** DP 表只有最优值时，怎样恢复一条具体最优选择序列？ **Ответ** 为每个 state 记录产生最优值的 `parent` 或选择，最后从目标 state 反向追踪到 base case。若只需一条路径，并列最优时使用确定的 tie-breaking 即可。 ### Карточка 207 **Вопрос** 把“最小化”贪心规则反向排序，是否就能解决对应的“最大化”目标？ **Ответ** 不能直接推断。目标方向改变后，可行替换和前缀支配关系也可能改变；反向规则需要自己的安全选择证明或反例检查。 ### Карточка 208 **Вопрос** 1D DP 压缩后出现“同一个候选被意外重复使用”，最先检查什么？ **Ответ** 检查内层索引方向。原地数组同时承载上一层和当前层；错误方向会让 transition 读到本轮刚写入的值，从而改变“每项一次”或“可重复”的语义。 ### Карточка 209 **Вопрос** 为什么给一个已证明的贪心问题增加新约束后，必须重做证明？ **Ответ** 新约束可能让原来的交换不再可行，或让局部选择消耗此前不存在的资源。算法代码即使还能运行，也不代表最优性仍成立。 ### Карточка 210 **Вопрос** top-down DP 在小输入正确、复杂输入偶尔错误时，memo key 应检查什么？ **Ответ** 检查 key 是否包含所有会影响未来答案的状态变量。若不同剩余资源、边界或约束共享同一个 key，后计算的分支会错误复用先前结果。 ### Карточка 211 **Вопрос** 尚无最优性证明或可用定理依据的局部选择算法，应怎样准确描述？ **Ответ** 应暂时描述为启发式，而不是精确贪心解法。它可能在常见输入上表现好，但不能承诺总是得到全局最优结果。 ### Карточка 212 **Вопрос** 为什么 DP 能处理局部最优选择不安全的场景？ **Ответ** DP 不立即固定单一路径，而是为不同 state 保留各自的最佳答案，再通过 transition 比较。它用更多 state 和计算换取对多种未来可能性的保留。 ### Карточка 213 **Вопрос** 贪心算法不能保证精确最优时，还可能证明什么有用性质？ **Ответ** 可能证明 approximation bound，即结果与最优值之间的最坏比例或加性差距。这个界必须单独证明，不能由“用了贪心”自动得到。 ### Карточка 214 **Вопрос** memoized backtracking 在什么情况下本质上就是 top-down DP？ **Ответ** 当搜索返回的是可聚合的最优值、计数或可行性，而且未来只由紧凑 state key 决定时。若必须区分并输出每条历史路径，单纯合并同 state 就不等价。 ### Карточка 215 **Вопрос** 贪心只维护目标值时，怎样在最后返回具体选择？ **Ответ** 在接受候选时同步记录其标识或 parent 关系。若之后允许替换，就同时更新记录；只保存聚合值通常无法唯一恢复选择集合。 ### Карточка 216 **Вопрос** 什么时候可以安全压缩 DP 空间？ **Ответ** 当未来 transition 只依赖一个有限窗口内的旧 state，且更新顺序不会提前覆盖仍需读取的值。先列出依赖，再决定滚动维度；不能只因表很大就压缩。 --- *[Открыть оформленную HTML\-версию этой страницы]()* *ИИ-агенты могут создать аккаунт пользователя в этом сервисе, начиная с `GET https://api.nibomo.com/v1/`. После настройки они также могут подключиться по MCP по адресу `https://mcp.nibomo.com/mcp`.* *Совет: добавьте `.md` к любому URL на https://nibomo.com, чтобы получить чистую Markdown-версию страницы.*