0498. 对角线遍历

0498. 对角线遍历 #

  • 标签:数组、矩阵、模拟
  • 难度:中等

题目大意 #

给你一个大小为 m * n 的矩阵 mat

要求:以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。

解题思路 #

这道题的关键是「找规律」和「考虑边界问题」。

找规律:

  • 当行号 + 列号为偶数时,遍历方向为从左下到右上。可以记为右上方向(-1, +1),即行号 -1,列号 +1。
  • 当行号 + 列号为奇数时,遍历方向为从右上到左下。可以记为左下方向(+1, -1),即行号 +1,列号 -1。

边界情况:

  • 向右上方向移动时:
    • 如果在最后一列,则向下方移动,即 x += 1
    • 如果在第一行,则向右方移动,即 y += 1
    • 其余情况想右上方向移动,即 x -= 1y += 1
  • 向左下方向移动时:
    • 如果在最后一行,则向右方移动,即 y += 1
    • 如果在第一列,则向下方移动,即 x += 1
    • 其余情况向左下方向移动,即 x += 1y -= 1

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        rows = len(mat)
        cols = len(mat[0])
        count = rows * cols
        x, y = 0, 0
        ans = []

        for i in range(count):
            ans.append(mat[x][y])

            if (x + y) % 2 == 0:
                # 最后一列
                if y == cols - 1:
                    x += 1
                # 第一行
                elif x == 0:
                    y += 1
                # 右上方向
                else:
                    x -= 1
                    y += 1
            else:
                # 最后一行
                if x == rows - 1:
                    y += 1
                # 第一列
                elif y == 0:
                    x += 1
                # 左下方向
                else:
                    x += 1
                    y -= 1
        return ans

参考资料 #

本站总访问量  次  |  您是本站第  位访问者