LeetCode 题解工作台
跳过交替单元格的之字形遍历
给你一个 m x n 的二维数组 grid ，数组由 正整数 组成。 你的任务是以 之字形 遍历 grid ，同时跳过每个 交替 的单元格。 之字形遍历的定义如下： 从左上角的单元格 (0, 0) 开始。 在当前行中向 右 移动，直到到达该行的末尾。 下移到下一行，然后在该行中向 左 移动，直到到达…
3
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·matrix
答案摘要
我们遍历每一行，如果当前行的索引是奇数，我们就将这一行的元素逆序，然后遍历这一行的元素，按照题目要求的规则将元素加入答案数组中。 时间复杂度 $O(m \times n)$，其中 和 分别是二维数组 的行数和列数。忽略答案数组的空间消耗，空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你一个 m x n 的二维数组 grid，数组由 正整数 组成。
你的任务是以 之字形 遍历 grid，同时跳过每个 交替 的单元格。
之字形遍历的定义如下：
- 从左上角的单元格
(0, 0)开始。 - 在当前行中向 右 移动，直到到达该行的末尾。
- 下移到下一行，然后在该行中向 左 移动，直到到达该行的开头。
- 继续在行间交替向右和向左移动，直到所有行都被遍历完。
注意：在遍历过程中，必须跳过每个 交替 的单元格。
返回一个整数数组 result，其中包含按 顺序 记录的、且跳过交替单元格后的之字形遍历中访问到的单元格值。
示例 1：
输入： grid = [[1,2],[3,4]]
输出： [1,4]
解释：
示例 2：
输入： grid = [[2,1],[2,1],[2,1]]
输出： [2,1,2]
解释：
示例 3：
输入： grid = [[1,2,3],[4,5,6],[7,8,9]]
输出： [1,3,5,7,9]
解释：
提示：
2 <= n == grid.length <= 502 <= m == grid[i].length <= 501 <= grid[i][j] <= 2500
解题思路
方法一：模拟
我们遍历每一行，如果当前行的索引是奇数，我们就将这一行的元素逆序，然后遍历这一行的元素，按照题目要求的规则将元素加入答案数组中。
时间复杂度 ，其中 和 分别是二维数组 的行数和列数。忽略答案数组的空间消耗，空间复杂度 。
class Solution:
def zigzagTraversal(self, grid: List[List[int]]) -> List[int]:
ok = True
ans = []
for i, row in enumerate(grid):
if i % 2:
row.reverse()
for x in row:
if ok:
ans.append(x)
ok = not ok
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m _n) since each cell is visited at most once for consideration. Space complexity is O(k) where k is the number of collected elements, proportional to roughly half of m_ n due to skips. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask about handling edge rows with uneven lengths or skips at boundaries.
- question_mark
Check if the candidate correctly toggles direction for zigzag and skips every other cell.
- question_mark
Probe whether the solution dynamically tracks positions without hardcoding indices.
常见陷阱
外企场景- error
Failing to toggle direction for every row, leading to linear instead of zigzag traversal.
- error
Off-by-one errors when skipping cells at row ends or matrix boundaries.
- error
Collecting skipped elements due to incorrect flag handling or index calculation.
进阶变体
外企场景- arrow_right_alt
Traverse the grid diagonally while skipping elements in a defined step pattern.
- arrow_right_alt
Apply the zigzag skip pattern but start from the bottom-left corner instead of top-left.
- arrow_right_alt
Use a different skip interval, such as every third cell, to test generalized simulation logic.