更新题目 螺旋遍历：遇障碍转向
题目 temu-spiral-blockers · 修改（rev 6） · · 2026-10-26 00:04
body
@@ -1,41 +1,96 @@ +## TL;DR + +- 先答 [[q:lc54]] 原题，follow-up 是矩阵里有障碍格，碰到就顺时针转向，只输出按规则走得到的格子（见「题目」）。 +- 四边界收缩的写法处理不了障碍，改用「方向数组 + visited」模拟，这个写法同时也能答原题（见「思路」）。 +- 每一步先试直走，走不通再按顺时针换方向。先试右转会把原题都走错（见「代码」里的对照）。 +- 右转后还走不通时，是继续转还是直接结束，开写前要问，两种理解在 `[[1, -1], [3, 4]]` 上结果不同（见「题目」里要问的问题）。 +- 同一轮也可能考生成版 [[q:lc59]]，代码只差把「读值」换成「填数」（见「Follow-up」）。 + ## 题目 -先是 [[q:lc54]] 原题：m × n 矩阵，从外到内顺时针螺旋输出所有值。 - -Follow-up：矩阵里有障碍格（blocker，有的帖子写成值为 -1 的格子）。走的时候碰到障碍就要转向，转向一律顺时针（右转），问最后的输出顺序。 - -> [!warning] 一亩三分地 2026-10 那篇店面的楼主在回复里补充：**不一定要输出全部数据，只要输出按规则能走到的那些格子**——也就是说，被障碍挡住、永远走不到的格子不输出。其他细节（障碍格本身肯定不输出、四个方向都走不了就结束）是按最自然的理解【推断】的，面试时还是先和面试官对一遍。 +先是 [[q:lc54]] 原题：给一个 m × n 矩阵，从左上角出发，从外到内顺时针螺旋输出所有值。 + +Follow-up：矩阵里有障碍格（blocker），有的帖子把它写成值为 -1 的格子。走的时候碰到障碍就要转向，转向一律顺时针（右转），问最后的输出顺序。 + +> [!note] 一篇店面的楼主在回复里补充了题意：不一定要输出全部数据，只输出按规则能走到的那些格子。被障碍挡住、永远走不到的格子不输出。 + +例子（障碍写成 -1）： + +``` +1 2 3 4 +5 -1 7 8 +9 10 11 12 +``` + +输出 `[1, 2, 3, 4, 8, 12, 11, 10, 9, 5]`。从 1 往右走到 4，碰到右边界转向下走到 12，碰到下边界转向左走到 9，碰到左边界转向上走到 5。在 5 这里，上面的 1 已经走过，右边是障碍，下面的 9 走过，左边越界，四个方向都走不了，结束。7 永远走不到，所以不输出。 + +### 要和面试官对清楚的问题 + +口头题面只说了「碰到障碍顺时针转」，下面几处是留白。第一条楼主确认过，其余是按最自然的理解【推断】的，面试时先问。 + +| 问题 | 通常的答案 | 答案不同时代码怎么改 | +| --- | --- | --- | +| 走不到的格子输出吗 | 不输出（楼主确认） | 按走路规则永远到不了这些格子，要输出就得另定一条规则决定它们排在哪里（比如走完后按行扫一遍补上），先问清这条规则，再在 `return out` 之前补一段 | +| 障碍格本身输出吗 | 不输出【推断】 | 不用改。障碍格本来就进不去 | +| 什么时候结束 | 当前格四个方向都走不了就结束【推断】 | 不用改 | +| 右转后还走不通怎么办 | 继续顺时针转，直到找到能走的方向【推断】 | 只允许右转一次的话，把内层循环的 `range(4)` 改成 `range(2)` | +| 障碍怎么表示 | 值为 -1 | 代码里 `blocker` 是参数，换成别的值直接传 | + +第四个问题最容易被忽略。「继续顺时针转」意味着转三次，转三次等于左转。在下面这个 2 × 2 的例子里两种理解结果不同： + +``` +1 -1 +3 4 +``` + +- 从 1 出发向右，右边是障碍，右转向下走到 3。在 3 这里方向是向下，下面越界，右转是向左，也越界。 +- 「继续转」的理解：再转一次是向上（1 走过），再转一次是向右，走到 4，输出 `[1, 3, 4]`。 +- 「只右转一次」的理解：右转后还走不通就结束，输出 `[1, 3]`。 + +2026-10-26 用脚本枚举了 1 × 1 到 4 × 4、最多两个障碍的所有网格，两种理解结果不同的网格有 125 个，面积最小的只有这一个。没有障碍时两种理解永远一样，因为原题里从来不需要左转（2026-10-26 在 1 × 1 到 10 × 10 的全部无障碍矩阵上跑过，两种理解和四边界写法的输出完全相同）。 + +> [!say] Before coding, I'd like to confirm two things. First, cells that the blockers make unreachable are simply not printed. Second, if turning right once still doesn't work, do I keep rotating, which effectively means turning left, or do I stop there? ## 面经里怎么考的 -**这是 Temu 第一轮技术面出现最多的题，Order 组尤其常见。** 2026-10-18 把一亩三分地上 Temu 最近两年的帖子读完后，螺旋矩阵（[[q:lc54]]）或者它的生成版（[[q:lc59]]）在第一轮出现了七次，其中三篇写明是 order / ordering 组： - -- 2026-10 两篇店面（发帖人不同，内容几乎一样）：先是 LC 54 原题，follow-up 加障碍格（blocker），遇到障碍就顺时针右转。其中一篇楼主在回复里说清了题意：**不要求输出全部数据，只要输出按规则能走到的那些格子**——和下面「代码」那一节的理解一致，被挡住、走不到的格子就不输出。 -- 2026-07 一篇 temu 一面（过）：LC 59 的 m × n 版本，follow-up 是遇到 -1 也要转向。回复里有人举了个例子问输出是什么，说明这个规则当场要和面试官对清楚。 -- 2026-07 一篇 ordering 组 Senior 第一轮（过）：30 分钟深挖过往项目，然后 LC 54 和 [[q:lc98]] 各一道。 -- 2026-08 一篇 Orders 组 Java 岗第一轮：LC 59，**要求用 Java 写**，面试平台只能用 Chrome 打开。 -- 2026-06 一篇 order team coding screen（挂）：给 m、n 生成 m × n 的螺旋矩阵（LC 59 的推广），楼主说忘了怎么写。 -- 2026-03 一篇第一轮：LC 59。 - -教训：这道题在面试里通常只占后 20 分钟左右（前面半小时到 40 分钟是深挖简历），所以要能**一次写对、边写边讲**，并且原题、生成版、带障碍的 follow-up 三种都要熟。 +这道题出现在 Temu 第一轮技术面，order 组最常见。考法是先写 [[q:lc54]] 原题，写完后面试官加障碍格作为 follow-up，规则是遇到障碍就顺时针右转。有楼主在回复里说清了题意：只输出按规则能走到的格子。 + +同一个组的第一轮也常考它的生成版 [[q:lc59]]：给 m 和 n，按螺旋顺序把 1, 2, 3, …… 填进 m × n 矩阵。有一篇面经的 follow-up 是填的时候遇到 -1 也要转向，回复里还有人举了一个例子问输出是什么，说明这条规则当场要和面试官对清楚。另一篇 order team 的 coding screen 考的就是生成版，楼主说忘了怎么写，挂了。 + +其他几篇面经提供了这一轮的形式： + +- ordering 组一篇 Senior 第一轮先花 30 分钟深挖过往项目，然后做 LC 54 和 [[q:lc98]] 各一道。 +- Orders 组一篇 Java 岗第一轮考的是 LC 59，要求用 Java 写，面试平台只能用 Chrome 打开。 + +这道题在面试里通常只占后 20 分钟左右，前面半小时到 40 分钟是深挖简历。所以要能一次写对、边写边讲，原题、生成版、带障碍的 follow-up 三种都要熟。 ## 思路 -原题常见写法是四条边界收缩；但有了障碍格，边界法就不好用了。改成**方向数组 + visited 模拟**： - -- 方向按右、下、左、上排；当前方向下一格越界、走过、或者是障碍，就顺时针换下一个方向。 -- 四个方向都走不了就结束。 -- 不输出障碍格。 - -这个写法对没有障碍的矩阵也正确，所以原题直接用它答，follow-up 只多一个判断，面试时很顺。 +原题常见写法是四条边界收缩：维护上、下、左、右四条边界，每走完一圈把四条边界各往里收一格。这个写法把路线写死成一圈一圈的矩形，障碍格没法让它中途转向。最多只能做到「碰到障碍格跳过不输出」，结果和题意不符。在题目的例子上，它会多输出走不到的 7（输出见「代码」里的对照）。 + +所以改成直接模拟一个人在格子里走： + +- 记住当前位置 `(r, c)` 和当前方向 `d`。方向按右、下、左、上排成数组 `dirs`，下标加 1 就是顺时针转 90 度。 +- 用 visited 数组 `seen` 记下走过的格子。 +- 每一步从当前方向开始，依次试 `d`、`d+1`、`d+2`、`d+3`（对 4 取模）四个方向。代码里用 `t` 表示偏移量：`t = 0` 是直走，`t = 1` 是右转，`t = 2` 是掉头，`t = 3` 是左转（顺时针转三次）。 +- 某个方向的下一格没越界、没走过、也不是障碍，就走过去，并把方向更新成这个方向。四个都不行就结束。 + +`t = 2`（掉头）永远走不通，原因是除了起点，来的那一格一定走过，而起点向左是越界。保留它只是为了让「依次试四个方向」的循环写起来整齐。 + +在没有障碍的前提下，这个写法输出的就是原题的螺旋顺序。原因是没有障碍时，触发转向的只有越界和走过两种情况。沿外圈走到边界会右转，走完一圈回到起点下方时，上面那格走过，于是右转进入内圈。外圈走过之后，走过的格子就相当于往里收了一格的边界，内圈照同样的规则再走一圈，这和原题的路线一致。所以面试时原题直接用它答，follow-up 只在判断条件里多加 `grid[nr][nc] != blocker`。 + +> [!say] Instead of shrinking four boundaries, I simulate the walk. I keep a direction index and a visited grid. At each step I first try to go straight, and whenever the next cell is out of bounds, visited, or a blocker, I rotate clockwise and try again. If all four directions fail, I stop. ## 代码 ```python -def spiral_with_blockers(grid, blocker="#"): - m, n = len(grid), len(grid[0]) if grid else 0 - if not m or not n or grid[0][0] == blocker: +DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右、下、左、上：顺时针 + + +def spiral_with_blockers(grid, blocker=-1): + m = len(grid) + n = len(grid[0]) if m else 0 + if m == 0 or n == 0 or grid[0][0] == blocker: return [] - dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右、下、左、上：顺时针 seen = [[False] * n for _ in range(m)] r = c = d = 0 @@ -43,7 +98,7 @@ out = [grid[0][0]] while True: - for t in range(4): + for t in range(4): # t = 0 直走，t = 1 右转，t = 2 掉头，t = 3 左转 nd = (d + t) % 4 - nr, nc = r + dirs[nd][0], c + dirs[nd][1] + nr, nc = r + DIRS[nd][0], c + DIRS[nd][1] if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] != blocker: d, r, c = nd, nr, nc @@ -51,26 +106,208 @@ out.append(grid[r][c]) break + else: # 四个方向都没 break，走不动了 + return out +``` + +`for ... else` 的 `else` 只在循环没有被 `break` 打断时执行，这里就是「四个方向都试过、都走不通」。 + +### 正确版本和三个错误版本的对照 + +三个错误版本都是面试里容易写出来的： + +- `wrong_turn_first`：每一步先试右转，直走排到最后。 +- `wrong_no_visited`：忘了 visited，只判断越界和障碍。 +- `wrong_boundary_skip`：沿用原题的四边界收缩，遇到障碍格跳过不输出。 + +前两个和正确版本只差一行，其余照抄 `spiral_with_blockers`： + +```python +# wrong_turn_first：内层循环改成先试右转 + for t in (1, 2, 3, 0): + +# wrong_no_visited：判断条件去掉 not seen[nr][nc] + if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != blocker: +``` + +`wrong_no_visited` 停不下来，测试时在 `while True:` 下面第一行加了 `if len(out) >= 30: return out + ["..."]`，输出满 30 个就截断。 + +`wrong_boundary_skip` 是原题的标准写法，只在最后把障碍值滤掉： + +```python +def wrong_boundary_skip(grid, blocker=-1): + if not grid or not grid[0]: + return [] + top, bot, left, right = 0, len(grid) - 1, 0, len(grid[0]) - 1 + out = [] + while top <= bot and left <= right: + for c in range(left, right + 1): # 上边，向右 + out.append(grid[top][c]) + for r in range(top + 1, bot + 1): # 右边，向下 + out.append(grid[r][right]) + if top < bot: + for c in range(right - 1, left - 1, -1): # 下边，向左 + out.append(grid[bot][c]) + if left < right: + for r in range(bot - 1, top, -1): # 左边，向上 + out.append(grid[r][left]) + top, bot, left, right = top + 1, bot - 1, left + 1, right - 1 + return [x for x in out if x != blocker] +``` + +`if top < bot` 和 `if left < right` 防的是只剩一行或一列时，下边和左边把上边、右边已经输出的格子再输出一遍。 + +已运行（2026-10-26，Python 3.13.17），四个函数在同一组输入上的输出： + +| 输入 | 正确版本 | `wrong_turn_first` | `wrong_boundary_skip` | `wrong_no_visited` | +| --- | --- | --- | --- | --- | +| `[[1,2,3],[4,5,6],[7,8,9]]` | `[1,2,3,6,9,8,7,4,5]` | `[1,4,5,8,7]` | `[1,2,3,6,9,8,7,4,5]` | `1,2,3,6,9,8,7,4` 反复循环 | +| `[[1,2,3,4],[5,-1,7,8],[9,10,11,12]]` | `[1,2,3,4,8,12,11,10,9,5]` | `[1,5,9,10,11,7,8,12]` | `[1,2,3,4,8,12,11,10,9,5,7]` | `1,2,3,4,8,12,11,10,9,5` 反复循环 | +| `[[1,2,-1],[4,5,6],[7,8,9]]` | `[1,2,5,8,7,4]` | `[1,4,5,8,7]` | `[1,2,6,9,8,7,4,5]` | `1,2,5,8,7,4` 反复循环 | + +逐个看错在哪： + +- `wrong_turn_first` 在没有障碍的 3 × 3 上就错了。从 1 出发，先试右转（向下），走到 4，再先试右转（向左）越界，掉头（向上）是走过的 1，于是左转（向右）走到 5，之后一路偏离螺旋。 +- `wrong_boundary_skip` 在没有障碍时是对的，所以只测原题看不出问题。第二个输入里它多输出了走不到的 7。第三个输入里它没有在障碍处转向，按外圈顺序输出了 6、9，从第三个数起就和正确版本不同。 +- `wrong_no_visited` 走完外圈回到 1 时，1 不是障碍、也没越界，于是继续绕外圈，永远停不下来。 + +## 复杂度 + +时间 O(mn)。每个格子进去后马上标记 visited，之后不会再进，所以外层循环最多走 mn 步，每步最多试 4 个方向。 + +空间 O(mn)，用在 `seen` 上（不算输出）。可以把走过的格子原地改成障碍值来省掉 `seen`，但会改坏输入，要先问（见「Follow-up」）。 + +## 易错点 + +- 每一步先试直走（`t = 0`），走不通再转。先试右转连原题都会走错（见「代码」里的对照）。 +- 忘了 visited 会绕着外圈死循环，visited 也是「转进内圈」的触发条件（见「思路」）。 +- 矩阵为空、起点就是障碍，要在开头先返回空列表。 +- 行列不等时边界分开写 `0 <= nr < m and 0 <= nc < n`，见 [[p:me/python-pitfalls]]。 +- 只测原题看不出四边界写法处理不了障碍，测试时一定带一个会挡住格子的障碍。 + +## 测试用例 + +已运行（2026-10-26），除了上面对照表里的三组： + +| 输入 | 输出 | 测的是什么 | +| --- | --- | --- | +| `[[1,2,3,4],[5,6,7,8],[9,10,11,12]]` | `[1,2,3,4,8,12,11,10,9,5,6,7]` | 行列不等、无障碍 | +| `[[1,-1],[3,4]]` | `[1,3,4]` | 需要左转的情况，「只右转一次」的理解下是 `[1,3]` | +| `[[-1]]` | `[]` | 起点就是障碍 | +| `[]` | `[]` | 空矩阵 | +| `[[7]]` | `[7]` | 单个格子 | +| `[[1,2,3]]` | `[1,2,3]` | 单行 | +| `[[1],[2],[3]]` | `[1,2,3]` | 单列 | + +对照表的第二行（7 走不到）和第三行（3、6、9 走不到）正好拿来和面试官确认规则。 + +## Follow-up + +### 生成版：按螺旋顺序填数，遇到 -1 转向 + +这是 [[q:lc59]] 的 m × n 推广，再加上障碍。做法和上面一样，只是走到一格时填一个递增的数，不读值。矩阵初始全是 0，障碍格是 -1，所以「格子值为 0」同时表示没走过、也不是障碍，不需要单独的 visited。 + +它是对的，原因和遍历版一样：每格第一次走到就被填成正数，之后值不再是 0，不会被第二次走进，转向规则也完全相同，所以填数的顺序就是遍历版的输出顺序。代价和遍历版相同，时间 O(mn)，除了要返回的矩阵本身不需要额外空间。 + +面经只说「遇到 -1 也要转向」，没写障碍怎么给出。下面的代码让调用方传障碍坐标列表 `blockers`，这是【推断】的输入格式。面试官也可能直接给一个已经放好 -1 的矩阵，那就把它当 `g` 用，省掉前三行。走不到的格子留 0【推断】，填 0 还是别的值要先问面试官。 + +```python +DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)] + + +def spiral_fill(m, n, blockers=()): + g = [[0] * n for _ in range(m)] + for r, c in blockers: + g[r][c] = -1 + if m == 0 or n == 0 or g[0][0] == -1: + return g + r = c = d = 0 + k = 1 + g[0][0] = k + while True: + for t in range(4): + nd = (d + t) % 4 + nr, nc = r + DIRS[nd][0], c + DIRS[nd][1] + if 0 <= nr < m and 0 <= nc < n and g[nr][nc] == 0: # 0 = 没走过也不是障碍 + d, r, c = nd, nr, nc + k += 1 + g[r][c] = k + break + else: + return g +``` + +已运行（2026-10-26）： + +- `spiral_fill(3, 3)` → `[[1,2,3],[8,9,4],[7,6,5]]`，和 LC 59 一致。 +- `spiral_fill(3, 4)` → `[[1,2,3,4],[10,11,12,5],[9,8,7,6]]`。 +- `spiral_fill(3, 4, [(1, 1)])` → `[[1,2,3,4],[10,-1,0,5],[9,8,7,6]]`，走到 10 时右边是障碍，结束，`(1, 2)` 留 0。 +- `spiral_fill(3, 3, [(0, 2)])` → `[[1,2,-1],[6,3,0],[5,4,0]]`。 + +### 不用 visited 数组，原地标记 + +读完一格就把它改成障碍值，这样「走过」和「障碍」合成同一个判断，省掉 O(mn) 的 `seen`。代价是输入被改坏，调用方之后再读这个矩阵会出错，所以要先问面试官能不能改输入。 + +```python +def spiral_in_place(grid, blocker=-1): + m = len(grid) + n = len(grid[0]) if m else 0 + if m == 0 or n == 0 or grid[0][0] == blocker: + return [] + r = c = d = 0 + out = [grid[0][0]] + grid[0][0] = blocker + while True: + for t in range(4): + nd = (d + t) % 4 + nr, nc = r + DIRS[nd][0], c + DIRS[nd][1] + if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != blocker: + d, r, c = nd, nr, nc + out.append(grid[r][c]) + grid[r][c] = blocker + break else: return out ``` -已运行（2026-10-17）： - -- 无障碍 3 × 3 → `[1, 2, 3, 6, 9, 8, 7, 4, 5]`，和原题一致。 -- `[[1,2,3,4],[5,#,7,8],[9,10,11,12]]` → `[1, 2, 3, 4, 8, 12, 11, 10, 9, 5]`：走到 5 时右边是障碍、上面走过，就结束了，**7 永远走不到**。 -- `[[1,2,#],[4,5,6],[7,8,9]]` → `[1, 2, 5, 8, 7, 4]`：3、6、9 走不到。 - -后两个例子正好用来和面试官确认规则。 - -## 复杂度 - -O(mn) 时间，每格最多进一次、每次最多试 4 个方向；O(mn) 空间存 visited（可以原地把走过的格子改成标记来省空间，但会改输入，先问）。 - -## 易错点 - -- 「转向」时要从当前方向开始试（`t = 0` 是继续直走），而不是每步都先右转。 -- 起点就是障碍、矩阵为空，要先处理。 - -## 英文讲法 - -> [!say] Instead of shrinking four boundaries, I simulate: keep a direction index and a visited grid, and whenever the next cell is out of bounds, visited, or a blocker, rotate clockwise. If all four directions fail, I stop. Before coding, I'd confirm whether blocked cells can leave some cells unreachable, because with this rule they can. +已运行（2026-10-26）：输入 `[[1,2,3,4],[5,-1,7,8],[9,10,11,12]]`，输出 `[1,2,3,4,8,12,11,10,9,5]`，和正确版本一样。跑完后矩阵变成 `[[-1,-1,-1,-1],[-1,-1,7,-1],[-1,-1,-1,-1]]`，只剩走不到的 7 没被改。 + +### 要求用 Java 写 + +有一篇面经要求用 Java。用 Python 面试可以跳过这一条。Java 写法和思路、复杂度都和 Python 版本相同，它特有的坑和完整代码放在下面的可选知识框里。 + +> [!optional] Java 没有 `for ... else`，要换成一个标志 `moved`：每一步开始时设成 `false`，走成功了设成 `true` 再 `break`，内层循环结束后 `moved` 还是 `false` 就返回。`moved` 必须在每一步开头重置。放到 `while` 外面的话，第一步走成功后它一直是 `true`，走不动时也不会返回，会死循环。已运行（2026-10-26，OpenJDK 21.0.12.1）：把 `moved` 挪到 `while` 外面后，第一个输入就卡住，3 秒超时被终止，什么都没打印。 +> +> 下面的正确版本也已运行（同一天）。四个输入依次是无障碍 3 × 3、题目的例子、`[[1,2,-1],[4,5,6],[7,8,9]]`、`[[1,-1],[3,4]]`，输出 `[1, 2, 3, 6, 9, 8, 7, 4, 5]`、`[1, 2, 3, 4, 8, 12, 11, 10, 9, 5]`、`[1, 2, 5, 8, 7, 4]`、`[1, 3, 4]`，和 Python 版本一致。 +> +> ```java +> import java.util.*; +> +> public class Spiral { +> static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; +> +> static List<Integer> spiralWithBlockers(int[][] grid, int blocker) { +> List<Integer> out = new ArrayList<>(); +> int m = grid.length, n = m == 0 ? 0 : grid[0].length; +> if (m == 0 || n == 0 || grid[0][0] == blocker) return out; +> boolean[][] seen = new boolean[m][n]; +> int r = 0, c = 0, d = 0; +> seen[0][0] = true; +> out.add(grid[0][0]); +> while (true) { +> boolean moved = false; +> for (int t = 0; t < 4; t++) { +> int nd = (d + t) % 4; +> int nr = r + DIRS[nd][0], nc = c + DIRS[nd][1]; +> if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] != blocker) { +> d = nd; r = nr; c = nc; +> seen[r][c] = true; +> out.add(grid[r][c]); +> moved = true; +> break; +> } +> } +> if (!moved) return out; +> } +> } +> } +> ```
meta
@@ -1 +1,5 @@ -{} +{ + "depth_guide": "2026-10-23", + "rewritten_by": "cloud:20261025-2345", + "rewritten_at": "2026-10-26" +}