算法面试模式闪卡：双指针、滑动窗口、图与动态规划

这套卡组中的卡片

1. 卡片 1

   问题

   按索引遍历长度为 n 的序列时，最基本的合法边界是什么？

   答案

   合法索引满足 0 <= i < n。 空序列的 n = 0，因此一次也不应访问；需要查看 i + 1 时，还要把条件收紧到 i + 1 < n。

2. 卡片 2

   问题

   只需反复判断某个值是否出现过，通常先考虑什么结构？

   答案

   先考虑 hash set。 它直接表达 membership；处理 n 个元素时通常用 O(n) 辅助空间，单次查询期望 O(1)。如果还要次数或位置，再改用 hash map。

3. 卡片 3

   问题

   什么处理顺序是使用 stack 的强信号？

   答案

   最新进入、最先处理的 LIFO 顺序。 当一个对象要等到后面的信息出现才结算，而且最近未结算对象必须先处理时，stack 往往最自然。

4. 卡片 4

   问题

   决定原地修改数组前，必须先确认哪项语义前提？

   答案

   必须确认允许改写输入，而且后续不再需要原始排列。 原地算法省辅助空间，但会破坏旧值或顺序；若调用方仍依赖原数据，就应复制或选用非破坏式方案。

5. 卡片 5

   问题

   题目需要持续知道每个值出现了多少次，应维护什么状态？

   答案

   维护 value -> count 的 hash map。 读到一个值就更新其计数；这样 membership 只是 count > 0 的特例，也能正确区分重复值。

6. 卡片 6

   问题

   需要按发现顺序处理待办对象时，通常用什么结构保存 frontier？

   答案

   用 FIFO queue。 先发现的对象先出队，新的对象从队尾加入，因此处理顺序稳定；如果改用 stack，顺序会变成深度优先式的后进先出。

7. 卡片 7

   问题

   许多查询都要重复使用某位置左侧或右侧的聚合结果时，先考虑什么预处理？

   答案

   先考虑 prefix 或 suffix 聚合。 一次 O(n) 预处理后，读取某个已保存的前缀或后缀结果是 O(1)；若查询任意中间区间，还要确认聚合能否用逆运算拆分，或改用别的结构。

8. 卡片 8

   问题

   既要按值快速查找，又要返回原始位置时，hash map 应保存什么？

   答案

   保存 value -> index，或在重复值有意义时保存 value -> indices。 不能默认一个值只有一个位置；覆盖旧索引是否正确，取决于需要任意位置、最近位置还是全部位置。

9. 卡片 9

   问题

   检查成对分隔符的嵌套是否合法时，stack 应保存什么？

   答案

   保存尚未匹配的 opening delimiter。 遇到 closing delimiter 时，它必须匹配栈顶；栈空却要关闭，或扫描结束后栈仍非空，都表示结构不合法。

10. 卡片 10

    问题

    什么时候不能为了简化扫描而直接排序输入？

    答案

    当原始顺序或原始索引属于答案语义时，不能直接排序。 Comparison sort 通常花 O(n log n) 时间并重排元素；若排序仍有价值，可把原索引与值一起保存，或改用不破坏顺序的状态结构。

11. 卡片 11

    问题

    既要去重又要保留首次出现顺序时，为什么不能只返回 hash set？

    答案

    因为普通 hash set 只表达唯一性，不保证还原首次出现顺序。 扫描原序列时用 set 判断是否见过，并把首次出现的值追加到结果，才能同时满足两项要求。

12. 卡片 12

    问题

    算法需要在两端都进行 O(1) 级别的插入或删除时，应优先考虑什么结构？

    答案

    优先考虑 deque。 queue 只暴露固定的入队端和出队端，stack 只操作一端；deque 明确支持两端操作。这里的 O(1) 指常见 deque 实现的摊还或最坏界，需以具体实现为准。

13. 卡片 13

    问题

    判断数组扫描复杂度时，比“代码有几层循环”更可靠的做法是什么？

    答案

    计算每个元素被访问的总次数。 若长度为 n 的序列中，每个元素只被常数次访问，且每次处理为 O(1)，总时间就是 O(n)；若对每个位置都重新扫描一个随 n 增长的范围，才可能达到 O(n²)。

14. 卡片 14

    问题

    如何准确表述 hash table 查找、插入和删除的复杂度？

    答案

    通常是期望或摊还 O(1)，最坏 O(n)。 结论依赖分布良好的 hash、受控装载因子和扩容策略；严重碰撞可让一次操作退化为线性扫描。保存最多 n 个键时，辅助空间为 O(n)。

15. 卡片 15

    问题

    哪类“最近一个更大或更小元素”查询常提示 monotonic stack？

    答案

    当元素按顺序到达，并要找最近的支配元素时，考虑 monotonic stack。 栈中只保留仍可能成为答案的候选；新元素会淘汰已不可能再被选中的栈顶。

16. 卡片 16

    问题

    什么输入特征会让相向双指针成为候选模式？

    答案

    有序序列加上可单调判断的关系，是强信号。 当当前结果偏小只可能通过移动 left 改善、偏大只可能通过移动 right 改善时，每一步才能安全排除一批候选。

17. 卡片 17

    问题

    根节点和 left、right 引用如何表示一棵二叉树？

    答案

    从根节点沿 left、right 引用可到达全部节点。每个引用表示一条父到子的边；树结构还要求无环，并且除根外每个节点恰有一个父节点。

18. 卡片 18

    问题

    要比较所有长度恰好为 k 的连续片段时，应怎样避免每次重算？

    答案

    维护固定长度 sliding window。 窗口右移一格时加入新元素、移除离开的元素，便可复用上一窗口的 state；若更新各为 O(1)，扫描长度 n 的序列总计 O(n)。

19. 卡片 19

    问题

    递归 DFS 遍历树时，每次调用最自然的子问题是什么？

    答案

    以当前节点为根的整棵子树。调用处理当前节点，并从左右子树拿回结果；这让递归参数和返回值都围绕一个明确的子树定义。

20. 卡片 20

    问题

    使用半开区间写 binary search 时，循环不变量应怎样表述？

    答案

    候选区间始终是 [left, right)。 初始化通常为 left = 0, right = n，循环条件是 left < right；每次更新必须严格缩短这个区间，空输入自然得到 [0, 0)。

21. 卡片 21

    问题

    树的 BFS 怎样准确分隔当前层与下一层？

    答案

    处理一层前先记录当前队列长度 levelSize，只弹出这 levelSize 个节点。处理期间新入队的孩子自然属于下一层。

22. 卡片 22

    问题

    链表操作会频繁改动头节点时，sentinel 能消除哪类分支？

    答案

    它把“头节点前面没有 predecessor”这个特例变成普通情况。 让 sentinel.next 指向真实头节点后，删除、插入和合并都可统一通过前驱重连，最后返回 sentinel.next。

23. 卡片 23

    问题

    需要先处理父节点，再处理它的子树时，应选哪种遍历顺序？

    答案

    前序遍历：先当前节点，再左子树，最后右子树。它适合把父节点状态传给后代，或在进入子树前完成处理。

24. 卡片 24

    问题

    处理区间前，为什么必须先确定闭区间还是半开区间？

    答案

    因为端点相等时是否重叠取决于区间约定。 闭区间 [a, b] 与 [b, c] 共享 b；半开区间 [a, b) 与 [b, c) 不重叠。排序、合并和事件 tie-break 都必须沿用同一约定。

25. 卡片 25

    问题

    含 m 个元素的 binary heap 中，读取 top、push 和 pop 各是什么复杂度？

    答案

    读取 top 是 O(1)；push 和弹出 top 都是 O(log m)。后两者最多沿堆高调整一次，binary heap 的高度是 O(log m)。

26. 卡片 26

    问题

    相向双指针每次移动一端时，必须证明什么？

    答案

    必须证明被越过的候选不可能优于或满足答案。 这个 discard invariant 通常来自排序与单调关系；若无法证明，移动指针只是猜测，可能漏掉有效组合。

27. 卡片 27

    问题

    当前节点的答案依赖左右子树结果时，应优先想到哪种遍历顺序？

    答案

    后序遍历：先求左右子树，再处理当前节点。高度、子树大小和子树聚合都符合“孩子先完成，父节点再合并”的结构。

28. 卡片 28

    问题

    可变 sliding window 能靠移动 left 修复违规状态，需要什么前提？

    答案

    可行性必须对窗口收缩呈单调变化。 固定 right 后，移除左端元素应当只朝“更可行”的方向走；若收缩可能反复让状态变好又变坏，就不能用单向 left 安全排除候选。

29. 卡片 29

    问题

    为什么把 m 个已有元素自底向上建成 binary heap 是 O(m)，而不是 O(m log m)？

    答案

    因为自底向上的 heapify 只让少量靠近根的节点下沉较远，大多数节点移动很短或不移动；按高度汇总工作量是 O(m)。逐个 push 才是 O(m log m)。

30. 卡片 30

    问题

    怎样把“找第一个满足条件的位置”写成稳定的 binary search 目标？

    答案

    在 P(i) 从 false 单调变为 true 的前提下，搜索最小的 true 位置。 当 P(mid) 为真时保留 mid 并收紧右界，否则排除 mid 及其左侧；结束后还要检查返回位置是否在范围内且确实满足条件。

31. 卡片 31

    问题

    二叉树的中序遍历在什么前提下会得到非降序序列？

    答案

    这棵树必须满足 BST 的全局顺序约束，并采用一致的重复值策略。中序按左子树、当前节点、右子树访问；普通二叉树没有有序保证。

32. 卡片 32

    问题

    迭代反转单链表时，prev 与 current 应保持什么不变量？

    答案

    prev 始终是已反转前缀的头，current 是尚未处理后缀的头。 改写 current.next 前先保存原来的 next，再依次推进 prev 和 current，才不会丢失后缀。

33. 卡片 33

    问题

    递归处理空子树时，base case 应返回什么？

    答案

    返回当前子问题的中性结果，而不是随手写一个固定值。例如计数返回 0，高度按所选定义返回 0 或 -1，布尔验证常返回 true。定义必须与合并公式一致。

34. 卡片 34

    问题

    两个半开区间 [a, b) 与 [c, d) 的重叠条件是什么？

    答案

    重叠当且仅当 max(a, c) < min(b, d)。 严格小于体现了半开语义：b = c 只是首尾相接，不共享任何点。若改成闭区间，相应比较通常要允许端点相等。

35. 卡片 35

    问题

    扫描 n 个元素并保留最大的 k 个时，小根堆应维持什么不变量？

    答案

    堆中始终是当前见过元素里最大的至多 k 个，堆顶是候选里的最小门槛。假设 1 ≤ k ≤ n；堆未满时直接加入，满后只用更大值替换 top。时间 O(n log k)，辅助空间 O(k)。

36. 卡片 36

    问题

    原地筛选或压缩数组时，read/write pointers 的核心不变量是什么？

    答案

    [0, write) 始终是已经确定的输出前缀，read 扫描尚未处理的输入。 每遇到应保留的元素，就写到 write 并递增；前提是允许覆盖已读区域。

37. 卡片 37

    问题

    访问一棵含 n 个节点、高度为 h 的树一次，递归遍历的时间和辅助空间是多少？

    答案

    时间通常是 O(n)，递归辅助空间是 O(h)。每个节点只处理常数次；调用栈只保存当前根到节点的路径。输出本身占用的空间应另计。

38. 卡片 38

    问题

    sliding window 的计数或总和状态必须始终对应什么范围？

    答案

    必须精确对应当前窗口 [left, right] 或 [left, right)，二者选定一种。 扩张时先加入新元素，收缩时移除离开元素；边界约定和更新顺序不一致会产生 off-by-one。

39. 卡片 39

    问题

    数据逐个到达、总长度未知，但只需随时保留最大的 k 个值，应选什么结构？

    答案

    选容量为 k 的小根堆，并假设 k ≥ 1。它不需要保存完整数据流；每个输入最坏做一次 O(log k) 的堆更新，辅助空间保持 O(k)。

40. 卡片 40

    问题

    “最后一个满足条件的位置”怎样借助边界 binary search 表达？

    答案

    在 predicate 从 true 单调变为 false 时，先找第一个 false，再取其前一个位置。 这把右边界问题转成统一的左边界模板；返回前必须检查前一个位置存在，并确实属于有效范围。

41. 卡片 41

    问题

    用栈实现“根、左、右”的迭代 DFS 时，孩子应按什么顺序入栈？

    答案

    先压入右孩子，再压入左孩子。栈是 LIFO，左孩子因此先弹出；若反过来入栈，实际访问顺序会变成“根、右、左”。

42. 卡片 42

    问题

    为什么“单链表删除是 O(1)”必须附带节点定位前提？

    答案

    只有待改写的 predecessor 已知时，局部重连才是 O(1)。 若先要从头找到第 k 个节点、目标值或其前驱，定位本身是 O(n)；不能把查找成本藏在删除操作之外。

43. 卡片 43

    问题

    合并 k 个各自非降序、总计 N 个元素的序列时，堆里应保存什么？

    答案

    保存每个尚未耗尽序列的当前头部候选。每次弹出全局最小值，再把同一序列的下一个值入堆；时间 O(N log k)，辅助空间 O(k)。

44. 卡片 44

    问题

    按起点排序后合并区间时，应保持什么扫描不变量？

    答案

    结果中已完成区间互不重叠，最后一个区间代表当前可扩展的 union。 新区间若按既定端点语义与它重叠，就更新终点；否则追加为下一段。按起点排序保证后续起点不会倒退。

45. 卡片 45

    问题

    树的 BFS 为什么不能笼统地说只占 O(h) 辅助空间？

    答案

    因为队列保存的是一段横向 frontier，空间由最大层宽 w 决定，即 O(w)，最坏可达 O(n)。h 描述的是高度，更直接对应 DFS 路径栈。

46. 卡片 46

    问题

    判断一个序列能否按顺序匹配到另一个序列中时，双指针如何分工？

    答案

    一个指针指向下一个待匹配元素，另一个只向前扫描候选序列。 匹配成功才推进前者；不变量是前者之前的元素已按顺序匹配，扫描过的位置无需回看。

47. 卡片 47

    问题

    只保留 k 个候选时，第 k 大与第 k 小分别该用哪一侧的堆？

    答案

    假设 1 ≤ k ≤ n：第 k 大用容量 k 的小根堆；第 k 小用容量 k 的大根堆。堆顶始终是当前候选集合里最容易被淘汰的边界值。

48. 卡片 48

    问题

    求最长可行窗口与最短可行窗口时，收缩时机有什么区别？

    答案

    最长问题通常在窗口违规时收缩；最短问题通常在窗口仍可行时持续收缩并更新答案。 两者都依赖单调可行性，但优化目标决定何时记录候选。

49. 卡片 49

    问题

    含 n 个节点的树做递归 DFS 时，调用栈何时是 O(log n)，何时会退化为 O(n)？

    答案

    只有树高 h = O(log n)，例如树明确平衡时，调用栈才是 O(log n)；链状或严重偏斜的树有 h = O(n)，调用栈也会达到 O(n)。

50. 卡片 50

    问题

    没有显式有序数组时，什么条件仍允许在 answer space 上二分？

    答案

    候选答案必须有序，而且可行性 predicate 在某个边界只改变一次真假。 每次检查 mid 后，predicate 要能证明一整侧都可排除；检查本身不必是 O(1)。

51. 卡片 51

    问题

    什么时候直接排序通常比维护 top-k 堆更合适？

    答案

    需要完整有序结果，或 k 与 n 同量级时，排序通常更简单。comparison sort 用 O(n log n) 时间；容量 k 的堆适合只取少量候选，用 O(n log k) 时间和 O(k) 辅助空间。

52. 卡片 52

    问题

    要在一次遍历中找到单链表中点，fast/slow pointers 应怎样移动？

    答案

    slow 每次走一步，fast 每次走两步。 当 fast 到达末尾时，slow 约走了链长的一半；偶数长度时返回两个中点中的哪一个，取决于循环条件，必须事先约定。

53. 卡片 53

    问题

    沿一个孩子方向查找 BST 的做法依赖什么前提，复杂度怎样写？

    答案

    前提是整棵树满足约定的 BST 顺序。查找时间是 O(h)；只有明确平衡时才是 O(log n)，任意 BST 在偏斜时最坏为 O(n)。

54. 卡片 54

    问题

    要计算任一时刻同时活跃的区间数，扫描线维护什么量？

    答案

    维护当前 active count，并记录其最大值。 按时间处理开始与结束事件：开始时加一，结束时减一；端点相同时谁先处理，必须由闭区间或半开区间语义决定。

55. 卡片 55

    问题

    为什么 binary heap 不适合查找一个任意给定值？

    答案

    堆只保证父子之间的偏序，不保证左右子树内部有序。除 top 外，一个值可能出现在许多位置，因此查找任意值最坏仍要扫描 O(m) 个元素。

56. 卡片 56

    问题

    双指针代码含嵌套 while 时，何时总时间仍是 O(n)？

    答案

    当每个指针都只单向移动，且各自总共最多跨过 n 个位置时。 内层循环的所有迭代可以按指针移动次数合计，因此是 O(n + n) = O(n)，不是逐次相乘。

57. 卡片 57

    问题

    在 BST 中只关心闭区间 [L, R] 内的值时，何时可剪掉整侧子树？

    答案

    当前值小于 L 时可跳过左子树；当前值大于 R 时可跳过右子树。这个剪枝依赖有效 BST 的全局顺序和已明确的闭区间语义。

58. 卡片 58

    问题

    窗口允许重复值且要精确移除左端元素时，为什么 set 往往不够？

    答案

    因为 set 不记录同一值在窗口中还有几份。 应维护 frequency map；元素离开时减一，只有计数降到零才删除键，这样窗口 state 才不会过早宣告该值消失。

59. 卡片 59

    问题

    堆中旧条目无法高效定位删除时，lazy deletion 怎样保持 top 正确？

    答案

    另存最新状态或有效标记；每次读取 top 前，持续弹出已失效条目。每次弹出是 O(log m)，但每个旧条目最多清理一次，所以总清理成本可摊还；堆仍可能暂时保存所有未清理条目。

60. 卡片 60

    问题

    如果 predicate 随候选值反复在 true 与 false 之间切换，为什么不能 binary search？

    答案

    因为一次判断无法安全排除完整的一侧。 Binary search 需要真假区间只有一个分界；predicate 非单调时，mid 的结果不能说明左侧或右侧全部无效。

61. 卡片 61

    问题

    为什么只比较 BST 节点与它的直接孩子不足以验证整棵树？

    答案

    因为更深的后代也必须满足所有祖先带来的范围限制。递归时应传递允许的下界和上界，并按既定重复值策略决定边界是严格还是可包含。

62. 卡片 62

    问题

    为什么一快一慢两个指针能用 O(1) 辅助空间检测链表中的环？

    答案

    进入环后，fast 每轮相对 slow 多前进一步，因此最终会追上它。 若 fast 先到达 null，链表无环；整个过程最多线性步数，所以时间 O(n)、辅助空间 O(1)。

63. 卡片 63

    问题

    用双堆维护数据流中位数时，需要维持哪两个不变量？

    答案

    小值半区用大根堆、大值半区用小根堆；两边大小最多相差 1，且前者所有值不大于后者所有值。插入是 O(log n)，读中位数是 O(1)，空间是 O(n)。

64. 卡片 64

    问题

    半开区间 [start, end) 的扫描线中，同一时刻的结束和开始事件谁先处理？

    答案

    先处理结束，再处理开始。 因为在半开语义下，旧区间在 end 已不活跃，新区间可从同一时刻开始；反过来会把本不重叠的两段短暂计为同时活跃。

65. 卡片 65

    问题

    BST 允许重复值时，为什么必须先约定重复值放在哪一侧？

    答案

    因为搜索、插入、验证和中序有序性的边界都依赖同一约定。例如“左侧严格小于、右侧大于等于”与“两侧都严格”不是同一个数据结构契约。

66. 卡片 66

    问题

    无序序列上的关系不随指针移动单调变化时，为什么不应硬套相向双指针？

    答案

    因为移动任一端都无法证明被跳过的组合无效。 若排序不破坏答案语义，可以先排序建立单调性；否则应考虑 hash 状态、完整搜索或别的能保留候选的方法。

67. 卡片 67

    问题

    每个节点都要汇总其整棵子树的信息时，递归函数应返回什么？

    答案

    返回父节点合并时真正需要的子树摘要，例如大小、高度或最佳向下值。这样每个节点只合并一次，通常是 O(n) 时间和 O(h) 调用栈。

68. 卡片 68

    问题

    窗口收缩到空时，哪些 state 必须同步恢复？

    答案

    所有只描述窗口内容的 state 都必须回到空状态。 计数、总和、distinct 数和 deque 都不能残留已移除元素；同时边界应满足所选约定，例如半开窗口 [left, right) 在 left = right 时为空。

69. 卡片 69

    问题

    DFS 共用一个可变 path 记录当前根到节点路径时，离开节点前必须做什么？

    答案

    必须撤销本层加入的节点，也就是 pop。不回退会让一个分支的节点泄漏到兄弟分支；进入时 push、退出时 pop 正好维持“path 等于当前递归路径”的不变量。

70. 卡片 70

    问题

    长度为 n 的候选区间每轮至少减半时，迭代和递归 binary search 的复杂度分别是什么？

    答案

    两者时间都是 O(log n)；迭代辅助空间 O(1)，递归调用栈 O(log n)。 前提是每轮检查与边界更新为 O(1)；若每次 predicate 检查的上界为 C(n)，总时间上界是 O(C(n) log n)。

71. 卡片 71

    问题

    树中经过当前节点的最长简单路径，为什么要组合两个孩子方向的贡献？

    答案

    因为这条路径可从一个子树上来，再进入另一个子树，所以要组合两个最大的向下长度；但返回给父节点时只能选其中一个方向。节点数或边数的口径要从 base case 到公式保持一致。

72. 卡片 72

    问题

    快慢指针在环内相遇后，怎样找到环的入口？

    答案

    把一个指针移回头节点，再让两个指针每次各走一步；下一次相遇点就是环入口。 这个结论来自相遇时走过距离的整圈关系，不需要额外 set，整体时间 O(n)、辅助空间 O(1)。

73. 卡片 73

    问题

    树 DFS 把答案放在跨调用复用的全局变量里，最常见的正确性风险是什么？

    答案

    旧结果会污染新的遍历，兄弟分支也可能意外共享不该共享的状态。优先让递归返回子树结果；确需共享聚合量时，把它限制在单次调用范围并明确初始化。

74. 卡片 74

    问题

    先按端点排序、再线性扫描 n 个区间时，整体复杂度应怎样写？

    答案

    时间是 O(n log n)，由 comparison sort 主导；扫描是 O(n)。 辅助空间取决于排序实现，不能一概写成 O(1)；若把返回结果也计入总空间，最多 n 个新区间另占 O(n)。

75. 卡片 75

    问题

    怎样在一次后序遍历中同时计算树高并发现不平衡子树？

    答案

    让递归返回高度或一个“不平衡” sentinel。任一孩子已不平衡，或左右高度差超过允许值，就继续向上传 sentinel；否则返回当前高度。这样是 O(n)，避免反复计算高度导致最坏 O(n²)。

76. 卡片 76

    问题

    monotonic stack 为什么常能在线性时间内完成整次扫描？

    答案

    每个元素最多入栈一次、出栈一次。 虽然某一步可能连续弹出很多元素，但对 n 个元素合计只有 O(n) 次 push/pop；栈最多保存 n 个候选，辅助空间 O(n)。

77. 卡片 77

    问题

    看到“树上的路径”时，写算法前最先要澄清什么？

    答案

    先澄清端点范围：根到叶、根到任意节点，还是任意节点到任意节点。还要确认长度按边还是按节点计；这些定义会直接改变 base case 和合并方式。

78. 卡片 78

    问题

    可变 sliding window 有内层收缩循环时，何时总时间是 O(n)？

    答案

    当 right 与 left 都只向前，且各自最多移动 n 次时。 对长度 n 的序列，所有扩张与收缩合计 O(n)；辅助空间等于窗口 state，可从 O(1) 到最多 O(n)。

79. 卡片 79

    问题

    即使递归 DFS 的渐进空间是正确的，什么树形仍可能让实现栈溢出？

    答案

    高度接近 n 的链状或严重偏斜树。它需要 O(n) 层调用；输入深度可能超过运行时栈限制时，应改用显式栈或确认环境能承受该深度。

80. 卡片 80

    问题

    整数 binary search 中，怎样计算 mid 更不容易溢出？

    答案

    使用 mid = left + (right - left) / 2 的整数取整形式。 它避免先计算可能溢出的 left + right；向下还是向上取整要与边界更新配套，确保候选区间每轮严格缩小。

81. 卡片 81

    问题

    普通根树中，后序 DFS 如何识别两个不同且已知存在节点的最低共同祖先？

    答案

    找最深的汇合点：当前节点自身和各子树返回的命中信号中，只要有两路覆盖两个目标，当前节点就是最低共同祖先。若目标不保证都存在，还必须另行确认两者确实被找到。

82. 卡片 82

    问题

    合并两个已按同一规则排序的链表时，tail 应保持什么不变量？

    答案

    tail 始终指向已合并有序前缀的最后节点。 每次比较两个当前节点，把较小者接到 tail.next 并推进对应指针；一条链耗尽后，剩余有序后缀可以整体接上。

83. 卡片 83

    问题

    二叉树里什么才算叶节点？空树和单节点树分别怎样判断？

    答案

    叶节点是自身存在且 left、right 都为空的节点。空树没有叶节点；单节点树的根同时也是叶节点。不能把空引用本身当成叶节点。

84. 卡片 84

    问题

    用两个 stack 实现 queue 时，怎样得到摊还 O(1) 的出队？

    答案

    入队压入 in；只有 out 为空时，才把 in 全部倒入 out。 每个元素最多被压入和弹出常数次，所以一串 m 次操作总计 O(m)；单次搬运仍可能是 O(n)。

85. 卡片 85

    问题

    树题中，什么信号更偏向 BFS，什么信号更偏向 DFS？

    答案

    逐层、离根最近或最少边数更偏向 BFS；子树聚合、根到节点状态和回溯路径更偏向 DFS。两者通常都能遍历全树，选择依据是需要的访问顺序与状态形状。

86. 卡片 86

    问题

    含 V 个顶点、E 条边的稀疏图，通常应选哪种邻接表示？

    答案

    通常选 adjacency list。它占 O(V+E) 空间，并能只遍历真实存在的邻边；实现时也要为孤立顶点保留空邻接表或等价记录。

87. 卡片 87

    问题

    需要列举一连串选择形成的所有可行结果时，应先把搜索过程看成什么结构？

    答案

    决策树。每一层表示一次选择，每条边表示一个候选动作，叶子或满足终止条件的节点表示完整结果；这正是回溯适用的基本信号。

88. 卡片 88

    问题

    adjacency list 中，有向边与无向边应怎样记录？

    答案

    有向边 u → v 只把 v 放进 u 的邻接表；无向边 {u, v} 通常同时记录 u → v 和 v → u。若 E 按逻辑无向边计数，存两次仍是 O(V+E) 空间。

89. 卡片 89

    问题

    回溯中 choose → explore → unchoose 的核心不变量是什么？

    答案

    每次递归返回后，共享状态必须恢复到选择前的样子。这样下一个候选分支看到的是同一个父状态，而不是被前一分支污染的状态。

90. 卡片 90

    问题

    图的 BFS 为什么通常要在入队时标记 visited，而不是出队时？

    答案

    入队时标记可保证每个顶点只进入队列一次。若等到出队，同一顶点可能被多个前驱重复入队，放大时间和空间；无权图中，首次发现时的距离也已是最短距离。

91. 卡片 91

    问题

    为什么删除单链表中的当前节点通常需要它的 predecessor？

    答案

    因为要把 predecessor.next 改为 current.next。 单链表没有反向链接；若只拿到当前节点，通用删除无法更新前一条边，尾节点尤其不能靠复制后继值处理。

92. 卡片 92

    问题

    什么时候 adjacency matrix 比 adjacency list 更合适？

    答案

    图很稠密，或需要频繁 O(1) 判断任意两点是否有边时，matrix 更合适。代价是 O(V²) 空间，枚举一个顶点的全部邻居也要扫描 O(V) 个位置。

93. 卡片 93

    问题

    怎样判断回溯递归参数是否记录了足够但不过量的状态？

    答案

    状态应恰好决定“接下来还能选什么”和“何时得到结果”。能由现有参数推导的信息不必重复存；缺少会影响合法候选的信息，则会让不同子问题被错误混在一起。

94. 卡片 94

    问题

    图的 DFS 为什么不能像树遍历那样只递归所有邻居？

    答案

    图可能有环，也可能有多条路径到同一顶点，所以必须记录访问状态，避免无限递归和重复处理。仅有一个 visited 集合足够做普通可达性遍历，但某些环检测还需要更细状态。

95. 卡片 95

    问题

    回溯的终止条件需要同时保证哪两件事？

    答案

    保证正确收集完整解，并阻止搜索越过有效深度。条件太早会漏解，太晚会访问无意义或越界状态；应直接对应“一个候选解已经完整”的定义。

96. 卡片 96

    问题

    无权图中，求源点到各点的最少边数应选什么算法？

    答案

    选 BFS。它按距离层扩展，第一次发现顶点时就得到最少边数；用 adjacency list 时，时间 O(V+E)，队列和访问状态占 O(V)。

97. 卡片 97

    问题

    用 monotonic deque 维护窗口最大值时，deque 中应保留什么？

    答案

    按值单调递减排列、且仍在窗口内的候选索引。 新元素进入时从队尾删掉不大于它的旧候选，窗口左移时从队首删掉过期索引；队首因此始终是当前最大值的位置。

98. 卡片 98

    问题

    用 adjacency list 完整遍历图时，BFS 或 DFS 的复杂度怎样写？

    答案

    时间是 O(V+E)，辅助状态通常是 O(V)，不含图本身。完整遍历要从每个未访问顶点启动一次；无向边虽在邻接表出现两次，不改变渐进复杂度。

99. 卡片 99

    问题

    回溯里的 path 与控制搜索的状态有什么区别？

    答案

    path 保存当前已选内容；控制状态决定下一步候选，例如位置、剩余额度或已用集合。两者可能重叠，但不能因为 path 可展示结果，就假定它包含全部搜索约束。

100. 卡片 100

     问题

     怎样用一次总体线性的遍历统计无向图的连通分量？

     答案

     依次检查所有顶点；每遇到一个未访问顶点，就从它启动一次 BFS 或 DFS，并把分量数加一。用 adjacency list 时，每个顶点和边总共只处理常数次，时间 O(V+E)。

101. 卡片 101

     问题

     设计回溯时，“生成候选”这一步应回答什么问题？

     答案

     它应列出从当前状态出发所有且仅有的合法下一步。漏掉候选会破坏完备性，加入非法候选则需要额外检查并扩大搜索树。

102. 卡片 102

     问题

     同一个图改用 adjacency matrix 后，完整 BFS 或 DFS 为什么通常变成 O(V²)？

     答案

     因为每访问一个顶点，都要扫描长度为 V 的整行来找邻居；最多扫描 V 行，所以是 O(V²)，即使实际边很少也是如此。matrix 本身也占 O(V²) 空间。

103. 卡片 103

     问题

     改写单链表的 current.next 前，最常见的防丢链动作是什么？

     答案

     先把原来的 current.next 保存到临时变量。 一旦覆盖这条链接，又没有其他引用指向后缀，后续节点就无法继续访问；重连顺序应明确每一步仍能到达未处理部分。

104. 卡片 104

     问题

     用 DFS 检测有向图环时，为什么需要 white/gray/black 三种状态？

     答案

     gray 表示顶点仍在当前递归路径上，遇到指向 gray 的边就说明有环；black 表示该顶点已完整处理。单一 visited 无法区分“当前路径上的祖先”和“其他已完成分支”。

105. 卡片 105

     问题

     把当前 path 加入结果集时，为什么通常要保存副本？

     答案

     因为 path 往往是后续会继续修改的可变容器。若只保存同一个引用，回溯撤销和后续选择会改掉已经收集的结果。

106. 卡片 106

     问题

     无权图 BFS 能保证最短距离的核心队列不变量是什么？

     答案

     队列按从小到大的距离层处理顶点。距离为 d 的顶点只会发现尚未访问、距离为 d+1 的邻居，因此一个顶点首次被发现时，不可能还存在更短的未处理路径。

107. 卡片 107

     问题

     只需生成无顺序的选择组合时，递归参数常用什么来避免反向重复？

     答案

     使用单调前进的 start 索引。下一层只从当前索引之后选择，使同一组元素只按一种顺序生成，而不是再生成顺序相反的副本。

108. 卡片 108

     问题

     简单无向图中，DFS 遇到已访问邻居时，怎样区分父边与环？

     答案

     把进入当前顶点的 parent 一并传入；已访问邻居若不是 parent，就存在环。这个判断假设没有平行边；多重图要追踪边 ID，不能只比较父顶点。

     

     216张卡片

     算法面试模式闪卡：双指针、滑动窗口、图与动态规划

     免费学习这套卡组

     Flashcards 将打开，你可以立即开始学习。

109. 卡片 109

     问题

     monotonic deque 扫描 n 个元素时，为什么总维护成本是 O(n)？

     答案

     每个索引最多从队尾加入一次，并从队首或队尾删除一次。 某一步虽可能连续删除多个索引，整次扫描的 deque 操作总数仍为 O(n)；最坏辅助空间为 O(n)。

110. 卡片 110

     问题

     为什么普通 DFS 不能保证找到无权图中的最短路径？

     答案

     DFS 会先沿一个分支走深，第一次到达目标的路径可能很长。无权最短路应使用按层扩展的 BFS；只有树中两点路径唯一等特殊结构，遍历顺序才不影响那条路径本身。

111. 卡片 111

     问题

     一个剪枝条件要正确，必须证明什么？

     答案

     必须证明被剪掉的前缀不可能扩展成任何所需解。剪枝只是减少访问状态，不能靠“通常没有希望”来牺牲完备性。

112. 卡片 112

     问题

     题目要求所有依赖都先于依赖者出现时，应想到什么图模型与算法？

     答案

     建有向依赖图并求 topological order。只有 DAG 才存在这种顺序；若图中有向环存在，就不可能同时满足所有先后约束。

113. 卡片 113

     问题

     每个位置都可从尚未使用的元素中选择时，状态通常要增加什么？

     答案

     增加 used 集合或布尔数组。它记录当前路径已经占用的元素，使每层都能从全部未用元素中选择；这适合顺序会产生不同结果的排列型状态。

114. 卡片 114

     问题

     无权图中要计算每个顶点到最近源点的距离，多个源点应怎样启动 BFS？

     答案

     把所有源点都以距离 0 同时入队，再做一次 BFS。它们共同形成第 0 层，后续首次发现距离就是到任一源点的最短距离；adjacency list 上仍是 O(V+E)。

115. 卡片 115

     问题

     算法频繁按第 k 个位置访问元素时，为什么单链表通常不是合适选择？

     答案

     因为单链表没有随机访问，第 k 个位置需要从头走 O(k)。 数组可按索引 O(1) 访问；链表的优势是已知位置附近的重连，不是按下标查找。

116. 卡片 116

     问题

     边不断加入，只需回答“两点现在是否连通”时，应优先想到什么结构？

     答案

     优先想到 union-find。每条新边用 union 合并分量，查询时比较两个点的 find 结果；它适合增量式无向连通，不负责恢复具体路径。

117. 卡片 117

     问题

     找到一个可行解后能否立即返回，取决于什么？

     答案

     取决于目标是“任意一个解”还是“全部解／最优解”。前者可短路；后者仍需探索其他可能分支，除非已有正确的最优性界。

118. 卡片 118

     问题

     带权图的边权满足什么条件时，可以用 Dijkstra 求单源最短路？

     答案

     所有可达边的权重都必须非负。Dijkstra 每次确定当前 tentative distance 最小的未确定顶点；非负权保证以后经过更远顶点不可能把它改得更小。

119. 卡片 119

     问题

     输入含重复值且结果按值去重时，怎样跳过同一层的重复分支？

     答案

     可为每层维护 seen；若排序不改变题意，也可先让相同值相邻，再跳过同层的等值候选。只跳同层重复，跨层出现同值可能代表合法的再次选择。

120. 卡片 120

     问题

     Kahn 拓扑排序中，入度为 0 的队列表示什么？

     答案

     它保存当前所有前置依赖都已移除的顶点。弹出一个顶点并删去它的出边后，新变成入度 0 的顶点入队；若最终处理数小于 V，图中有环。adjacency list 实现为 O(V+E) 时间、O(V) 辅助空间。

121. 卡片 121

     问题

     用 queue 分层处理 frontier 时，怎样避免把下一层节点混入当前层？

     答案

     在处理本层前先记录当前 queue size，只弹出这固定数量的对象。 过程中加入队尾的新对象属于下一层；不要让不断变化的 queue length 决定本层循环次数。

122. 卡片 122

     问题

     union-find 中，find(x) 返回值必须满足什么代表元不变量？

     答案

     它返回 x 所在分量的根代表元 r，且 parent[r] = r。两个元素连通当且仅当它们的根相同；路径压缩只能缩短父链，不能改变分量归属。

123. 卡片 123

     问题

     为什么列举全部结果的回溯复杂度必须考虑输出规模？

     答案

     因为仅写出结果就需要与输出字节数成正比的时间。更准确的口径是 O(访问状态数 × 每状态工作 + 输出规模)；结果很多时，算法不可能比输出本身更快。

124. 卡片 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. 卡片 125

     问题

     “输入位置互不相同”为什么不等于“生成结果按值互不重复”？

     答案

     不同索引可以保存相同值。用索引判断是否已使用只能防止重复占用同一位置；若结果按值判等，还要处理等值候选造成的对称分支。

126. 卡片 126

     问题

     DFS 怎样生成 topological order？

     答案

     在一个顶点的所有出邻居处理完后，把它加入 finish 列表，最后反转该列表。还要用三色状态检测有向环；有环时 finish 顺序不是有效拓扑序。

127. 卡片 127

     问题

     union by rank 或 size 为什么只能在两个根之间合并？

     答案

     因为 rank 或 size 描述的是整棵代表树，只有根持有有效的分量摘要。先 find 两个根，再把较矮或较小的根挂到另一根下，才能保持结构浅且摘要正确。

128. 卡片 128

     问题

     哪类前缀最适合立即剪枝？

     答案

     已经违反且后续选择无法修复的约束前缀。例如约束具有单调恶化性质时，一旦越界，继续加选择也不可能恢复合法。

129. 卡片 129

     问题

     从源点可达的边中出现负权时，为什么不能继续套用 Dijkstra？

     答案

     因为一个已弹出的顶点仍可能经负权边得到更短路径，破坏“最小 tentative distance 已确定”的不变量。无负环时可考虑 Bellman–Ford；若存在源点可达的负环，从该环还能到达的顶点没有有限最短距离。

130. 卡片 130

     问题

     求最优值的回溯中，什么时候可以用上界或下界剪掉整个分支？

     答案

     当该分支即使达到可证明的最好界，也不可能优于当前最优解时。界必须对该分支剩余可能性有效；界越紧通常剪得越多，但不会改变最坏情况保证。

131. 卡片 131

     问题

     为什么同一个 DAG 可能有多个合法 topological order？

     答案

     没有依赖关系强制先后的顶点可以交换位置。Kahn 过程中若某一步同时有多个入度 0 的选择，就存在多个合法顺序；每一步都只有一个选择时，顺序才唯一。

132. 卡片 132

     问题

     同时使用路径压缩和按秩或大小合并时，union-find 操作的复杂度应怎样表述？

     答案

     完成 O(n) 初始化后，m 次 find/union 总时间是 O(m α(n))，所以单次是摊还 O(α(n))。α(n) 是增长极慢的反 Ackermann 函数，工程上近似常数，但不是严格 O(1)。

133. 卡片 133

     问题

     搜索树每层最多 b 个候选、最大深度为 d 时，朴素回溯的规模怎样估算？

     答案

     节点上界是 1+b+…+b^d；当 b>1 时为 O(b^d)，当 b=1 时为 O(d)。若每个叶子还复制长度 d 的结果，要另计复制成本；实际分析优先使用真实访问状态数。

134. 卡片 134

     问题

     逐条加入简单无向图的边时，union-find 怎样识别一条形成环的冗余边？

     答案

     加入 {u, v} 前若 find(u) = find(v)，两点已经连通，这条新边就闭合了一个环；否则执行 union。这个判定针对增量式无向图，不能直接套到有向图。

135. 卡片 135

     问题

     当前和超过目标就停止向下搜索，需要什么前提？

     答案

     需要后续选择不会让和下降，例如所有可追加值都非负。若还允许负值，超过目标的前缀仍可能被拉回，直接剪枝会漏解。

136. 卡片 136

     问题

     union-find 能回答连通性，却不能直接回答哪些常见图问题？

     答案

     它不能恢复具体路径、计算最短距离或表达有向可达性，也不擅长普通在线删边。需要这些信息时，应保留图表示，并选择 BFS、DFS、最短路或更专门的动态结构。

137. 卡片 137

     问题

     不计输出时，深度为 d 的原地回溯通常需要多少辅助空间？

     答案

     通常是 O(d) 调用栈，再加当前路径和约束状态所占空间。若每层复制完整状态，空间可能更高，不能只看递归深度。

138. 卡片 138

     问题

     什么组合信号最值得考虑动态规划？

     答案

     问题可拆成重复出现的子问题，而且目标答案能由这些子问题答案组合出来。还需要能把每个子问题压成有限、可比较的 state；只有递归结构并不够。

139. 卡片 139

     问题

     某状态下只有一个合法候选时，应怎样处理这一步？

     答案

     直接沿唯一候选继续即可。它仍属于搜索状态转换，但不会产生分支；提前识别 forced move 能减少通用候选循环的开销，也方便暴露无候选的失败状态。

140. 卡片 140

     问题

     写 DP 前，dp[...] 的含义应该明确到什么程度？

     答案

     要明确每个索引代表的输入范围、资源或边界，以及值表示最大值、最小值、计数还是可行性。例如“处理前 i 个元素、容量为 c 时的最佳值”才足以推导 transition。

141. 卡片 141

     问题

     约束搜索中，为什么常优先处理候选最少的未决变量？

     答案

     它更可能尽早暴露冲突，从而缩短失败分支。这是改变搜索顺序的启发式，不会单独证明更好的最坏复杂度，也不能删掉任何合法候选。

142. 卡片 142

     问题

     base case 在 DP 中除了终止递归，还承担什么作用？

     答案

     它定义最小子问题的真实答案，并为所有后续 transition 提供起点。错误的 base case 会系统性污染整张表，即使递推式本身正确。

143. 卡片 143

     问题

     回溯中的 symmetry breaking 在删什么？

     答案

     它删除的是由对称选择产生、但代表同一个本质结果的等价分支。规则必须为每个等价类保留至少一个代表，否则会把真正不同的解一起删掉。

144. 卡片 144

     问题

     怎样检查 DP state 是否足以代表子问题？

     答案

     若两个历史映射到同一 state，它们未来的合法选择和最优后续值必须相同。若未来还依赖被丢掉的历史信息，state 就不充分，需要增加维度或改变定义。

145. 卡片 145

     问题

     一次选择后立即缩小其他变量的候选集合，为什么能加速回溯？

     答案

     这是约束传播：它把新确定的信息尽早传给后续状态，让矛盾更早出现。撤销选择时也必须恢复被缩小的候选集合，或使用不可变的新状态。

146. 卡片 146

     问题

     为什么很多 DP 要显式定义空前缀、零容量或空区间？

     答案

     这些是 transition 会引用的合法最小状态。把它们作为哨兵行、哨兵列或长度为零的 base case，能让边界与普通递推保持同一语义。

147. 卡片 147

     问题

     加入剪枝后，为什么不能直接宣称回溯从指数时间变成多项式时间？

     答案

     因为剪枝效果依赖输入和界的强弱；仍可能出现几乎没有分支可剪的输入。除非能证明所有输入的访问状态数都有多项式上界，否则最坏复杂度仍可能是指数级。

148. 卡片 148

     问题

     DP transition 应从哪里推导，而不是靠套模板？

     答案

     从最后一次选择或当前 state 的合法前驱推导。先覆盖所有合法来源，再用与目标一致的 min、max、求和或逻辑运算合并；计数时还要保证分类互斥。

149. 卡片 149

     问题

     只改变候选尝试顺序，会影响回溯的正确性吗？

     答案

     完整枚举时不会，只要所有合法候选仍会被访问。寻找首个解或配合当前最优界时，好的顺序可能更早得到强基准，从而显著加快剪枝，但最坏情况未必改变。

150. 卡片 150

     问题

     tabulation 的迭代顺序由什么决定？

     答案

     由依赖方向决定：计算一个 state 前，它引用的所有前驱必须已经完成。先画出 transition 的依赖边，再选相应的索引、长度或拓扑顺序。

151. 卡片 151

     问题

     枚举不允许重复节点的路径时，visited 为什么常要在回溯后撤销？

     答案

     因为约束通常是“当前路径内不能重复”，而不是“所有路径全局不能再用”。离开当前分支后撤销标记，其他独立路径才有机会使用该节点。

152. 卡片 152

     问题

     memoization 怎样消除递归中的重复子问题？

     答案

     第一次计算某个完整 state key 时保存结果，以后遇到同一 key 直接复用。它只访问从初始状态可达的子问题，但还会保留递归调用栈。

153. 卡片 153

     问题

     什么时候可以给回溯加入 memo，而不把不同历史错误合并？

     答案

     当返回结果只由 memo key 表示的状态决定时。若合法后续还取决于未编码的路径历史，缓存会复用错误答案；若目标是逐条输出路径，也不能把聚合值缓存当成完整枚举。

154. 卡片 154

     问题

     tabulation 的核心做法是什么？

     答案

     按合法依赖顺序从 base case 向目标 state 填表。它不需要递归栈，通常布局紧凑，但可能计算一些从实际初始输入不可达的表项。

155. 卡片 155

     问题

     什么时候把 visited 设为全局且不撤销会改变搜索语义？

     答案

     当同一状态可由不同路径到达，而目标需要区分或枚举这些路径时。全局标记会合并后来的到达；只有“每个状态处理一次”足以完成目标时才适合不撤销。

156. 卡片 156

     问题

     状态空间稀疏且很多 state 不可达时，memoization 与 tabulation 通常怎样取舍？

     答案

     memoization 常更自然，因为只计算可达 state；tabulation 可能扫完整稠密表。若递归深度危险、依赖顺序清晰或需要紧凑连续内存，tabulation 可能更合适。

157. 卡片 157

     问题

     回溯状态应该每层复制，还是原地修改后撤销？

     答案

     两者都可以。复制更容易保持分支隔离但每层可能付出状态大小的时间和空间；原地修改更省复制成本，却要求每个变化都有严格对称的撤销。

158. 卡片 158

     问题

     DP 时间复杂度应怎样从 state 与 transition 推导？

     答案

     用 可达或已填的 state 数 S × 每个 state 的 transition 成本 T，即 O(S·T)。若不同 state 的出边数不同，更准确地把所有实际 transition 成本求和。

159. 卡片 159

     问题

     当前没有合法候选，但结果还不完整时，这个回溯状态代表什么？

     答案

     它代表失败叶子，应直接返回且不收集结果。不要把“无法继续”与“已经完成”混成同一个终止条件。

160. 卡片 160

     问题

     分析 top-down DP 的辅助空间时，要统计哪些部分？

     答案

     统计最多 S 个缓存 state、最大递归深度 h 的调用栈，以及每层或每个 state 保存的额外数据。因此常见口径是 O(S + h)，但大对象 key 或 parent 表还要另计。

161. 卡片 161

     问题

     搜索树可能非常深时，递归回溯还有什么实现风险？

     答案

     调用栈可能超出运行时限制。可改用显式栈保存状态与下一候选位置，但仍要准确模拟进入、探索和撤销；这只改变栈的承载方式，不降低搜索规模。

162. 卡片 162

     问题

     普通 DP recurrence 的依赖图有环时，为什么不能直接递归加 memo？

     答案

     因为某个 state 会在结果确定前再次依赖自己，memo 中还没有可复用的完成值。需要证明能消除环、改写 state，或使用适合循环依赖的其他算法，而不是把进行中的值当答案。

163. 卡片 163

     问题

     什么信号说明朴素回溯很可能无法承受输入规模？

     答案

     分支因子大、深度高、约束弱，而且不存在可复用的紧凑子状态。此时访问状态可能接近完整决策树规模；应寻找更强剪枝、可合并的 DP 状态或问题特有结构。

164. 卡片 164

     问题

     什么时候自然地把 1D DP state 定义为 dp[i]？

     答案

     当前答案只需描述前 i 个元素、长度 i 的前缀或位置 i，且未来不需要更多历史维度时。必须先说清 i 是数量还是索引，避免 base case 与返回位置错一位。

165. 卡片 165

     问题

     什么题目信号值得考虑贪心，但还不足以证明贪心正确？

     答案

     解由一串可立即做出的局部选择组成，而且希望每步只保留一个方向。这个结构只提示候选方法；还必须证明当前选择不会排除某个全局最优解。

166. 卡片 166

     问题

     网格型 DP 中，dp[r][c] 最常表示哪类子问题？

     答案

     表示到达格点 (r,c) 的答案，或以该格点为边界的矩形前缀答案。具体含义必须说明允许从哪些方向转移；坐标本身不能替代 transition 定义。

167. 卡片 167

     问题

     贪心选择性质具体要说明什么？

     答案

     要说明存在一个最优解包含当前贪心选择。这样做出该选择后，剩余部分仍可作为同类子问题继续求解，而不是仅凭局部指标看起来最好。

168. 卡片 168

     问题

     两个序列共同决定答案时，dp[i][j] 的自然语义是什么？

     答案

     通常表示第一个序列前 i 个元素与第二个序列前 j 个元素组成的子问题。比较当前末尾后，transition 可引用缩短一个或两个前缀的 state。

169. 卡片 169

     问题

     exchange argument 怎样证明第一步贪心选择是安全的？

     答案

     取一个最优解，把它与贪心选择冲突的部分换掉，并证明可行性不变且目标值不变差。于是至少有一个同样好的最优解以贪心选择开头。

170. 卡片 170

     问题

     资源容量限制下的选择型 DP，常用哪两个维度定义 state？

     答案

     常用“已考虑的前 i 个候选”和“当前容量 c”。dp[i][c] 表示在这两项限制下的目标值，使“不选当前项”和“选择当前项”能引用明确前驱。

171. 卡片 171

     问题

     staying-ahead 证明比较的是什么？

     答案

     比较贪心解与任意最优解的每个等长前缀，证明贪心前缀在关键指标上始终不落后。最后一个前缀就是完整解，因此得到整体最优性。

172. 卡片 172

     问题

     当答案由连续区间内部的拆分决定时，常用什么 DP state？

     答案

     使用 dp[l][r] 表示区间 [l,r] 的答案。transition 枚举合法分割点或最后合并位置，并组合更短的子区间。

173. 卡片 173

     问题

     用归纳法证明贪心时，归纳步骤要连接哪两个事实？

     答案

     先证明当前选择属于某个最优解，再证明选完后的剩余实例仍满足同样结构。这样可对剩余实例重复应用贪心论证。

174. 卡片 174

     问题

     DAG 上的 DP 应按什么顺序处理节点？

     答案

     按与 transition 依赖方向一致的拓扑顺序。若 u 的答案用于更新 v，就先完成 u；反向定义 state 时则使用反向拓扑顺序。

175. 卡片 175

     问题

     为什么只有 optimal substructure 不能推出贪心正确？

     答案

     因为它只说明最优解由最优子解组成，没有说明哪一个局部选择可安全固定。多个分支都可能通向不同子问题；若无法排除分支，通常仍需 DP 或搜索比较它们。

176. 卡片 176

     问题

     计数型 DP 为什么常把前驱答案相加？

     答案

     因为每个前驱代表一组到达当前 state 的方案；当这些方案集合互不重叠且覆盖全部情况时，总数就是求和。若分类重叠，相加会重复计数。

177. 卡片 177

     问题

     exchange argument 只证明能交换第一处差异，为什么还不够？

     答案

     还要说明交换可反复进行，最终能把某个最优解转换成完整的贪心解。若后续交换会破坏前面保持的结构，证明链就没有闭合。

178. 卡片 178

     问题

     1D recurrence 只依赖前 k 个 state 时，空间可怎样压缩？

     答案

     只保留长度 k 的滚动窗口，把空间从 O(n) 降到 O(k)；若 k 是常数，就是 O(1)。更新前要保存仍会被后续 transition 使用的旧值。

179. 卡片 179

     问题

     怀疑某个贪心规则错误时，一个直接的快速检查是什么？

     答案

     构造一个最小反例，让局部最优选择占用未来关键资源，而另一项当前略差的选择得到更好总结果。一个合法反例就足以否定通用正确性。

180. 卡片 180

     问题

     网格 DP 的第一行和第一列为什么经常需要单独初始化？

     答案

     它们缺少某些普通前驱，直接套通用 transition 会越界或读到假状态。可以单独初始化，也可加语义明确的哨兵边界；两种方法都要保持不可达位置不可被误用。

181. 卡片 181

     问题

     贪心算法先排序时，排序依据应怎样论证？

     答案

     常见办法是证明把相邻逆序对换成该顺序不会破坏可行性或使目标变差，并能反复交换到目标顺序。若只能说这个 key “直觉上重要”，排序仍是未经证明的猜测。

182. 卡片 182

     问题

     长度分别为 n 和 m 的双序列 DP，若每个 state 做 O(1) 工作，复杂度是多少？

     答案

     共有 O(nm) 个 state，因此时间为 O(nm)，完整表空间为 O(nm)。若只依赖有限相邻行，可按列数压缩；只有序列角色可交换时，才能进一步选短序列为列并写成 O(min(n,m))。

183. 卡片 183

     问题

     “每次拿当前收益最大项”为什么可能失败？

     答案

     当前最大收益可能消耗过多容量或阻塞多个稍小但合计更优的选择。除非能证明替换或支配关系，单步收益最大只是启发式。

184. 卡片 184

     问题

     “每个候选选或不选”的 DP transition 怎样组织？

     答案

     把当前 state 的答案合并为两类：不选时继承前一个候选层；可选时从扣除相应资源的合法前驱加上当前贡献。两类必须覆盖全部方案且不重复。

185. 卡片 185

     问题

     排序后单次贪心扫描通常需要维护什么不变量？

     答案

     已处理前缀的选择必须始终可行，并且能扩展成某个该前缀下不劣的完整解。每次接受或拒绝候选都要保持这个性质。

186. 卡片 186

     问题

     bottom-up interval DP 为什么通常按区间长度递增填表？

     答案

     因为长区间的 transition 通常依赖更短子区间。先完成长度较小的 [l,r]，再扩展长度，能保证所有前驱已经有值。

187. 卡片 187

     问题

     同一个最优化场景中，什么区别通常把贪心与 DP 分开？

     答案

     贪心能证明一个局部选择可永久固定；DP 则保留多个状态下的最佳结果，直到 transition 比较后再决定。无法证明安全丢弃其他选择时，更像 DP。

188. 卡片 188

     问题

     DAG DP 每条依赖边处理一次时，复杂度怎样计算？

     答案

     对 V 个 state 和 E 条 transition 边，拓扑排序加递推通常是 O(V+E) 时间；邻接表、入度和 DP 值共需 O(V+E) 空间。

189. 卡片 189

     问题

     贪心指标相同时，tie-breaking 可以随便写吗？

     答案

     只有证明任一并列选择都安全时才可以。否则第二关键字可能影响可行性或未来选择；实现中应明确稳定、确定且符合证明的 tie-breaking。

190. 卡片 190

     问题

     可行性 DP 的多个前驱通常怎样合并？

     答案

     用逻辑 OR：只要存在一个合法前驱能转移到当前 state，它就可达。初始化时必须区分真实可达的 base case 与默认的 false。

191. 卡片 191

     问题

     按收益与成本比选择时，“资源可切分”为什么是重要边界？

     答案

     可切分时，剩余容量可用候选的一部分填补；不可切分时，一个高比率大项可能挡住组合起来更好的小项。比率规则能否精确求优必须按具体约束证明。

192. 卡片 192

     问题

     把双序列 DP 压成一行时，为什么常需要保存左上角旧值？

     答案

     因为原 dp[i-1][j-1] 会在原地更新 dp[j] 时被覆盖。用临时变量保存更新前的左上角，才能同时读取上一行、当前行左侧和上一行左侧。

193. 卡片 193

     问题

     贪心前的排序或去除被支配项，属于算法复杂度的一部分吗？

     答案

     属于。若 n 个候选先 comparison sort 再线性扫描，时间是 O(n log n)，不是 O(n)；排序辅助空间取决于具体实现。

194. 卡片 194

     问题

     每个候选最多使用一次时，1D 容量 DP 为什么通常倒序更新 c？

     答案

     倒序保证读取的 dp[c-cost] 仍来自处理当前候选之前的旧层，因此当前候选不会在同一轮被重复使用。正序会读到本轮刚更新的值，改变问题语义。

195. 卡片 195

     问题

     什么时候可以用 dominance rule 永久丢弃一个候选？

     答案

     当另一个候选在所有与未来有关的维度上都不差，并至少一项更好，而且替换后仍可行。只比较一个维度不足以建立支配关系。

196. 卡片 196

     问题

     长度为 n 的 interval DP 若每个区间枚举 O(n) 个分割点，时间和表空间是多少？

     答案

     共有 O(n²) 个区间 state，每个最多做 O(n) 次 transition，所以时间为 O(n³)，完整表空间为 O(n²)。

197. 卡片 197

     问题

     若候选已按证明所需顺序给出，贪心扫描何时是 O(n)？

     答案

     当 n 个候选各处理一次，且每次可行性更新和选择都是 O(1) 时，扫描为 O(n)。若更新依赖树、heap 或再次搜索，就要把相应成本计入。

198. 卡片 198

     问题

     最小值或最大值 DP 中，不可达 state 应怎样初始化？

     答案

     用不会被误当成合法答案的 sentinel，例如最小化用 +∞、最大化用 -∞，并只从可达前驱转移。随手初始化为 0 可能凭空制造路径。

199. 卡片 199

     问题

     选择不可撤销且非法前缀无法修复时，贪心每一步要检查什么？

     答案

     检查加入候选后前缀仍然可行。一旦接受非法选择，后续无法修复；检查所用的状态和约束必须与正确性证明一致。

200. 卡片 200

     问题

     正成本候选允许重复使用时，1D 容量 DP 为什么常正序更新 c？

     答案

     正序让 dp[c-cost] 可以是本轮刚加入当前候选后的值，从而再次使用它。这个方向只适用于 transition 明确允许无限复用的语义；零成本候选要单独判断是否使目标无界。

201. 卡片 201

     问题

     用大小最多为 k 的 heap 从 n 个候选中保留当前最佳集合，复杂度怎样计算？

     答案

     若每个候选至多触发常数次 heap 操作，时间为 O(n log k)，辅助空间为 O(k)。这只是实现成本；保留哪些候选仍需要独立的正确性证明。

202. 卡片 202

     问题

     计数 DP 结果可能很大时，什么时候可以在每次 transition 后取模？

     答案

     只有题目要求返回某个模数下的结果，且后续运算与模运算兼容时。若需要精确计数、比较真实大小或恢复值，擅自取模会改变答案。

203. 卡片 203

     问题

     一个离线贪心证明为什么不能自动用于在线到达的候选？

     答案

     离线算法可能依赖完整排序或未来信息，在线算法在做决定时看不到这些内容。若选择不可撤销，信息条件变化会破坏原来的安全选择论证。

204. 卡片 204

     问题

     有 n 个候选、整数容量上限 C 的典型容量 DP，复杂度怎样表达？

     答案

     若每个 (i,c) state 做 O(1) transition，时间为 O(nC)；完整二维表空间为 O(nC)，可合法滚动时为 O(C)。这是 pseudo-polynomial：C 的数值可能远大于其编码长度。

205. 卡片 205

     问题

     输入允许负收益或负成本时，为什么要重新检查原有贪心规则？

     答案

     因为许多单调性、排序和“加入不会变差”的论证默认量为非负。负值不必然使贪心失败，但它可能直接破坏证明依赖的前提。

206. 卡片 206

     问题

     DP 表只有最优值时，怎样恢复一条具体最优选择序列？

     答案

     为每个 state 记录产生最优值的 parent 或选择，最后从目标 state 反向追踪到 base case。若只需一条路径，并列最优时使用确定的 tie-breaking 即可。

207. 卡片 207

     问题

     把“最小化”贪心规则反向排序，是否就能解决对应的“最大化”目标？

     答案

     不能直接推断。目标方向改变后，可行替换和前缀支配关系也可能改变；反向规则需要自己的安全选择证明或反例检查。

208. 卡片 208

     问题

     1D DP 压缩后出现“同一个候选被意外重复使用”，最先检查什么？

     答案

     检查内层索引方向。原地数组同时承载上一层和当前层；错误方向会让 transition 读到本轮刚写入的值，从而改变“每项一次”或“可重复”的语义。

209. 卡片 209

     问题

     为什么给一个已证明的贪心问题增加新约束后，必须重做证明？

     答案

     新约束可能让原来的交换不再可行，或让局部选择消耗此前不存在的资源。算法代码即使还能运行，也不代表最优性仍成立。

210. 卡片 210

     问题

     top-down DP 在小输入正确、复杂输入偶尔错误时，memo key 应检查什么？

     答案

     检查 key 是否包含所有会影响未来答案的状态变量。若不同剩余资源、边界或约束共享同一个 key，后计算的分支会错误复用先前结果。

211. 卡片 211

     问题

     尚无最优性证明或可用定理依据的局部选择算法，应怎样准确描述？

     答案

     应暂时描述为启发式，而不是精确贪心解法。它可能在常见输入上表现好，但不能承诺总是得到全局最优结果。

212. 卡片 212

     问题

     为什么 DP 能处理局部最优选择不安全的场景？

     答案

     DP 不立即固定单一路径，而是为不同 state 保留各自的最佳答案，再通过 transition 比较。它用更多 state 和计算换取对多种未来可能性的保留。

213. 卡片 213

     问题

     贪心算法不能保证精确最优时，还可能证明什么有用性质？

     答案

     可能证明 approximation bound，即结果与最优值之间的最坏比例或加性差距。这个界必须单独证明，不能由“用了贪心”自动得到。

214. 卡片 214

     问题

     memoized backtracking 在什么情况下本质上就是 top-down DP？

     答案

     当搜索返回的是可聚合的最优值、计数或可行性，而且未来只由紧凑 state key 决定时。若必须区分并输出每条历史路径，单纯合并同 state 就不等价。

215. 卡片 215

     问题

     贪心只维护目标值时，怎样在最后返回具体选择？

     答案

     在接受候选时同步记录其标识或 parent 关系。若之后允许替换，就同时更新记录；只保存聚合值通常无法唯一恢复选择集合。

216. 卡片 216

     问题

     什么时候可以安全压缩 DP 空间？

     答案

     当未来 transition 只依赖一个有限窗口内的旧 state，且更新顺序不会提前覆盖仍需读取的值。先列出依赖，再决定滚动维度；不能只因表很大就压缩。

216张卡片

算法面试模式闪卡：双指针、滑动窗口、图与动态规划

免费学习这套卡组

Flashcards 将打开，你可以立即开始学习。