Diagonal Traverse

https://leetcode.com/explore/learn/card/array-and-string/202/introduction-to-2d-array/1167/

Print matrix in zigzag order

这道题可以背诵

我们发现1-9 的矩阵的result是 $[1,2,4,7,5,3,6,8,9]$

 j/i  0 1 2
 0    1 2 3
 1    4 5 6
 2    7 8 9

从上图可以看出i+j相等的都被group在一起，(1) (2,4) (7,5,3) , (6,8), (9)

区别是sum为偶数，倒叙插入，奇数则反之。

from collections import defaultdict
class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        d = defaultdict(list)
        res = []
        m = len(matrix)
        if m == 0:
            return res
        n = len(matrix[0])
        for i in range(m):
            for j in range(n):
                currSum = i+j
                if currSum % 2 == 1:
                    d[currSum].append(matrix[i][j])
                else:
                    d[currSum].insert(0,matrix[i][j])
        
        for l in d:
            res += d[l]
        return res