leetcode回顾——Diagonal Traverse

LeetCode

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

 

示例:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

输出:  [1,2,4,7,5,3,6,8,9]

解释:

s

1
2
3
4

说明:

给定矩阵中的元素总数不会超过 100000 。

题解

这一道题其实可以这样想，将这个二维数组变为一维的，然后呢，结合这个图，虚线部分不管，就只单单看实线连接起来的（1和9就不看了，并且忽略箭头），先看2—>4这条线，如果在一维数组情况下，2所在的index为1，4所在的index为3，他们之间的差距为2；再看3->5->7，3所在的index为2，5所在的index为4，7所在的index为6，这三个数相邻之间的差距也为2，6->8同理，这个时候，我们来看看这个差距2，会发现，这个差距2，就是在原二维数组下，行的最大index值（数组的index下表起始为0），因此，就可以想到，其实就是寻找等间距的数字，而每组的起始数组index，就是这个矩阵的最上一行和最右一列的在一维数组下所对应的index值，而他们所对应的最大寻找位置，是这个矩阵的最左一列和最下一行在一维数组下所对应的index值

1
2
3
[[1, 2, 3], 
 [4, 5, 6],       二维  ==>  一维       [1, 2, 3, 4, 5, 6, 7, 8, 9]
 [7, 8, 9]]

起始数字的index值列表

1
[0, 1, 2, 5, 8]

所对应的最大寻找位置的index值列表

1
[0, 3, 6, 7, 8]

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution:
    def findDiagonalOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if len(matrix) == 0:
            return []
        width = len(matrix[0])
        height = len(matrix)
        if width == 1:
            return [matrix[i][0] for i in range(len(matrix))]
        edge = [i for i in range(width)]
        for i in range(2, height + 1):
            edge.append((width) * i - 1)
        edge_2 = [width * i for i in range(0, height)]
        for i in range(width):
            edge_2.append(edge_2[-1] + 1)
        print(edge_2)
        ans = [matrix[0][0]]
        for i in range(1, len(edge) - 1):
            tmp = []
            for j in range(edge[i], edge_2[i] + 1, width - 1):
                x, y = self.getLoc(n=j, width=width, height=height)
                if x < width and y < height:
                    tmp.append(matrix[y][x])
                else:
                    break
            if int(i % 2) == 0:
                tmp.reverse()
            ans.extend(tmp)
        ans.append(matrix[-1][-1])
        return ans

    def getLoc(self, n, width, height):
        x = int(n % width)
        y = int(n / width)
        return x, y


if __name__ == '__main__':
    s = Solution()
    t_1 = [[2,5],[8,4],[0,-1]]
    t = [[1,2,3,4,5,6,7],
         [8,9,10,11,12,13,14],
         [15,16,17,18,19,20,21]]
    print(s.findDiagonalOrder(matrix=t_1))