[LeetCode]Diagonal Traverse

题目描述:

LeetCode 498. Diagonal Traverse

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]
Explanation:

Note:

  1. The total number of elements of the given matrix will not exceed 10,000.

题目大意:

给定一个M行N列矩阵,用对角顺序返回矩阵的所有元素。

注意:

矩阵元素个数不超过10,000。

解题思路:

初始对角线方向为右上方(偏移量:行-1, 列+1),遇到边界时转向左下方(偏移量:行+1, 列-1)

对于边界的处理:

向右上方移动遇到上边界时,若未达到右边界,则向右移动(偏移量:行+0,列+1),否则向下移动(偏移量:行+1,列+0)

向左下方移动遇到左边界时,若未达到下边界,则向下移动(偏移量:行+1,列+0),否则向右移动(偏移量:行+0,列+1)

Python代码:

class Solution(object):
    def findDiagonalOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix: return []
        i, j, k = 0, 0, 1
        w, h = len(matrix), len(matrix[0])
        ans = []
        for x in range(w * h):
            ans.append(matrix[i][j])
            if k > 0:
                di, dj = i - 1, j + 1
            else:
                di, dj = i + 1, j - 1
            if 0 <= di < w and 0 <= dj < h:
                i, j = di, dj
            else:
                if k > 0:
                    if j + 1 < h:
                        j += 1
                    else:
                        i += 1
                else:
                    if i + 1 < w:
                        i += 1
                    else:
                        j += 1
                k *= -1
        return ans

 

本文链接:http://bookshadow.com/weblog/2017/02/05/leetcode-diagonal-traverse/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码