【力扣算法】【python】对角线遍历

题目

给定一个含有 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/

解题思路

1. 明确题意：以对角线遍历的顺序返回矩阵中的所有元素
2. 明确输出：输出的是一个list，包含矩阵中的所有元素
3. 思路化解：首先是以对角线的顺序一来一回的获取对角线上的元素，所以可以将一个对角线看成一个处理对象；上面的3*3矩阵就包含5个待处理的对象，可以看出最终的输出结果就是将这5个对象按规律拼接在一起就OK了;那么如何确定对象的数量?如何获取这些对象呢?
4. 对象的获取：看下图
   
   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