498. Diagonal Traverse
对角线 matrix坐标
Given an m x n
matrix mat
, return an array of all the elements of the array in a diagonal order.
Example 1:
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]
Example 2:
Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]
Constraints:
m == mat.length
n == mat[i].length
1 <= m, n <= 10
4
1 <= m * n <= 10
4
-10
5
<= mat[i][j] <= 10
5
分析:
↘ 主对角线
i - j == k
k ∈ [-(n-1), m-1]
1329, N-Queens, matrix diagonal sort
✅ 是主对称轴(i==j)
↙ 反对角线
i + j == k
k ∈ [0, m+n-2]
498, 1424, N-Queens, TicTacToe
❌ 不是对称轴
主对角线中心线
i == j
k=0 (i-j=0)
Transpose, isSymmetric
✅ 经典
利用对角线原理 正向对角线 x-y = k 反向对角线 x+y = k
同理可以对对角线组操作,对角线总数 m+n-1
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
if not mat or not mat[0]:
return []
res = []
n,m = len(mat), len(mat[0])
for k in range(n+m-1):
path = []
for i in range(n):
j = k - i
if 0 <= j < m:
path.append(mat[i][j])
if k%2 == 0:
path.reverse()
res += path
return res
初始检查:首先检查输入矩阵是否为空。
初始化参数:设置矩阵的行数
n
和列数m
,初始化结果列表res
,起始位置(row, col)
和初始方向direction
(1 表示右上,-1 表示左下)。遍历矩阵:使用
for
循环遍历矩阵的所有元素。添加当前元素:将当前位置的元素
mat[row][col]
加入结果列表res
。计算下一个位置:根据当前方向计算下一个位置
(new_row, new_col)
。边界检查:
如果下一个位置在矩阵范围内,更新当前位置。
如果超出范围,根据当前方向调整位置并改变方向。
返回结果:最终返回按对角线顺序遍历的结果列表
res
。
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
if not mat or not mat[0]:
return []
res = []
n,m=len(mat),len(mat[0])
row,col = 0,0
dir = 1 #1 up, -1 down
for _ in range(n*m):
res.append(mat[row][col])
new_col = col + (1 if dir == 1 else -1)
new_row = row + (-1 if dir == 1 else 1)
if 0<=new_row<n and 0<=new_col<m:
row,col=new_row,new_col
else:
if dir==1:
if 0<=col + 1<m:
col += 1
else:
row += 1
else:
if 0<=row+1<n:
row += 1
else:
col += 1
dir *= -1
return res
Last updated
Was this helpful?