欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【力扣算法】【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]

【力扣算法】【python】对角线遍历
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/diagonal-traverse/

解题思路

  1. 明确题意:以对角线遍历的顺序返回矩阵中的所有元素
  2. 明确输出:输出的是一个list,包含矩阵中的所有元素
  3. 思路化解:首先是以对角线的顺序一来一回的获取对角线上的元素,所以可以将一个对角线看成一个处理对象;上面的3*3矩阵就包含5个待处理的对象,可以看出最终的输出结果就是将这5个对象按规律拼接在一起就OK了;那么如何确定对象的数量?如何获取这些对象呢?
  4. 对象的获取:看下图
    【力扣算法】【python】对角线遍历
    4.1:每个箭头所连接的元素就是一个我们想要的对象,对象的数量正好是object_count = row_len+col_len-1。
    4.2:接下来是获取每个对象的具体元素值,从[0,0]开始遍历object_count次,当一个对象获取完后,接着获取下一个对象。前col_len个对象的第一个与元素是矩阵的第一行的元素; 之后的所有对象的第一个元素是矩阵的最后一列的元素(去除第一个)。可以将矩阵看作一个二维坐标系, 到达坐标系的边界就是一次遍历的结束条件。
    【力扣算法】【python】对角线遍历

代码

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