Java 中带跳过的锯齿形网格遍历

给定一个 m x n 的正整数二维数组 grid。我们需要沿着之字形路径遍历网格，并跳过每个交替的单元格。之字形模式由以下阶段定义。

• 从左上角的单元格 (0, 0) 开始。
• 到达一行末尾时，在该行内向右移动。
• 向下移动到下一行，然后向左移动，直到到达该行的开头。

在左右遍历之间不断来回进行，直到遍历完所有行。

注意：遍历是通过跳过每个交替的单元格进行的。提供一个 数组，其中按顺序包含在此跳过式之字形遍历期间访问的单元格的值。

示例 1

输入

int grid = [[1,2,3],[4,5,6],[7,8,9]]

输出

顺序是 [1, 3, 5, 7, 9]

解释

在跳过中间元素的同时，遍历具有之字形模式

• 首先转到 grid[0][0] → 1。
• 沿着右下对角线移动到 grid[0][2]。
• 从 grid[0][2] 沿左下对角线移动到 grid[1][1] （跳过 grid[0][1]）→ 5 （跳过 grid[1][0] 和 grid[1][2]）
• 向下移动到 grid[2][0]。
• 从 grid[2][0] 沿右对角线移动到 grid[2][2] （跳过 grid[2][1]）→ 9。

示例 2

输入

int grid = [[2,1],[2,1],[2,1]]

输出

顺序是 [2, 1, 2]

解释

使用之字形模式，遍历会省略中间元素

• 从 grid[0][0] → 2 开始
• 沿右下对角线移动到 grid[0][1] → 1 （跳过了第二行中的 2）
• 沿左下对角线移动到 grid[2][0] → 2，在第二行中跳过了第一行。

示例 3

输入

int grid = [[1,2],[3,4]]

输出

顺序是 [1,4]

解释

使用之字形模式，遍历会省略中间元素

• 从 grid[0][0] → 1 开始
• 沿右下对角线移动到 grid[1][1] → 4 （跳过了 2 和 3）

方法：带有行反转的之字形遍历

GridTraversal 类以之字形方式处理二维网格，该类会交替跳过元素。逐行迭代，为了保持之字形模式，如果行索引为奇数，则会反转该行。在处理完每个组件以强制跳过之后，会使用一个布尔标志 (Add) 来切换其状态，以确定是否将元素包含在结果列表中。使用双指针技术，reverse 方法通过交换数组中的成员来有效地反转行的顺序。此方法通过避免每个交替元素并以交替方向继续，从而保持有组织的网格遍历。

算法

步骤 1：创建一个名为 Add 的布尔标志，并将其初始值设置为 true。使用此标志，交替地将行中的元素包含在结果列表 (res) 中。

步骤 2：从上到下，逐行重复遍历网格。

步骤 3：验证每一行的行索引是奇数还是偶数。

步骤 3.1：如果索引是偶数，则按原样处理该行。

步骤 3.2：处理之前，如果索引是奇数，则翻转该行。

步骤 4：如果 Add 为 true，请检查行中的每个元素，无论其是否被反转。

步骤 4.1：如果为 true，则应将元素包含在结果列表 (res) 中。

步骤 5：为了确保添加行中的不同元素，请在每个元素之后切换标志 (Add = !Add)。

步骤 6：处理完所有行后，返回 res 列表，其中包含网格的之字形遍历。

实施

输出

 
The order is: [1, 3, 5, 7, 9]   

复杂度分析

上述代码的时间复杂度为 O(M * N)，其中 M 表示网格中的行数，N 表示每行的列数。空间复杂度为 O(M * N)。