README.md

comments	difficulty	edit_url	tags
true	简单	https://github.com/doocs/leetcode/edit/main/solution/3400-3499/3417.Zigzag%20Grid%20Traversal%20With%20Skip/README.md	数组 矩阵 模拟

3417. 跳过交替单元格的之字形遍历

English Version

题目描述

给你一个 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 <= 50
• 2 <= m == grid[i].length <= 50
• 1 <= grid[i][j] <= 2500

解法

方法一：模拟

我们遍历每一行，如果当前行的索引是奇数，我们就将这一行的元素逆序，然后遍历这一行的元素，按照题目要求的规则将元素加入答案数组中。

时间复杂度 $O(m \times n)$，其中 $m$ 和 $n$ 分别是二维数组 $\textit{grid}$ 的行数和列数。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

Python3

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

Java

class Solution {
    public List<Integer> zigzagTraversal(int[][] grid) {
        boolean ok = true;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < grid.length; ++i) {
            if (i % 2 == 1) {
                reverse(grid[i]);
            }
            for (int x : grid[i]) {
                if (ok) {
                    ans.add(x);
                }
                ok = !ok;
            }
        }
        return ans;
    }

    private void reverse(int[] nums) {
        for (int i = 0, j = nums.length - 1; i < j; ++i, --j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
}

C++

class Solution {
public:
    vector<int> zigzagTraversal(vector<vector<int>>& grid) {
        vector<int> ans;
        bool ok = true;
        for (int i = 0; i < grid.size(); ++i) {
            if (i % 2 != 0) {
                ranges::reverse(grid[i]);
            }
            for (int x : grid[i]) {
                if (ok) {
                    ans.push_back(x);
                }
                ok = !ok;
            }
        }
        return ans;
    }
};

Go

func zigzagTraversal(grid [][]int) (ans []int) {
	ok := true
	for i, row := range grid {
		if i%2 != 0 {
			slices.Reverse(row)
		}
		for _, x := range row {
			if ok {
				ans = append(ans, x)
			}
			ok = !ok
		}
	}
	return
}

TypeScript

function zigzagTraversal(grid: number[][]): number[] {
    const ans: number[] = [];
    let ok: boolean = true;
    for (let i = 0; i < grid.length; ++i) {
        if (i % 2) {
            grid[i].reverse();
        }
        for (const x of grid[i]) {
            if (ok) {
                ans.push(x);
            }
            ok = !ok;
        }
    }
    return ans;
}