Leetcode 1424. Diagonal Traverse II

Tyan

发布于 2021-07-27 15:50:04

2930

发布于 2021-07-27 15:50:04

文章被收录于专栏：SnailTyanSnailTyan

文章作者：Tyan 博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

**解析：**Version 1，根据矩阵对角线元素的规律，行坐标与列坐标和相等的元素属于同一对角线，由于对角线从左下到右上，因此应该同一对角线的元素应该按列坐标的顺序排列，将所有元素按(i+j, j, nums[i][j])保存，并按照(i+j,j)进行排序即可。Version 2，每一条对角线上的数据保存到一个列表中，列表的索引为行坐标与列坐标的和，由于每一条对角线的元素是按照行顺序保存的，因此合并时应将顺序反转。Version 3把问题看做是一个树的遍历问题(广度优先搜索)，每个节点只关心其下边的点及其右侧的点，下边的点只有第一行才有，右侧的点每个点都有，否则会出现重复搜索，要对点是否存在进行判断，搜索顺序使用队列实现。

Version 1

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        diagonals = []
        for i in range(len(nums)):
            for j in range(len(nums[i])):
                diagonals.append((i+j, j, nums[i][j]))
        diagonals.sort(key=lambda x: (x[0], x[1]))
        result = [x[2] for x in diagonals]
        return result

Version 2

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        diagonals = []
        for i in range(len(nums)):
            for j in range(len(nums[i])):
                if i + j == len(diagonals):
                    diagonals.append([])
                diagonals[i+j].append(nums[i][j])
        result = []
        for diagonal in diagonals:
            result += diagonal[::-1]
        return result

Version 3

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:        
        result = []
        queue = collections.deque([(0, 0)])
        while queue:
            i, j = queue.popleft()
            result.append(nums[i][j])
            if i < len(nums) - 1 and j == 0:
                queue.append((i+1, j))
            if j < len(nums[i]) - 1:
                queue.append((i, j+1))
        return result