【力扣算法】【python】对角线遍历
程序员文章站
2022-05-30 22:52:48
题目给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。输入:[[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]输出: [1,2,4,7,5,3,6,8,9]代码class Solution(object): def findDiagonalOrder(self, matrix): """ :type matrix: List[List[int]]...
题目
给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下所示。
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,4,7,5,3,6,8,9]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/diagonal-traverse/
解题思路
- 明确题意:以对角线遍历的顺序返回矩阵中的所有元素
- 明确输出:输出的是一个list,包含矩阵中的所有元素
- 思路化解:首先是以对角线的顺序一来一回的获取对角线上的元素,所以可以将一个对角线看成一个处理对象;上面的3*3矩阵就包含5个待处理的对象,可以看出最终的输出结果就是将这5个对象按规律拼接在一起就OK了;那么如何确定对象的数量?如何获取这些对象呢?
- 对象的获取:看下图
4.1:每个箭头所连接的元素就是一个我们想要的对象,对象的数量正好是object_count = row_len+col_len-1。
4.2:接下来是获取每个对象的具体元素值,从[0,0]开始遍历object_count次,当一个对象获取完后,接着获取下一个对象。前col_len个对象的第一个与元素是矩阵的第一行的元素; 之后的所有对象的第一个元素是矩阵的最后一列的元素(去除第一个)。可以将矩阵看作一个二维坐标系, 到达坐标系的边界就是一次遍历的结束条件。
代码
class Solution(object):
def findDiagonalOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if len(matrix) == 0:
return []
return_list = []
row = 0
col = 0
col_len = len(matrix[0])
row_len = len(matrix)
# 一共需要得到row_len+col_len-1个子数组
for i in range(row_len+col_len-1):
new_list = []
# while 条件即为一个一次遍历结束的标志
while col >= 0 and row < row_len:
new_list.append(matrix[row][col])
col -= 1
row += 1
# 每个子数组的起始元素是先从第一行的元素依次获取,然后再依次取最后一列的元素
if i < col_len-1:
col = i + 1
row = 0
else:
row = i - col_len + 2
col = col_len - 1
# 若i是偶数,则改new_list需要倒置
if i % 2 == 0:
return_list += new_list[::-1]
else:
return_list += new_list
return return_list
本文地址:https://blog.csdn.net/qq_40829873/article/details/107187968