🔄 复习日 / Review Day — Day 125 (2026-09-03)
📊 NeetCode: 98/150 · SysDesign: 60/40 · Behavioral: 60/40 · Frontend: 37/50 · AI: 30/30
🔥 3-day streak!
🔄 复习日 / Review Day
今天是复习日！回顾过去4天的内容。
Days covered: 121 (Cheapest Flights deep dive), 122 (Reconstruct Itinerary), 123 (Swim in Rising Water), 124 (Alien Dictionary)
📝 Quick Quiz — 3 Mini-Reviews
Q1: [💻 Algorithms — Alien Dictionary (Day 124)]
给你一个字典顺序排列的单词列表，其中字母顺序与英语不同。写一个函数推导出字母的拓扑顺序。如果遇到矛盾（比如 ["abc", "ab"]），应该返回什么？为什么？
You have a word list sorted by an alien alphabet's order. If you encounter ["abc", "ab"] in the list (a longer word before its prefix), what should you return and why?
💡 答案 / Answer:
返回空字符串 ""，因为这代表无效输入。在拓扑排序中，这种情况等价于图中出现了环（cycle）。
具体原因："abc" 排在 "ab" 之前，意味着字符 c（位置3）应该先于"不存在"的字符——但 "ab" 是 "abc" 的前缀，即在相同前缀下较短的词出现在后面，这在任何有效字典中都是矛盾的。
Key insight: Return "" (empty string). When "abc" comes before its prefix "ab", it's an invalid ordering—no valid topological sort exists. In your cycle detection (DFS or Kahn's BFS), this manifests as a cycle in the directed graph. Always check: if word1 is a prefix of word2 but word1 appears after word2, return "" immediately before even building the graph.
# Early exit check before BFS/DFS:
if len(w1) > len(w2) and w1[:len(w2)] == w2:
return ""Q2: [🧩 Deep Dive — Cheapest Flights Within K Stops (Day 121)]
在"K次中转最便宜机票"这道题中，为什么不能直接用标准 Dijkstra？Bellman-Ford 的哪个关键修改让它能处理"最多K次中转"的限制？
In "Cheapest Flights Within K Stops", why can't standard Dijkstra be applied directly? What key modification to Bellman-Ford handles the "at most K stops" constraint?
💡 答案 / Answer:
为什么Dijkstra不行： 标准Dijkstra用贪心选取当前最短距离的节点，但这里的"最短"有两个维度——费用和中转次数。一条费用更低但中转数更多的路径可能使你超过K次限制，而Dijkstra已经把某些节点标记为"已确定"，无法回头。
Bellman-Ford的关键修改： 精确执行 K+1 轮松弛，每轮代表一次飞行。关键在于必须用上一轮的快照（copy of prices）来更新，而不是直接在原数组上修改——否则同一轮内的更新会串联，等于允许了超过1步的跳跃。
Why Dijkstra fails: It greedily finalizes nodes, but here cost and stops are two separate dimensions. A cheaper path might use more stops, and once Dijkstra "settles" a node, it won't revisit it with a higher-stop cheaper variant.
The Bellman-Ford fix: Run exactly K+1 relaxation rounds (one per flight leg). The critical trick: always relax using a copy of the previous round's distances, not in-place. Without this snapshot, a single round could chain multiple hops, blowing past the K-stop limit.
# Key pattern:
for i in range(k + 1):
tmp = prices.copy() # snapshot!
for u, v, w in flights:
if prices[u] + w < tmp[v]:
tmp[v] = prices[u] + w
prices = tmpQ3: [💻 Algorithms — Swim in Rising Water (Day 123)]
"Swim in Rising Water"中，水位 t 表示你必须等待到时间 t 才能踩上值为 t 的格子。这道题为什么适合用 Dijkstra（最小堆），而不是标准BFS？它的"代价"函数是什么？
In "Swim in Rising Water", why is Dijkstra (min-heap) the right tool rather than BFS? What exactly is the "cost" being minimized?
💡 答案 / Answer:
为什么不用BFS： BFS假设每步代价相等（为1），但这里每个格子有不同的"等待代价"（格子的值）。BFS第一次到达终点不代表路径最优。
Dijkstra的"代价"函数： 最小化从起点到终点路径上所有格子值的最大值（max along the path），而不是总和。因为你的等待时间 = 路径上最大的格子值。
直觉： 想象你在找一条"海拔最高点最低"的登山路线。Dijkstra中，每个状态存储的不是累计费用，而是max(当前路径上所有格子值)。
Why not BFS: BFS treats all edges as equal cost, but here each cell has a different "waiting cost" (its value). The first path BFS finds isn't guaranteed to minimize the bottleneck.
The "cost" being minimized: The maximum cell value along the path (not the sum). Your wait time equals the highest-valued cell you step on. So the min-heap key is max(cost_so_far, grid[r][c]).
heap = [(grid[0][0], 0, 0)] # (max_so_far, row, col)
while heap:
cost, r, c = heappop(heap)
if (r, c) == (n-1, n-1): return cost
for nr, nc in neighbors:
new_cost = max(cost, grid[nr][nc])
heappush(heap, (new_cost, nr, nc))This is essentially Dijkstra on a "minimax" objective — a pattern that appears in many graph problems.
💡 复习巩固记忆，螺旋式上升。图算法这周覆盖了拓扑排序、最短路径变体和最小瓶颈路径——三种完全不同的图问题范式！
📅 明天继续新内容！