Leetcode 498 Diagonal Traverse

发表于 |



分析：

  1. 这道题像我们之前做的那种走迷宫的问题，给一个矩阵，0代表可以通信，1代表有障碍，问从左上走到右下最短距离是多少，走不到返回-1，这种就是标准的bfs问题
  2. 这道题中我们按层依次遍历，始终从左下到右上，只要额外判断一下本身该是从右上到左下的层数即可

思路：
用visited记录已经遍历过的下标，rec记录每一层的所有元素，level判断奇偶来决定是否要反转rec

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
class Solution(object):
    def findDiagonalOrder(self, matrix):
        if not matrix or not matrix[0]: return []
        n,m = len(matrix), len(matrix[0])
        
        vis = set([(0,0)])
        Q = collections.deque([(0, 0, 0)])
        res, rec = [], []
        while Q:
            for _ in range(len(Q)):
                i, j, level = Q.popleft()
                for x, y in [(i+1, j), (i, j+1)]:
                    if 0<=x<n and 0<=y<m and (x,y) not in vis:
                        vis.add((x,y))
                        Q.append((x,y,level+1))
                rec.append(matrix[i][j])
            if level % 2 == 1 and rec:
                rec = rec[::-1]
            res.extend(rec)
            rec = []
        return res

# O(m*n) time, O(m*n) space
# 32 / 32 test cases passed.
# difficluty: medium
# Runtime: 204ms,beats 20%