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

Question 1

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

Accepted Answer

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

Question 2

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

Accepted Answer

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

Question 3

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

Accepted Answer

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

Question 4

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

Accepted Answer

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

Question 5

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

Accepted Answer

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

Question 6

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

Accepted Answer

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

Question 7

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

Accepted Answer

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

Question 8

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

Accepted Answer

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

Question 9

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

Accepted Answer

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

Question 10

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

Accepted Answer

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

Question 11

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

Accepted Answer

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

Question 12

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

Accepted Answer

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

Question 13

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

Accepted Answer

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

Question 14

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

Accepted Answer

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

Question 15

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

Accepted Answer

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

Question 16

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

Accepted Answer

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

Question 17

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

Accepted Answer

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

Question 18

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

Accepted Answer

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

Question 19

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

Accepted Answer

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

Question 20

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

Accepted Answer

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

Question 21

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

Accepted Answer

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

Question 22

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

Accepted Answer

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

Question 23

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

Accepted Answer

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

Question 24

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

Accepted Answer

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

Question 25

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

Accepted Answer

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

Question 26

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

Accepted Answer

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

Question 27

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

Accepted Answer

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

Question 28

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

Accepted Answer

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

Question 29

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

Accepted Answer

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

Question 30

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

Accepted Answer

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

Question 31

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

Accepted Answer

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

Question 32

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

Accepted Answer

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

Question 33

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

Accepted Answer

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

Question 34

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

Accepted Answer

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

Question 35

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

Accepted Answer

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

Question 36

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

Accepted Answer

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

Question 37

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

Accepted Answer

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

Question 38

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

Accepted Answer

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

Question 39

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

Accepted Answer

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

Question 40

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

Accepted Answer

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

Question 41

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

Accepted Answer

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

Question 42

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

Accepted Answer

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

Question 43

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

Accepted Answer

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

Question 44

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

Accepted Answer

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

Question 45

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

Accepted Answer

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

Question 46

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

Accepted Answer

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

Question 47

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

Accepted Answer

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

Question 48

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

Accepted Answer

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

Question 49

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

Accepted Answer

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

Question 50

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

Accepted Answer

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

Question 51

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

Accepted Answer

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

Question 52

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

Accepted Answer

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

Question 53

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

Accepted Answer

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

Question 54

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

Accepted Answer

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

Question 55

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

Accepted Answer

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

Question 56

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

Accepted Answer

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

Question 57

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

Accepted Answer

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

Question 58

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

Accepted Answer

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

Question 59

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

Accepted Answer

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

Question 60

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

Accepted Answer

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

Question 61

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

Accepted Answer

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

Question 62

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

Accepted Answer

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

Question 63

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

Accepted Answer

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

Question 64

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

Accepted Answer

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

Sobre este mazo

Tarjetas de este mazo

Tarjeta 1

Tarjeta 2

Tarjeta 3

Tarjeta 4

Tarjeta 5

Tarjeta 6

Tarjeta 7

Tarjeta 8

Tarjeta 9

Tarjeta 10

Tarjeta 11

Tarjeta 12

Tarjeta 13

Tarjeta 14

Tarjeta 15

Tarjeta 16

Tarjeta 17

Tarjeta 18

Tarjeta 19

Tarjeta 20

Tarjeta 21

Tarjeta 22

Tarjeta 23

Tarjeta 24

Tarjeta 25

Tarjeta 26

Tarjeta 27

Tarjeta 28

Tarjeta 29

Tarjeta 30

Tarjeta 31

Tarjeta 32

Tarjeta 33

Tarjeta 34

Tarjeta 35

Tarjeta 36

Tarjeta 37

Tarjeta 38

Tarjeta 39

Tarjeta 40

Tarjeta 41

Tarjeta 42

Tarjeta 43

Tarjeta 44

Tarjeta 45

Tarjeta 46

Tarjeta 47

Tarjeta 48

Tarjeta 49

Tarjeta 50

Tarjeta 51

Tarjeta 52

Tarjeta 53

Tarjeta 54

Tarjeta 55

Tarjeta 56

Tarjeta 57

Tarjeta 58

Tarjeta 59

Tarjeta 60

Tarjeta 61

Tarjeta 62

Tarjeta 63

Tarjeta 64

Tarjeta 65

Tarjeta 66

Tarjeta 67

Tarjeta 68

Tarjeta 69

Tarjeta 70

Tarjeta 71

Tarjeta 72

Tarjeta 73

Tarjeta 74

Tarjeta 75

Tarjeta 76

Tarjeta 77

Tarjeta 78